《数据结构7-非线性结构1-树》由会员分享，可在线阅读，更多相关《数据结构7-非线性结构1-树（35页珍藏版）》请在金锄头文库上搜索。
1、非线性数据结构树树树树 树：一对多的数据结构，结点之间有分支和层次关系树：一对多的数据结构，结点之间有分支和层次关系 树定义树定义是n个结点的有限集是n个结点的有限集有且仅有一个称为根的结点有且仅有一个称为根的结点n1时,其余结点可分为m个互不相交的有限集，每个结点又是一棵树（称为根的子树）n1时,其余结点可分为m个互不相交的有限集，每个结点又是一棵树（称为根的子树）树的基本概念树的基本概念 结点结点：包含一个数据元素及若干指向其子树的分支：包含一个数据元素及若干指向其子树的分支 结点的度结点的度：结点拥有的子树数目：结点拥有的子树数目 叶结点叶结点(终端结点):度为0的结点(终端结点):度为
2、0的结点 分支结点分支结点(非终端结点):度不为0的结点(非终端结点):度不为0的结点 树的度树的度：树内各结点的度的最大值：树内各结点的度的最大值 子节点子节点：结点子树的根称为该结点的孩子，该结点称为：结点子树的根称为该结点的孩子，该结点称为孩子结点的双亲孩子结点的双亲 兄弟兄弟：双亲相同的孩子之间互称兄弟：双亲相同的孩子之间互称兄弟 结点的祖先结点的祖先：从根到结点所经分支上的所有结点：从根到结点所经分支上的所有结点 子孙子孙：以某结点为根的子树中的任意结点称为该结点的：以某结点为根的子树中的任意结点称为该结点的子孙子孙 层次与深度层次与深度：树的深度为树中结点的最大层次数：树的深度为树
3、中结点的最大层次数 有序树与无序树有序树与无序树 森林森林:n棵树的集合:n棵树的集合树的示意图树的示意图根结点根结点子树子树子树子树二叉树 二叉树的定义：二叉树的定义：n个结点的有限集合n个结点的有限集合n=0称为空二叉树n=0称为空二叉树n0，由根结点和两棵互不相交的子树组成n0，由根结点和两棵互不相交的子树组成有序树有序树根结点根结点子树子树子树子树二叉树的五种基本形态空二叉仅一个根节点空二叉仅一个根节点满二叉树 所有分支结点都存在左子树和右子树所有分支结点都存在左子树和右子树 所有叶子结点都在同一层上所有叶子结点都在同一层上 满二叉树结点编号满二叉树结点编号CABDEFG完全二叉树 只
4、有最下面两层上的结点的度可以小于2只有最下面两层上的结点的度可以小于2 最下一层的结点都集中在该层的最左边最下一层的结点都集中在该层的最左边 所有结点的序号与满二叉树对应位置的序所有结点的序号与满二叉树对应位置的序号一致号一致CABDEFG二叉排序树 如果二叉树不为空,满足左子树上的所有结点的值小于根结点,右子树上的所有结点的值都大于根结点如果二叉树不为空,满足左子树上的所有结点的值小于根结点,右子树上的所有结点的值都大于根结点139421114二叉树的存储结构 顺序存储结构顺序存储结构对于进行了编号的满二叉树或完全二叉树有如下特点：对于进行了编号的满二叉树或完全二叉树有如下特点：如果i1,i
5、结点的父结点序号为i/2如果i1,i结点的父结点序号为i/22i=n,序号为i的结点的左孩子序号为2i2i=n,序号为i的结点的左孩子序号为2i2i+1=n,序号为i的结点的右孩子序号为2i12i+1LC !=NULL) preorder(BT-LC);if(BT-RC!=NULL) preorder(BT-RC);二叉树遍历实例二叉树遍历实例CABDEHGF 中序遍历中序遍历(LDR) 按中序遍历根节点的左子树；按中序遍历根节点的左子树； 访问根节点；访问根节点； 按中序遍历根节点的右子树。按中序遍历根节点的右子树。 遍历结果？ 二叉树遍历实例二叉树遍历实例CABDEHGF 中序遍历中序遍历
6、(LDR) 按中序遍历根节点的左子树；按中序遍历根节点的左子树； 访问根节点；访问根节点； 按中序遍历根节点的右子树。按中序遍历根节点的右子树。 遍历结果 DGBEAFHCVoid inorder(bnode *BT)if(BT=NULL)return;elseif(BT-LC !=NULL) inorder(BT-LC); visit(BT);if(BT-RC!=NULL) inorder(BT-RC);二叉树遍历实例二叉树遍历实例CABDEHGF 后序遍历后序遍历(LRD) 按后序遍历根节点的左子树； 按后序遍历根节点的右子树； 访问根节点； 遍历结果？ 二叉树遍历实例二叉树遍历实例CAB
7、DEHGF 后序遍历后序遍历(LRD) 按后序遍历根节点的左子树； 按后序遍历根节点的右子树； 访问根节点； 遍历结果 GDEBHFCAVoid postorder(bnode *BT)if(BT=NULL)return;elseif(BT-LC !=NULL) postorder(BT-LC);if(BT-RC!=NULL) postorder(BT-RC); visit(BT);根据遍历序列构造二叉树根据遍历序列构造二叉树 实现:利用中序遍历序列,结合先序遍历序列或后序遍历序列重新构造二叉树实现:利用中序遍历序列,结合先序遍历序列或后序遍历序列重新构造二叉树LDR:LDR:DLRDLRLR
8、DLRD已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历序列为CBDEAFHIGJ,试构造这棵二叉树已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历序列为CBDEAFHIGJ,试构造这棵二叉树 ABCDEFGHIJ CBDE FHIGJCBDEAFHIGJ CBDE C DE FHIGJ HIGJ HIGJ HI J 从先序序列中找到根节点 从中序序列中分别找出左子树序列和右子树序列AC,B,D,EF,H,I,G,LFABCD,EH,I,G,JFABCDGEH,IJFABCDGEHJI如果后序遍历序列为CEDBIHJGFA？如果后序遍历序列为CEDBIHJGFA？ CE
9、DBIHJGFA CBDE FHIGJCBDEAFHIGJ CBDE C DE FHIGJ HIGJ HIGJ HI J 从后序序列中找到根节点 从中序序列中分别找出左子树序列和右子树序列二叉排序树的生成二叉排序树的生成 例，将下列例，将下列7个数构成的序列，排列成一个二叉排序树，个数构成的序列，排列成一个二叉排序树，190, 381, 12, 40, 410, 394, 540Void Creat_Binary_Sort_tree(bnode *proot)Bnode *p,*q;Int k;Int I,n;*proot=NULL; /初始化空树初始化空树Printf(“input n:”)
10、; /输入数据元素的个数输入数据元素的个数Scanf(“%d”,&n);For(I=0;ILC = NULL; p-RC = NULL; printf(“input k:”);/输入结点数据输入结点数据 scanf(“%d”,&k);p-data = k; if(*proot=NULL)*proot = p; else q=*proot; /q指向当前待比较的结点指向当前待比较的结点while(q!=NULL) if(q-datak) /插入值小于根插入值小于根 if(q-LC!=NULL) q=q-LC; else q-LC = p; q=null; else /插入值大于根插入值大于根 i
11、f(q-RC!=NULL) q=q-RC; else q-RC = p; q=NULL; /end while /end if(*proot=NULL) /end for/end function树、森林与二叉树的转换树、森林与二叉树的转换 一般树的节点度数不规则，用链表结构表示无法确定指针域数目；一般树的节点度数不规则，用链表结构表示无法确定指针域数目； 按最大指针域存储，则浪费存储空间；按最大指针域存储，则浪费存储空间； 按实际数目分配指针域又增加了编程的困难；按实际数目分配指针域又增加了编程的困难； 按二叉树存储，可以利用二叉树的有关算法来实现树的有关操作。按二叉树存储，可以利用二叉树的
12、有关算法来实现树的有关操作。 树与二叉树的转换 结点的左孩子是树中该结点的第一个子结点，其它孩子结点依次作为前一孩子结点的左孩子是树中该结点的第一个子结点，其它孩子结点依次作为前一孩子(左孩子左孩子)结点的右孩子结点的右孩子 步骤、举例步骤、举例森林与二叉树的转换森林与二叉树的转换 森林中的每棵树转换成二叉树森林中的每棵树转换成二叉树 将转换后的二叉树的根结点看成是兄弟结点，利用树与二叉树的转换规则，将之连接成为二叉树将转换后的二叉树的根结点看成是兄弟结点，利用树与二叉树的转换规则，将之连接成为二叉树 步骤、举例步骤、举例二叉树应用举例二叉树应用举例 最优二叉树与霍夫曼编码最优二叉树与霍夫曼编
13、码 目的：设计一套二进制编码，使得采用该编码通信，总的信息传输量最省；目的：设计一套二进制编码，使得采用该编码通信，总的信息传输量最省； 依据：字符传输的频率；依据：字符传输的频率； 霍夫曼编码举例：霍夫曼编码举例： a(115),b(11),c(14),d(35),e(516),f(254),g(55) 压缩比压缩比typedef struct float weight; int lchild, rchild, parent; HTNodeviod CreateHuffmanTree(T) int i, p1, p2; InitHuffmanTree(T); Input Weight(T); for (i=n; i2n-1; i+) SelectMin(T, i-1, &p1,&p2); Tp1.parent = i; Tp2.parent = i; Ti.lchild = p1; Ti.rchild = p2; Ti.weight=Tp1.weight +Tp2.weight
