编程知识 cdmana.com

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

(一)

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

Scroll to Top