数据结构学习(三)--树

IT迷途小书童 2020-11-11 14:38:23
学习 数据结构 数据 结构 结构学


(一)

1. 树的定义

树是n个结点的有限集。N=0的时候称为空树。在任意一棵非空数中,(1)有且仅有一个特定的结点称之为根(root)的结点。(2)当n>1时,其余结点可以分为m个互不相交的子树。

树的结点包含一个数据元素和若干个指向其余子树的分支。结点拥有的子树称为结点的Degree)。度为零的点称为叶子leaf)结点或者终端结点。度不为零的结点称为分支结点或内部结点。树的是各个结点度的最大值。结点的子树称为结点的孩子child)。结点又称为子树的双亲parent)。同一个双亲的孩子之间相互称为兄弟sibling)。结点的祖先是从根结点到当前结点所经过的所有结点。以某结点为根节点的子树中任意一个结点都称为该结点的子孙

结点的层次(level)从根节点定义开始,根为第一层,根的孩子为第二层。若结点在第l层,则其子节点在第l+1层。树的最大层次称为树的深度(Depth)或者高度。

将树中的结点的各子树从左到右是有次序的,不能交换的。则该树称为有序树。否则称为无序树

森林(forestm棵不互相交的树的集合称为森林。

2. 树的存储结构

(1) 双亲表示法

用数组的形式存放树的数据元素。

设计结点数据结构。Node包含数据域data和指针域parent。其中data存放结点数据。指针域parent存放双亲结点在数组中的下标。根节点的parent-1.

根据需要,有一些对双亲表示法的变种。比如在Node结点结构中添加一个左边第一个孩子的指针,称为长子域。

(2) 孩子表示法

每个结点有多个指针域,其中每个指针指向一个子树的根节点。这种表示方法也称为多种链表表示法。

方法一:Node结点结构一致。比如除数据域外都有5个孩子指针域。本质上是多重链表。

方法二:Node结点一致。有数据域,度域和孩子域。其中度中数值是整数几,后面就有几个孩子的指针域。

方法三:孩子双亲表示法:每个结点的孩子排列起来,以单链表作为存储结构。n个结点有n个孩子链表。如果是叶子结点,则单链表为空。n个结点又组成一个线性表。用顺序存储结构存储。存放在一维数组中。

一个数组表示顶点。数据元素为结构为(1),数组元素中有一个指针 指向当前结点的孩子链表。类似图中的邻接表。

其中,(1树顶点元素的数据结构为:data【存放数据元素本身】和firstChild【第一个孩子根节点的地址】

2)链表数据元素结构:child【当前孩子结点地址】,next【下一个孩子结点地址】

(3) 孩子兄弟表示法

任何一棵树,它的结点的第一个孩子如果存在就是唯一的,右兄弟如果存在也是唯一的。因此我们设置了两个指针。分别指向该结点的第一个孩子和该结点的兄弟。该方法的特点是,不论什么树,都可以转换成一棵二叉树

结点的数据结构为:datafirstChildrightSib

3. 二叉树定义、性质、建立

(1) 二叉树的定义

二叉树是n个结点的有限集合,该结点或者为空集(称为空二叉树),或者由一个结点和两个互不相交的二叉树组成。

l 特点

每个结点最多有两棵子树,所以,二叉树不存在度大于2的结点。左子树和右子树有顺序的,不能交换。及时某个结点只有一个子树,也必须区分是左子树还是右子树。

二叉树有5中形态。A.空二叉树。B.只有一个根节点。C.根节点只有左子树。D.根节点只有右子树。E.根节点有左子树也有右子树。

l 特殊二叉树

斜树(左斜树--所有结点只有左子树、右斜树--所有结点只有右子树)

满二叉树:所有结点都存在左子树和右子树,并且所有叶子都在同一层上。特点【非叶子结点的度一定为2,同样深度的二叉树中,满二叉树的叶子最多】

完全二叉树:对于满二叉树的最后一层叶子结点。从右向左缺少n个结点。N<满二叉树的叶子结点的个数。

 

 

(2) 二叉树的存储结构

顺序存储

按照满二叉树给二叉树编号。所以,二叉树的每个结点都有自己的编号。将二叉树存入顺序的一维数组中。编号作为数组的下标。数值为数组中的数据元素。

这种方式的缺点是:数组的大小是按照当前二叉树的深度的满二叉树的结点来设置的。如果原二叉树比较稀疏,则浪费比较大。

l 二叉链表

二叉树每个结点最多有两个孩子,所以设计一个数据域和两个指针域的结点。我们成这样的链表为二叉链表。Node结点结构为datalchildrchild。【如果添加双亲结点的指针parent,则为三叉链表】

4. 遍历二叉树

从根节点出发,按照某种次序依次访问所有结点。使得每个结点被访问一次且仅访问一次。

先序,中序和后续遍历的定义中,都使用了递归定义。

已知前序和中序遍历序列,可以唯一确定一棵二叉树

已知中序和后续遍历序列,也可以唯一确认一棵二叉树

已知前序和后续遍历的序列,不能唯一确定一棵二叉树。

(1) 前序遍历

如果二叉树为空,则返回空操作。否则,先访问根节点,然后先序遍历左子树,然后先序遍历右子树。

(2) 中序遍历

如果二叉树为空,则返回空操作。否则,先中序遍历左子树,然后访问根节点,最后中序遍历右子树。

(3) 后续遍历

如果二叉树为空,则返回空操作。否则,先后序遍历左子树,然后访问根节点,最后后序遍历右子树。

(4) 层次遍历

如果二叉树为空,则返回空操作。否则从第一层,也就是根节点开始访问,从上而下逐层访问。在同一层中,按照从左向右的顺序逐个结点访问。

5. 线索二叉树

(1) 概念及结点设计

二叉树中,指向前驱和后继的指针称为线索。加上线索的二叉链表称为线索链表。相应的二叉树称为线索二叉树。

线索化:二叉树以某种次序遍历使其变成线索二叉树的过程称作线索化。

线索二叉树的结点设计。分为5部分,分别是data:数据、lchild:左孩子地址或者某种线索化加入进来的前驱结点地址、ltag0代表lchild为左孩子1代表lchild是某种线索化加入进来的前驱结点地址、rchild:右孩子地址或者某种线索化加入进来的后继结点地址、rtag0代表rchild为右孩子1代表rchild是某种线索化加入进来的后继结点地址。

(2) 线索化步骤及代码实现

以中序遍历为例,对二叉树进行线索化。线索二叉树的过程也是使用递归的方式完成的。

P为当前需要处理的二叉树。

1) 对左二子树进行中序线索化。

2) 如果P的左孩子是否为null,则修改pltag1,同时将前一个结点pre的地址赋给lchild

3) 如果p的前驱pre的右孩子为null,则修改prtag1,同时将p的地址赋值给prerchild

4) p赋值给prepre=p

5) 线索化p的右孩子。

 

 

  1. void InThreading(BiThrTree &p, BiThrTree &pre) {  
  2. if (p) {    // 对以p为根的非空二叉树进行中序线索化  
  3. InThreading(p->lchild, pre);    // 左子树线索化  
  4. if (!p->lchild)      // 空,建前驱线索  
  5. { p->LTag = Thread;    p->lchild = pre; }  
  6. if (!pre->rchild)   // 空,建后继线索  
  7. { pre->RTag = Thread;   pre->rchild = p; }   
  8. pre = p;             // 保持 pre 指向 p 的前驱  
  9. InThreading(p->rchild , pre);  // 右子树线索化  
  10. } // if  
  11. }   
(3) 对已经前序线索化后的二叉树遍历代码

如果node.isLeftThread0,后继元素就取左孩子,如果node.isLeftThread1,后继就是指针所指的后继元素node.right

  1. void preThreadList(Node node) {  
  2. while(node != null) {  
  3. while(!node.isLeftThread) {  
  4. System.out.print(node.data + ", ");  
  5. node = node.left;  
  6. }  
  7. System.out.print(node.data + ", ");  
  8. node = node.right;  
  9. }  

 

6. 树、森林与二叉树的转换

l 树转换成二叉树

(1) 加线:所有兄弟之间加一条线。

(2) 去线:结点和孩子结点间除了最左侧的孩子外连线保留,其余线条去掉。

(3) 调整层次:以树的根节点为轴心,整棵树顺时针调整一定角度。

l 森林转换成二叉树

(1) 每棵树转成二叉树。

(2) 第一棵树不动,从第二棵树开始,依次把后一棵树的 跟结点作为前一棵树的有孩子。

l 二叉树转换成树

(1) 加线:如果某个结点的左孩子存在,则将该节点和左孩子的右孩子,左孩子的右孩子的右孩子 等加一条线。

(2) 去线:删除原线条中所有结点和右孩子的连线。

(3) 层次调整:使层次分明。

7. 赫夫曼树

(1) 定义

从树的一个结点到另一个结点之间的分支构成两个结点之间的路径。路径上的分支数叫路径的长度

树的路径长度就是从根节点到每个结点的路径之和。

树的带权路径的长度为树所有叶子结点的带权路径长度之和。其中带权路径长度之和最小的二叉树称为赫夫曼树。

赫夫曼树的应用主要在压缩和解压缩中。

(2) 构造赫夫曼树算法

根据给定n个权值{W1W2 ... Wn}构造成n棵二叉树的集合,其中每棵树Ti只有一个带权值为Wi的根节点。左右子树都为空。

F中选择两个权值最小的树作为左右子树,且置新的二叉树的根节点的权值为左右子树的权值之和。

F中删除这两棵树,同时将新得到的两棵树加入到F中。

重复23步骤,直至F中只有一棵树位置。这棵树就是赫夫曼树。

(3) 赫夫曼编码

赫夫曼树规定左分支代表0,右分支代表1.从根节点到叶子结点送经过的路径组成的01的序列便是结点对应字符的编码。这就是赫夫曼编码。

版权声明
本文为[IT迷途小书童]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/maopneo/p/13958506.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云