《《数据结构——C语言描述》第6章：树》由会员分享，可在线阅读，更多相关《《数据结构——C语言描述》第6章：树（67页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树,树的概念与定义 二 叉 树 二叉树的遍历与线索化 树和森林 哈夫曼树及其应用 树的计数,6. 1树的概念与定义,树的定义：树(tree)是n(n0)个结点的有限集T，当n=0时，称为空树；当n0时，满足以下条件： （1）有且仅有一个结点被称为树根（root）结点；（2）当n1时，除根结点以外的其余n-1个结点可以划分成m(m0)个互不相交的有限集T1,T2,，Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。,图6.1,结点(node)：表示树中的元素，包括数据项及若干指向其子树的分支。 结点的度(degree)：结点拥有的子树的数目。图6.1中结点A的度
2、为3。 叶子(leaf)：度为0的结点称为叶子结点，也称为终端结点。图6.1中，叶子结点有：K，L，F，G，M，I，J。 分支结点：度不为0的结点称为分支结点，也称为非终端结点。图6.1中，非终端结点有：A，B，C，D等。,孩子结点(child)：结点的子树的根称为该结点的孩子结点。图6.1中，结点A的孩子结点为B，C，D，结点B的孩子结点为E，F。 双亲结点(parents)：孩子结点的上层结点称为该结点的双亲结点。图6.1中，结点I的双亲为D，结点L的双亲为E。 兄弟结点(sibling)：具有同一双亲结点的孩子结点之间互称为兄弟结点。图6.1中，结点B，C，D互为兄弟，结点K，L互为兄弟
3、。,树的度：树中最大的结点的度数即为树的度。图6.1中的树的度为3。结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层。若某结点在第l层，则其孩子结点就在第l+1层。图6.1中，结点A的层次为1，结点M的层次为4。树的高度(depth)：树中结点的最大层次数。图6.1中的树的高度为4。 森林(forest)：m(m0)棵互不相交的树的集合。,有序树与无序树：树中结点的各子树从左至右是有次序的（不能互换）则称该树为有序树，否则称该树为无序树。,6.2 二叉树,二叉树的定义：二叉树是由n(n0)个结点的有限集T构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，
4、并且左右子树都是二叉树。注意：二叉树的子树有左右之分，因此二叉树是一种有序树。,二叉树的性质：,性质1 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2 深度为k的二叉树至多有2k1个结点（k=1）。 性质3 对任意一棵二叉树BT，如果其叶子结点数为n0，度为2的结点数为n2，则n0n21。 性质4 具有n个结点的完全二叉树的深度为【log2n】1。（符号【x】表示不大于x的最大整数。）,二叉树的性质：,性质5 对于具有n个结点的完全二叉树，如果对其结点按层次编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是【i/2】 (2)
5、如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。 完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。,二叉树的存储结构,顺序存储结构 :为了能够反映出结点之间的逻辑关系，必须将它“修补”成完全二叉树，对应该完全二叉树，可以开辟长度为12的数组，对12个数据元素进行存储，原二叉树中空缺的结点在数组中的相应单元必须置空,二叉树的存储结构,链式存储结构 :表示二叉树的链
6、表中的结点应该包含3个域：数据域和指向左、右子树的指针域，二叉树的这种存储结构被称为二叉链表。,在n个结点的二叉链表中，有n+1个空指针域,6.3 二叉树的遍历与线索化,二叉树的遍历：是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。,先根遍历二叉树 （1）访问根结点； （2）先根遍历左子树； （3）先根遍历右子树。,中根遍历二叉树（1）中根遍历左子树；（2）访问根结点；（3）中根遍历右子树。 后根遍历二叉树 （1）后根遍历左子树； （2）后根遍历右子树；（3）访问根结点。,先根遍历: -+a*bcd/ef中根遍历: a+b*cde/f后根遍历: abcd-*
7、+ef/-,typedef struct Node datatype data; struct Node *Lchild; struct Node *Rchild; BTnode,*Btree;,先根遍历算法void preorder(Btree root) if(root!=NULL) Visit(root-data); preorder(root-Lchild); preorder(root-Rchild); ,中根遍历算法void InOrder(Btree root) if(root!=NULL) InOrder(root-Lchild); Visit(root-data); InOr
8、der(root-Rchild); ,后根遍历算法void PostOrder(Btree root)if(root!=NULL) PostOrder(root-Lchild); PostOrder(root-Rchild); Visit(root -data); ,线索二叉树：利用二插链表剩余的n+1个空指针域来存放遍历过程中结点的前驱和后继的指针，这种附加的指针称为“线索”，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。,为了区分结点的指针域是指向其孩子的指针，还是指向其前驱或后继的线索，可在二叉链表的结点中,再增设2个标志域。,0 Lchild域指示结点的左孩子Ltag=
9、 1 Lchild域指示结点的遍历前驱,0 Rchild域指示结点的右孩子Rtag= 1 Rchild域指示结点的遍历后继,中序线索二叉树,基于遍历的应用与线索二叉树的应用,二叉树的遍历是对二叉树进行各种运算的一个重要基础，对访问（程序中的visit函数）结点可理解为各种对二叉树中结点进行操作。因此，只要将二叉树三种遍历算法中的visit函数具体化，就产生了基于二叉树的不同应用。,输出二叉树中的结点,Void paintnode (Btree root) if (root!=NULL)printf (root -data);paintnode (root -Lchild);paintnode
10、(root -Rchild);,输出二叉树中的叶子结点,Void paintleaf (Btree root) if (root!=NULL)if (root -Lchild=NULL & root -Rchild=NULL)printf (root -data);paintleaf (root -Lchild);paintleaf (root -Rchild);,统计叶子结点数目,Void leafcount(Btree root)if(root!=NULL)leafcount(root-Lchild);leafcount(root-Rchild);if (root -Lchild=NULL
11、 & root -Rchild=NULL)count+;,提示：count为全局变量，在主函数中定义。,建立二叉树,图中二叉树的先根遍历序列为：ABDGCEHF，而考虑空子树后的先根遍历序列应为：ABDGCEHF，其中“”代表空子树。,如果已知二叉树的考虑了空子树后的遍历序列，那么建立这棵二叉树的算法如下(假定datatype类型为char)：Void CreateBtree(Btree *bt) char ch;ch=getchar();if(ch=.) *bt=NULL; else*bt=(Btree)malloc(sizeof(BTnode);(*bt)-data=ch;CreateBi
12、Tree(&(*bt)-Lchild);CreateBiTree(&(*bt)-Rchild);,求二叉树的高度,采用递归的方法定义二叉树的高度：（1）若二叉树为空，则高度为0；（2）若二叉树非空，其高度应为其左右子树高度的最大值加1。,int TreeDepth(Btree bt) int hl,hr,max; if(bt!=NULL) hl=TreeDepth(bt-Lchild); hr=TreeDepth(bt-Rchild);,max=(hl，hr); return(max+1); else return(0);,在中根遍历的线索树中查找前驱结点,对于二叉树中任意结点p，要找其前驱结
13、点,当p-Ltag=1时，p-Lchild即为p的前驱结点；当p-Ltag=0时，说明p有左子树，此时p的中根遍历下的前驱结点即为其左子树右链下的最后一个结点。,Void Previous(ThreadTnode * p, ThreadTnode *pre) ThreadTnode *q;if(p-Ltag=1) pre= p-Lchild; else for(q= p-Lchild;q-Rtag=0;q=q-Rchild);pre=q;,在中根遍历的线索树中查找后继结点,二叉树中任意结点p，若要找其后继结点，当p-Rtag=1时，p-Rchild即为p的后继结点；当p-Rtag=0时，说明p
14、有右子树，此时p的中根遍历下的后继结点即为其右子树左链下的最后一个结点。,Void Succedent(ThreadTnode *p, ThreadTnode *succ) ThreadTnode *q;if (p-Rtag=1) succ= p- RChild; else for(q= p-RChild; q-Ltag=0 ;q=q-LChild );succ=q; ,6.4 树和森林,树的存储结构,双亲（链表）表示法,用一组连续的存储空间（数组）来存储树中的结点，每个数组元素中不但包含结点本身的信息，还保存该结点双亲结点在数组中的下标号。数组中每个结点含两个域： 数据域：存放结点本身信息
15、双亲域：指示本结点的双亲结点在数组中位置,在双亲表示法下，树的数据类型定义如下：#define Maxsize 50typedef struct NodeDataType data;int parent;Tnode;Tnode PtreeMaxsize;,1,1,2,2,3,5,5,5,1,6,0,1,2,3,4,5,7,8,data,parent,如何找孩子结点,孩子链表表示法,把每个结点的孩子结点排列起来，构成一个单链表，该单链表就是本结点的孩子链表。具有n个结点的树就形成了n个孩子链表,孩子结点 #define Maxsize 50typedef struct ChildNodeint Child;struct ChildNode * next;ChildNode;,表头结点typedef structDataType data;ChildNode * ChildHead ;DataNode; 孩子链表 DataNode CtreeMaxsize;,
