数据结构学习笔记（树、二叉树）

树（一对多的数据结构）

树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种： （1）有且仅有一个特定的称为根（Root）的结点； （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

对于树的定义还需要强调两点： 1.n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。 2.m>0时，子树的个数没有限制，但它们一定是互不相交的。

结点分类： 结点拥有的子树数称为结点的度。度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

结点间关系： 结点的子树的跟称为该结点的孩子，相应地，该结点称为孩子的双亲。 同一个双亲的孩子之间互称兄弟，结点的祖先是从根到该结点所经分支上的所有结点。

树的其他相关概念： 结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第I层，则其子树的根就在第I+1层。其双亲在同一层的结点互为堂兄弟。 树中结点的最大层次称为树的深度或高度。 如果将树种结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。 森林是m(m>=0)课互不相交的树的集合。

树的存储结构： 双亲表示法、孩子表示法、孩子兄弟表示法。

1.双亲表示法（时间复杂度为O(1))： 在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。 结点结构为：data | parent 其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。 由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1. 2.孩子表示法： 把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

为此，设计两种结点结构： 一个是孩子链表的孩子结点， child | next 其中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点的指针。 另一个是表头数组的表头结点， data | firstchild 其中data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。

3.孩子兄弟表示法： 任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。 结点结构如表所示： data | firstchild | rightsib 其中data是数据域，first child为指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址。

二叉树

二叉树的定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。（在某个阶段都是两种结果的情形）

二叉树的特点有： *每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。 *左子树和右子树是有顺序的，次序不能任意颠倒。 *即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有五种基本形态： 1.空二叉树。 2.只有一个根结点。 3.根结点只有左子树。 4.根结点只有右子树。 5.根结点既有左子树又有右子树。

特殊二叉树： 1.斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。 2.满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。 满二叉树的特点有： *叶子只能出现在嘴下一层。出现在其它层就不可能达成平衡。 *非叶子结点的度一定是2。 *在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3.完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。 完全二叉树的特点： *满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

*叶子结点只能出现在最下两层。 *最下层的叶子一定集中在左部连续位置。 *倒数二层，若有叶子结点，一定都在右部连续位置。 *如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。 *同样结点的二叉树，完全二叉树的深度最小。

**判断某二叉树是否是完全二叉树： 给每个结点按照二叉树的结构逐层顺序编号，如果编号出现空挡，就说明不是完全二叉树，否则就是。

二叉树的性质 1.性质1：在二叉树的第i层上至多有2∧i-1个结点（i>=1)。 2.性质2：深度为k的二叉树至多有2∧k -1个结点（k>=1)。 3.性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 4.性质4：具有n个结点的完全二叉树的深度为[log2n]+1 ([x]表示不大于x的最大整数。 5.性质5：如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1) 的结点按层序编号（从第1层到[log2n]+1层，每层从左到右），对任一节点i(1≦i≦n)有： *.如果i=1,则结点i是二叉树的根，无双亲；如果i>1, 则其双亲是结点[i/2]。 *.如果2i>n, 则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。 *.如果2i+1>n, 则结点i无右孩子；否则其右孩子是结点2i+1。

##二叉树的存储结构

1.二叉树的顺序存储结构： 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。 *顺序存储结构一般只用于完全二叉树。

2.二叉链表（链式存储结构） 二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

##二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点呗访问一次且仅被访问一次。

二叉树遍历方法 1.前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

2.中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

3.后序遍历：规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

4.层序遍历：规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

*前序遍历算法： /*二叉树的前序遍历递归算法*/ void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c", T-?lchild); /*显示结点数据，可以更改为其他对结点操作*/ PreOrderTraverse(T->lchild); /*再先序遍历左子树*/ PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/ }

*中序遍历算法： /*二叉树的中序遍历递归算法*/ void InOrderTraverse(BiTree T) { if(T==NULL) return; InOrderTraverse(T->lchild); /*中序遍历左子树*/ printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/ InOrderTraverse(T->rchild); /*最后中序遍历右子树*/ }

*后序遍历算法： /*二叉树的后序遍历递归算法*/ void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /*先后序遍历左子树*/ PostOrderTraverse(T->rchild); /*再后续遍历右子树*/ printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/ }

**已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

##二叉树的建立：建立二叉树，也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点，给结点赋值的操作而已。 **对二叉树进行拓展：将二叉树中每个结点的空指针引出一个虚节点，其值唯一特定值，比如”#“。

用前序遍历生成二叉树： /*按前序输入二叉树中结点的值（一个字符）*/ /** #表示空树，构造二叉链表表示二叉树T。*/ void CreateBiTree(BiTree *T) { TElemType ch; scanf("%c", &ch); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; /*生成根结点*/ CreateBiTree(&(*T)->lchild); /*构造左子树*/ CreateBiTree(&(*T)->rchild); /*构造右子树*/ } }

##线索二叉树

*对于一个有n个结点的儿茶链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-1(n-1)=n+1个空指针域。

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

*线索二叉树，等于是把一棵二叉树转变成了一个双向链表。

*对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

#线索二叉树结构实现： /*二叉树的二叉线索存储结构定义*/ typedef enum(Link,Thread) PointerTag; /*Link==0表示指向左右孩子指针*/ /*Thread==1表示指向前驱或后继的线索*/ typedef struct BiThrNode /*二叉树线索存储结点结构*/ { TElemType data; /*结点数据*/ struct BiThrNode *lchild, *rchild; /*左右孩子指针*/ PointerTag LTag; PointerTag RTag; /*左右标志*/ }BiThrNode, *BiThree;

*线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

*线索二叉树的时间复杂度为O(n).

#如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

##树、森林与二叉树的转换

#.树转换为二叉树 1.加线。在所有兄弟结点之间加一条连线。 2.去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。 3.层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

#森林转换为二叉树 1.把每个树转换为二叉树。 2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

#二叉树转换为树 1.加线。若某结点的右孩子存在，则将做左孩子的n各右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。 2.去线。删除原二叉树中所有结点与其右孩子结点的连线。 3.层次调整。使之结构层次分明。

***判断一棵二叉树能够转换成一棵树还是森林，就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

#二叉树转换为森林 1.从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，在查看分离后的二叉树，若右孩子存在，则连线删除......，直到所有右孩子连线都删除为止，得到分离的二叉树。 2.再将每棵分离后的二叉树转换为树即可。

树与森林的遍历 树的遍历分为两种方式 1.一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。、 2.另一种是后跟遍历，即先依次后根遍历每棵子树，然后再访问根结点。

森林的遍历也分为两种方式： 1.前序遍历：先访问森林中第一棵树的根结点，然后再依次县根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。 2.后序遍历：是先访问森林中第一棵树，后跟遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

**当以二叉树做作树的存储结构时，树的先根遍历和后跟遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

赫夫曼树及其应用 1、路径和路径长度 　　在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 2、结点的权及带权路径长度 　　若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 3、树的带权路径长度 　　树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。 其中带权路径长度WPL最小的二叉树称作赫夫曼树。

#赫夫曼树的构造： 1.先把有权值得叶子结点按照从小到大的顺序排列成一个有序序列，即：A5, E10, B15, D30, C40。 2.取头两个最小权值的结点作为一个新节点N1的两个子结点，注意相对较小的是左孩子，这里就是A为N1的左孩子，E为N1的右孩子。新结点的权值为两个叶子权值得和5+10=15. 3.将N1替换A与E，插入有序序列中，保持从小到大排列。即：N115,B15,D30,C40. 4.重复步骤2.将N1与B作为一个新节点N2的两个子结点。N2的权值=15+15=30。 5.将N2替换N1与B，插入有序序列中，保持从小到大排列。即：N230,D30,C40. 6.重复步骤2.将N2于D作为一个新节点N3的两个子结点。N3的权值=30+30=60. 7.将N3替换N2与D，插入有序序列中，保持从小到大排列。即：C40， N360. 8.重复步骤2.将C与N3作为一个新节点T的两个子结点，由于T即是根结点，完成赫夫曼树的构造。

#构造赫夫曼树的赫夫曼算法描述： 1.根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中没棵二叉树Ti中只有一个带权为w1根结点，其左右子树均为空。 2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 3.在F中删除这两棵树，同时将新得到的二叉树加入F中。 4.重复2和3步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。

#赫夫曼编码 *若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

*一般地，设需要编码的字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶子结点，以w1,w2,…,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。