数据结构-第6章树和二叉树.

第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用6.1树的定义和基本术语6.1.1树的定义6.1.2基本术语6.1.3树的表示1.树的定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n0，则：（1）有且仅有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）当n1时,其余结点可以划分为m（m0）个互不相交的有限集合T1，T2，…，Tm，每个集合又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1。6.1.1树的定义一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k={ki∣1≤i≤n;n≥0,ki∈elemtype}R={r}其中，n为树中结点个数，若n=0，则为一棵空树，n0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。2.树的逻辑结构描述例如，对图6-1(c)的树结构,可以二元组表示为：K={A，B，C，D，E，F，G，H，I，J，K，L，M}R={r}r={A,B，A,C，A,D，B,E，B,F，C,G，D,H，D,I，E,J，E,K，E,L，H,M}(1)InitTree(&T)初始化树T。(2)Root(T)求树T的根结点(3)Parent(T,x)求树T中，值为x的结点的双亲。(4)Child(T,x,i)求树T中，值为x的结点的第i个孩子。(5)AddChild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)DelChild(x,i)删除值为x的结点的第i个孩子。(7)TraverseTree(T)遍历或访问树T。3.树的基本运算1.结点:树的结点包含一个数据元素及若干指向其子树的分支2.度:一个结点包含子树的数目，称为该结点的度。3.叶子（终端）结点度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。5.双亲结点若结点X有子女Y，则X为Y的双亲结点。6.1.2基本术语6.祖先结点从根结点到该结点所经过分支上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点。9.分支结点除叶子结点外的所有结点，为分支结点，也叫非终端结点。(度不为0的结点)10．层数(层次)根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。12.树的度树中结点度的最大值称为树的度。13.有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。14.无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15．森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。1．树形结构表示法6.1.3树的表示2.凹入法表示法3.嵌套集合表示法4.广义表表示法（A（B（E（J，K，L），F），C（G），D（H（M），I）））6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.2.1二叉树的定义1．二叉树的定义和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态。(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树二叉树的五种基本形态（1）InitBitree(&T)二叉树的初始化。（2）Root(T)求二叉树的根结点（3）Parent(T,x)求二叉树T中值为x的结点的双亲（4）Lchild(T,x)求二叉树T中值为x的结点的左孩子。（5）Rchild(T,x)求二叉树T中值为x的结点的右孩子。（6）Lbrother(T,x)求二叉树T中值为x的结点的左兄弟。（7）Rbrother(T,x)求二叉树T中值为x的结点的右兄弟。2.二叉树的基本运算（8）Traverse(T)遍历二叉树T。（9）CreateBiTree(&T)建立一棵二叉树T。（10）AddLchild(&T,x,y)在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。（11）AddRchild(&T,x,y)在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。（12）DelLchild(&T,x)在二叉树T中，删除值为x的结点的左孩子。（13）DelRchild(&T,x)在二叉树T中，删除值为x的结点的右孩子。性质1若二叉树的层数从1开始，则二叉树的第i层结点数，最多为2i-1个（i≥1）。6.2.2二叉树的性质20=121=222=423=8深度（高度）为k的二叉树最大结点数为2k-1（k≥1）。证明:最大结点个数=20+21+22+……+2k-1=2k-1性质2对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足：n=n0+n1+n2①再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为：n=B+1②另外，由于这些分支是由度为1或2的结点射出的，则有B=n1+2n2③则由上三式得：n0=n2+1性质3为继续给出二叉树的其它性质，先定义两种特殊的二叉树：满二叉树深度为k具有2k-1个结点的二叉树，称为满二叉树。完全二叉树如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1--n的结点一一对应，则称这棵二叉树为完全二叉树。①②③④⑤⑥⑦⑧⑨⑩1112131415具有n个结点的完全二叉树的深度为log2n+1证明：设深度为k,则由性质2和完全二叉树的性质有：2k-1-1n≤2k-1即2k-1≤n2k则有k-1≤log2nk由于k是整数，则有k=log2n+1性质4对于完全二叉树中任一个编号为i的结点(1≤i≤n)，它的父结点和左、右儿子结点的编号与i值有如下的关系：(1)如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为i/2。(2)如果2i≤n，则其左儿子结点编号为2i；若2in，则无左儿子结点。(3)如果（2i+1）≤n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。性质5①②③④⑤⑥⑦⑧⑨⑩11121314156.2.3二叉树的存储结构1.顺序存储结构2.链式存储结构1.顺序存储结构思想:用一个一维数组来存储二叉树的各个结点C语言表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;分析:显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。例:对应的顺序存储结构:下标123456789100123456789完全二叉树的顺序表示:例:对应的顺序存储结构:一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.非完全二叉树的顺序表示:○A○B○C○E○F○G○DABDCEGF总结:顺序存储结构适合存储完全二叉树对于非完全二叉树，采用链式存储结构更合适2.二叉链表结点结构:通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。lchilddatarchild存储表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BITree;这里的TElemType可以是任何相应的数据类型如int、float或char等。二叉链表例:链式存储:A∧B∧EC∧D∧∧G∧∧F∧3.三叉链表通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。lchilddatarchildparent6.3遍历二叉树和线索二叉树6.3.1遍历二叉树定义:二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。本节仅讨论二叉链表的遍历过程。一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序：–①左、根、右；③根、左、右；⑤左、右、根；–②右、根、左；④根、右、左；⑥右、左、根；由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中①、③、⑤三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。(1)中序（InOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：–中序遍历左子树；–访问根结点；–中序遍历右子树。(2)先序（PreOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：–访问根结点；–先序遍历左子树；–先序遍历右子树。三种遍历次序以递归的形式定义：(3)后序（PostOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：–后序遍历左子树；–后序遍历右子树；–访问根结点。•中序遍历序列：•先序遍历序列：•后序遍历序列：二叉树遍历举例HDIBEAFCG○B○C○D○E○F○G○A○H○IABDHIECFGHIDEBFGCA中序遍历递归算法voidInOrder(BITreeT){if(T){InOrder(T-lchild);visit(T-data);InOrder(T-rchild);}}先序遍历递归算法voidPreOrder(BITreeT){if(T){visit(T-data);PreOrder(T-lchild);PreOrder(T-rchild);}}后序遍历递归算法voidPostOrder(BITreeT){if(T){PostOrder(T-lchild);PostOrder(T-rchild);visit(T-data);}}遍历算法的应用二叉树的遍历算法是一个重要的应用注意:1.理解访问根结点的意义2.对具体问题需要考虑遍历的顺序1.先序创建二叉链表StatusCreateBiTree(BITree&T){scanf(&ch);if(ch==‘’)T=Null;else{if(!(T=(BiTNode*)mallo