《数据结构-树(1)-严蔚敏版》由会员分享，可在线阅读，更多相关《数据结构-树(1)-严蔚敏版（78页珍藏版）》请在金锄头文库上搜索。
1、第五章 树树是一类重要的非线性数据结构，是以分支关 系定义的层次结构 5.1 树的定义定义 v定义：树(tree)是n(n0)个结点的有限集T，其中： l有且仅有一个特定的结点，称为树的根(root) l当n1时，其余结点可分为m(m0)个互不相交的有限集 T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的 子树(subtree) v特点： l树中至少有一个结点根 l树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树基本术语 v结点(node)表示树中的元素，包括数据项及若干 指向其子树的分支 v结点的度(degree)结点拥有的子树数 v叶子(leaf
2、)度为0的结点 v孩子(child)结点子树的根称为该结点的孩子 v双亲(parents)孩子结点的上层结点叫该结点的 v兄弟(sibling)同一双亲的孩子 v树的度一棵树中最大的结点度数 v结点的层次(level)从根结点算起，根为第一层， 它的孩子为第二层 v深度(depth)树中结点的最大层次数 v森林(forest)m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3 结点B的度：2 结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D 结点B的孩子：E，F结点I的双亲：D 结点L的双亲：E结点B，C，D为兄弟 结点K，L为兄弟树的度：3结点A的层
3、次：1 结点M的层次：4树的深度：4结点F，G为堂兄弟 结点A是结点F，G的祖先 5.2 二叉树定义 v定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成 v特点 l每个结点至多有二棵子树(即不存在度大于2的结点) l二叉树的子树有左、右之分，且其次序不能任意颠倒 v基本形态A只有根结点 的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树 均非空二叉树性质 v性质1：证明：用归纳法证明之i=1时，只有一个根结点， 是对的 假设对所有j(1j1，则其 双亲是i/2(2) 如果2in，则结点i无左孩子；如果2
4、in，则其左孩子是2i(3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子 是2i+1 5.3 树的存储结构树的存储结构 v双亲表示法 l实现：定义结构数组存放树的结点，每个结点含两个域： u数据域：存放结点本身信息 u双亲域：指示本结点的双亲结点在数组中位置 l特点：找双亲容易，找孩子难typedef struct node datatype data;int parent; JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或 存结点个数如何找孩子结点v孩子表示法 l多重链表：每个结点有多个指针域
5、，分别指向其子树的根 u结点同构：结点的指针个数相等，为树的度D u结点不同构：结点指针个数不等，为该结点的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子链表：每个结点的孩子结点用单链表存储，再用含n个 元素的结构数组指向每个孩子链表孩子结点：typedef struct node int child; /该结点在表头数组中下标struct node *next; /指向下一孩子结点JD; 表头结点：typedef struct tnode datatype data; /数据域struct node *fc
6、; /指向第一个孩子结点TD;TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc2 34 59 7 86如何找双亲结点l带双亲的孩子链表612345789acdefghibdatafc2 34 59 7 86012235551parentabcdefhgiv孩子兄弟表示法（二叉树表示法） l实现：用二叉链表作树的存储结构，链表中每个结点的两个 指针域分别指向其第一个孩子结点和下一个兄弟结点 l特点 u操作容易 u破坏了树的层次typedef struct node datatype data;struct node *fch, *nsib; JD;ab
7、cdefhgia b c d e f g h i二叉树的存储结构 v顺序存储结构 l实现：按满二叉树的结点层次编号，依次存放二叉树中的数 据元素 l特点： u结点间关系蕴含在其存储位置中 u浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v链式存储结构 l二叉链表typedef struct node datatype data;struct node *lchild, *rchild; JD;lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABC DE F
8、Gl三叉链表typedef struct node datatype data;struct node *lchild, *rchild, *parent; JD;lchild data parent rchildABCDEFGAB C DE FG树与二叉树转换ACBED树ABCDE二叉树A BC D E A B C D E A BC D E 对应存储存储解释解释v将树转换成二叉树 l加线：在兄弟之间加一连线 l抹线：对每个结点，除了其左孩子外，去除其与其余孩子之 间的关系 l旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIA
9、BCDEFGHI树转换成的二叉树其右子树一定为空v将二叉树转换成树 l加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩 子的右孩子，沿分支找到的所有右孩子，都与p的双亲 用线连起来 l抹线：抹掉原二叉树中双亲与右孩子之间的连线 l调整：将结点按层次排列，形成树结构 ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIv森林转换成二叉树 l将各棵树分别转换成二叉树 l将每棵树的根结点用线相连 l以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时 针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJv
10、二叉树转换成森林 l抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索 到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 l还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 5.4 树和二叉树的遍历树的遍历 v遍历按一定规律走遍树的各个顶点，且使每一顶点 仅被访问一次，即找一个完整而有规律的走法，以得到 树中所有结点的一个线性排列 v常用方法 l先根（序）遍历：先访问树的根结点，然后依次先根遍历根的 每棵子树 l后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 l按层次遍历：先访问第一层上的结点，然后依次遍历第二层， 第n层
11、的结点ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO二叉树的遍历 v方法 l先序遍历：先访问根结点,然后分别先序遍历左子树、右子树 l中序遍历：先中序遍历左子树，然后访问根结点，最后中序 遍历右子树 l后序遍历：先后序遍历左、右子树，然后访问根结点 l按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLR RDL、RLD、DRLADBCD L RA D L RD L RBDCD L R先序遍历序列：A B D C先序遍历:A
12、DBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:ADBCL R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e fv算法 l递归算法Ch5_1.cvoid preorder(JD *bt) if(bt!=NULL) printf(“%dt“,bt-data);preorder(bt-lchild);preorder(bt-rchild);
13、 主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B); pre(T L);BTAprintf(A); pre(T L);ATDprintf(D); pre(T L);DTCprintf(C); pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D Cl非递归算法ABCDEFGpi P-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGi P-A访问：
14、C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B E p(8)ABCDEFGiP-AP-DP-G访问：C B E P=NULL(9)ABCDEFGi P-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E G p(10)ABCDEFGi P-A访问：C B E G D Fp=NULL (13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)Ch5_4.c Ch5_40.C后序遍历非递归算法v遍历算法应用 l按先序遍历序列建立二叉树的二叉链表，已知先序序
