数据结构-树与二叉树ppt课件

1、计算机科学与工程系计算机科学与工程系计算机科学与工程系计算机科学与工程系2P residen t -C E OP ro duct io nM an agerSalesM an agerSh ip p in gSup erv iso rP erso n n elM an agerW areh o useSup erv iso rP urch asin gSup erv iso rH IER A R C H IC A L TR EE S TR U C TU R E计算机科学与工程系计算机科学与工程系3File Documents计算机科学与工程系计算机科学与工程系4AJIHGFEDCB(a)(b

2、)A G E N E R A L T R E E 树是一类重要的非线性数据构造，是以分支关树是一类重要的非线性数据构造，是以分支关系定义的层次构造系定义的层次构造计算机科学与工程系计算机科学与工程系5 树树(Tree)：是包括：是包括n(n=0)个结点的有限集个结点的有限集T。当。当T非空时，满足：非空时，满足：1有且仅有一个特别标出的称为根的有且仅有一个特别标出的称为根的 结点；结点；2除根结点外，其他结点可分为除根结点外，其他结点可分为mm=0 个互不相交非空的有限集个互不相交非空的有限集T1, T2, , Tm, 其中其中 每一个集合本身又是一棵树，称为根的子树每一个集合本身又是一棵树，

3、称为根的子树 (Subtree)。树的递归定义：树的递归定义：空树：不包括任何结点的树。空树：不包括任何结点的树。计算机科学与工程系计算机科学与工程系A只需根结点的树只需根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树计算机科学与工程系计算机科学与工程系7A有子女有子女B,C； B和和 C分别有子女分别有子女D,E,F和和G,H;E有有 子女子女I , J。T=(N,R) ,其中其中N=A, B, C, D, E, F, G, H, I, J R= A, B, A, C, B, D , B, E, B, F, C, G, C, H, E, I, E, J 计算机科学与工程系

4、计算机科学与工程系8(b ) 凹入表凹入表a树形表示树形表示ABCDEFIJGH计算机科学与工程系计算机科学与工程系9(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括号表示法嵌套括号表示法CDEIJFGHAB(c) 文氏图文氏图计算机科学与工程系计算机科学与工程系 根本术语根本术语 结点结点(node)表示树中的元素，包括数据项及假设表示树中的元素，包括数据项及假设干指向其子树的分支干指向其子树的分支 结点的度结点的度(degree)结点拥有的子树数结点拥有的子树数 叶子叶子(leaf)度为度为0的结点的结点 孩子孩子(child)结点子树的根称为该结点的孩子结点子树的根称为该结点

5、的孩子 双亲双亲(parents)孩子结点的上层结点叫该结点的双孩子结点的上层结点叫该结点的双亲亲 兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子 树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数 结点的层次结点的层次(level)从根结点算起，根为第一层，从根结点算起，根为第一层，它的孩子为第二层它的孩子为第二层 深度深度(depth)树中结点的最大层次数树中结点的最大层次数 森林森林(forest)m(m0)棵互不相交的树的集合棵互不相交的树的集合计算机科学与工程系计算机科学与工程系ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的

6、度：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的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点A的层次：的层次：1结点结点M的层次：的层次：4计算机科学与工程系计算机科学与工程系12 无序树、有序树无序树、有序树(ordered tree)对子树的次序不加区别的树叫作无序树。对子树之间对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。的次

7、序加以区别的树叫作有序树。 (a) (a) 树树t t (b) (b) 树树t t 计算机科学与工程系计算机科学与工程系对比树型构造和线性构造对比树型构造和线性构造的构造特点的构造特点计算机科学与工程系计算机科学与工程系线性构造线性构造树型构造树型构造第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点 (无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )计算机科学与工程系计算机科

8、学与工程系 树的根本操作：查查 找找 类类 插插 入入 类类删删 除除 类类计算机科学与工程系计算机科学与工程系 Root(T) / 求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 断定树能否为空树断定树能否为空树 TreeDepth(T) / 求树的深度求树的深

9、度TraverseTree( T, Visit() ) / 遍历遍历计算机科学与工程系计算机科学与工程系InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵棵子树子树计算机科学与工程系计算机科学与工程系 ClearTree(&T) / 将树清空 删除类：删除类：

10、DestroyTree(&T) / 销毁树的构造销毁树的构造DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树计算机科学与工程系计算机科学与工程系 6.2 二叉树二叉树 定义定义 定义：二叉树是定义：二叉树是n(n0)个结点的有限集，它或个结点的有限集，它或为空树为空树(n=0)，或由一个根结点和两棵分别称为，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成左子树和右子树的互不相交的二叉树构成 特点特点 每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2的结的结点点) 二叉树的子树有左、右

11、之分，且其次序不能恣意二叉树的子树有左、右之分，且其次序不能恣意颠倒颠倒计算机科学与工程系计算机科学与工程系 根本形状根本形状A只需根结点只需根结点的二叉树的二叉树 空二叉树空二叉树AB右子树为空右子树为空AB左子树为空左子树为空ABC左、右子树左、右子树均非空均非空计算机科学与工程系计算机科学与工程系 二叉树性质二叉树性质 性质性质1：证明：用归纳法证明之证明：用归纳法证明之 i=1时，只需一个根结点，时，只需一个根结点， 是对的是对的 假设对一切假设对一切j(1j(i1)1)计算机科学与工程系计算机科学与工程系v性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有 个结点个结点(k1)

12、12 k证明：由性质证明：由性质1，可得深度为，可得深度为k 的二叉树最大结点数是的二叉树最大结点数是122)(111kkikiii层的最大结点数第计算机科学与工程系计算机科学与工程系v性质性质3：对任何一棵二叉树：对任何一棵二叉树T，假设其终端结点数为，假设其终端结点数为n0，度，度为为2的结点数为的结点数为n2，那么，那么n0=n2+1证明：证明：n1n1为二叉树为二叉树T T中度为中度为1 1的结点数的结点数 由于：二叉树中一切结点的度均小于或等于由于：二叉树中一切结点的度均小于或等于2 2 所以：其结点总数所以：其结点总数n=n0+n1+n2 (1)n=n0+n1+n2 (1) 又由于

13、在二叉树中，除根结点外，其他结点都只又由于在二叉树中，除根结点外，其他结点都只 有一个分支进入有一个分支进入 设设B B为分支总数，那么为分支总数，那么n=B+1n=B+1 又：分支由度为又：分支由度为1 1和度为和度为2 2的结点射出，的结点射出， B=n1+2B=n1+2* *n2n2 于是，于是，n=B+1=n1+2n=B+1=n1+2* *n2+1 (2)n2+1 (2) n1+2 n1+2* *n2+1 =n0+n1+n2 n2+1 =n0+n1+n2 n0=n2+1n0=n2+1计算机科学与工程系计算机科学与工程系 几种特殊方式的二叉树几种特殊方式的二叉树 满二叉树满二叉树 定义：

14、定义：12个结点的二叉树称为且有一棵深度为kkl特点：每一层上的结点数都是最大结点数特点：每一层上的结点数都是最大结点数v完全二叉树完全二叉树l定义：深度为定义：深度为k，有，有n个结点的二叉树当且仅当个结点的二叉树当且仅当其每一个结点都与深度为其每一个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称为的结点一一对应时，称为l特点特点l叶子结点只能够在层次最大的两层上出现叶子结点只能够在层次最大的两层上出现l对任一结点，假设其右分支下子孙的最大层次为对任一结点，假设其右分支下子孙的最大层次为l，那么其左分支下子孙的最大层次必为那么其左分支下子孙的最大层次必为l

15、或或l+1计算机科学与工程系计算机科学与工程系1231145891213671014151231145891267101234567123456计算机科学与工程系计算机科学与工程系性质性质4：具有：具有n个结点的完全二叉树的深度个结点的完全二叉树的深度k为为log2n +1.证明证明:假设深度为假设深度为k,那么根据性质那么根据性质2和完全二叉树的定义和完全二叉树的定义有有: 2k-1-1n 2k-1 等价于等价于: 2k-1 n 2k k-1 log2n k k= log2n +1计算机科学与工程系计算机科学与工程系v性质性质5：假设对一棵有：假设对一棵有n个结点的完全二叉树的结个结点的完全

16、二叉树的结点按层序编号，那么对任一结点点按层序编号，那么对任一结点i(1in)，有：，有：v (1) 假设假设i=1，那么结点，那么结点i是二叉树的根，无双亲；是二叉树的根，无双亲；假设假设i1，那么其双亲是，那么其双亲是i/2 v (2) 假设假设2in，那么结点，那么结点i无左孩子；假设无左孩子；假设2in，那么其左孩子是那么其左孩子是2iv (3) 假设假设2i+1n，那么结点，那么结点i无右孩子；假设无右孩子；假设2i+1n，那么其右孩子是，那么其右孩子是2i+1计算机科学与工程系计算机科学与工程系28i2i2i+1i/2123456789计算机科学与工程系计算机科学与工程系29性质性

17、质5的证明：对于的证明：对于2和和3 当当i=1时，时， 2i=2 n ，左子女结点的序号为，左子女结点的序号为2。2i+1=3 n， 右子女结点的序号为右子女结点的序号为3。 假设对于序号为假设对于序号为j的结点，命题成立。的结点，命题成立。 对于对于i=j+1，其左子女结点的序号等于，其左子女结点的序号等于j的右子的右子女结点的序号加女结点的序号加1，即：，即：2j+1+1=2(j+1) 其右子女结点的序号等于：其右子女结点的序号等于：2(j+1)+1根据根据2和和3，知的父结点为，知的父结点为i/2. 完全二叉树的层次序列，反映了它的构造。完全二叉树的层次序列，反映了它的构造。计算机科学

18、与工程系计算机科学与工程系30123jj+1 2j 2j+1 2(j+1) 2(j+1)+1计算机科学与工程系计算机科学与工程系31i2i+12i+2(i-1)/2012345678从编号？从编号？计算机科学与工程系计算机科学与工程系 二叉树的存储构造二叉树的存储构造 顺序存储构造顺序存储构造 实现：按满二叉树的结点层次编号，依次存放二叉树实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素中的数据元素 特点：特点： 结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0

19、0 0 f g 1 2 3 4 5 6 7 8 9 10 11计算机科学与工程系计算机科学与工程系 链式存储构造 二叉链表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode , *BiTree;lchild data rchild ABCDEFG在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针域个空指针域? AB C D E F G计算机科学与工程系计算机科学与工程系l三叉链表三叉链表typedef struct BiTNodeTElemType data; struct

20、 BiTNode *lchild, *rchild, *parent; BiTNode, *BiTree;lchild data parent rchildABCDEFG A B C D E F G计算机科学与工程系计算机科学与工程系 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 遍历树遍历树 遍历遍历按一定规律走遍树的各个顶点，且按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完好而使每一顶点仅被访问一次，即找一个完好而有规律的走法，以得到树中一切结点的一个有规律的走法，以得到树中一切结点的一个线性陈列线性陈列计算机科学与工程系计算机科学与工程系 顺着某一条搜索途径巡访

21、二叉树顺着某一条搜索途径巡访二叉树中的结点，使得每个结点均被访问一中的结点，使得每个结点均被访问一次，而且仅被访问一次。次，而且仅被访问一次。u问题的提出问题的提出“访问的含义可以很广，如：输出访问的含义可以很广，如：输出结点的信息等。结点的信息等。计算机科学与工程系计算机科学与工程系u “遍历是任何类型均有的操作，遍历是任何类型均有的操作，u对线性构造而言，只需一条搜索途径对线性构造而言，只需一条搜索途径(由于每个结点均只需一个后继由于每个结点均只需一个后继)u而二叉树是非线性构造，每个结点有而二叉树是非线性构造，每个结点有两个后继，那么存在如何遍历即按什么两个后继，那么存在如何遍历即按什么

22、样的搜索途径进展遍历的问题样的搜索途径进展遍历的问题计算机科学与工程系计算机科学与工程系 1先上后下的按层次遍历；先上后下的按层次遍历； 2先左子树后右子树先左子树后右子树的遍历；的遍历； 3先右子树后左子树先右子树后左子树的遍历。的遍历。计算机科学与工程系计算机科学与工程系二、先左后右的遍历算法二、先左后右的遍历算法先根序的遍历算法先根序的遍历算法中根序的遍历算法中根序的遍历算法后根序的遍历算法后根序的遍历算法根根左左子树子树右右子树子树根根根根根根根根根根计算机科学与工程系计算机科学与工程系 假设二叉树为空树，那么空操作；否那么，假设二叉树为空树，那么空操作；否那么，1访问根结点；访问根结

23、点；2先序遍历左子树；先序遍历左子树；3先序遍历右子树。先序遍历右子树。先根序的遍历算法：先根序的遍历算法：计算机科学与工程系计算机科学与工程系 假设二叉树为空树，那么空操作；否那么，假设二叉树为空树，那么空操作；否那么，1中序遍历左子树；中序遍历左子树；2访问根结点；访问根结点；3中序遍历右子树。中序遍历右子树。中根序的遍历算法：中根序的遍历算法：计算机科学与工程系计算机科学与工程系 假设二叉树为空树，那么空操作；否那么，假设二叉树为空树，那么空操作；否那么，1后序遍历左子树；后序遍历左子树；2后序遍历右子树；后序遍历右子树；3访问根结点。访问根结点。后根序的遍历算法：后根序的遍历算法：计算

24、机科学与工程系计算机科学与工程系 二叉树的遍历二叉树的遍历 方法方法 先序遍历：先访问根结点先序遍历：先访问根结点,然后分别先序遍历左子树、右子树然后分别先序遍历左子树、右子树 中序遍历：先中序遍历左子树，然后访问根结点，最后中序中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树遍历右子树 后序遍历：先后序遍历左、右子树，然后访问根结点后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL计算机科学与工程系计算机科学与工程系ADBCD L RAD L RD L

25、 RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历:计算机科学与工程系计算机科学与工程系ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历中序遍历:计算机科学与工程系计算机科学与工程系ADBC L 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

26、*b - c d/e f-+a*b-c d/e f计算机科学与工程系计算机科学与工程系ABCDEFGHK练习：练习：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A计算机科学与工程系计算机科学与工程系 遍历算法遍历算法 递归算法递归算法 非递归算法非递归算法void PreorderTraverse(T) if(T) printf(%dt,T-data); preorder(T-lchild); preorder(T-rchild); 主程序主程序Pre( T )前往前往前往前往前

27、往前往前往前往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 Cpre(T R);pre(T R);l非递归算法：中序非递归算法：中序ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP

28、-B访问：访问：C(4)pABCDEFGiP-A访问：访问：C B(5)ABCDEFGiP-AP-D访问：访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：访问：C Bp(7)ABCDEFGiP-AP-D访问：访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：访问：C B EP=NULL(9)ABCDEFGiP-A访问：访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：访问：C B E Gp(10)ABCDEFGiP-A访问：访问：C B E G D Fp=NULL(13)ABCDEF

29、Gi访问：访问：C B E G D F Ap(14)ABCDEFGi访问：访问：C B E G D F Ap=NULL(15)计算机科学与工程系计算机科学与工程系Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法算法6.3 / 采用二叉链表存储构造，采用二叉链表存储构造，Visit是对数据元素操作的运用函数。是对数据元素操作的运用函数。 / 中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。 stack S; BiTree p; InitStack(S);

30、 p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; / 非空指针进栈，继续左进非空指针进栈，继续左进 else / 上层指针退栈，访问其所指结点，再向右进上层指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse计算机科学与工程系计算机科学与工程系遍历算法的运用举例遍历算法的运用举例2 2、建立二叉树的存储构造、建立二叉树的存储构造1、查询二叉树中某个结点、查询

31、二叉树中某个结点计算机科学与工程系计算机科学与工程系计算机科学与工程系计算机科学与工程系1. 在二叉树不空的前提下在二叉树不空的前提下,和根结点的元素进和根结点的元素进展比较展比较,假设相等假设相等,那么找到前往那么找到前往 TRUE;2. 否那么在左子树中进展查找否那么在左子树中进展查找,假设找到假设找到,那么前往那么前往 TRUE;3. 否那么继续在右子树中进展查找否那么继续在右子树中进展查找,假设假设找到找到,那么前往那么前往 TRUE,否那么前往否那么前往 FALSE;计算机科学与工程系计算机科学与工程系Status Preorder (BiTree T, ElemType x, Bi

32、Tree &p) / 假设二叉树中存在和假设二叉树中存在和 x 一样的元素，那么一样的元素，那么 p 指向该结点并前往指向该结点并前往 OK,/ 否那么前往否那么前往 FALSE if (T) if (T-data=x) p = T; return OK, /if else return FALSE;else if (Preorder(T-lchild, x, p) return OK; else return(Preorder(T-rchild, x, p) ;/else计算机科学与工程系计算机科学与工程系不同的定义方法相应有不同不同的定义方法相应有不同的存储构造的建立算法的存储构造

33、的建立算法计算机科学与工程系计算机科学与工程系以字符串的方式以字符串的方式 “根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树,空树要显式表示空树要显式表示计算机科学与工程系计算机科学与工程系例如例如: :以空白字符“#表示ABCDA(B(# ,C(# , # ),D(# , # )空树空树只含一个根结点的二叉树只含一个根结点的二叉树A以字符串“A # #表示以以下字符串表示计算机科学与工程系计算机科学与工程系Status CreateBiTree(BiTree &T) scanf(&ch); if (ch=#) T = NULL; else if (!(T = n

34、ew BiTNode) exit(OVERFLOW); T-data = ch; / 生成根结点生成根结点 CreateBiTree(T-lchild); / 构造左子树构造左子树 CreateBiTree(T-rchild); / 构造右子树构造右子树 return OK; / CreateBiTree计算机科学与工程系计算机科学与工程系A B # C # # D # # A BCD上页算法执行过程举例如下:ATBCDscanf(&ch);if (ch= ) T = NULL;else if (!(T = new BiTNode) exit(OVERFLOW); T-data = c

35、h;CreateBiTree(T-lchild); CreateBiTree(T-rchild);计算机科学与工程系计算机科学与工程系v遍历算法运用遍历算法运用v按先序遍历序列建立二叉树的二叉链表，知先序序列按先序遍历序列建立二叉树的二叉链表，知先序序列为：为：v A B C # # D E # G # # F # # #ABCDEFG A B C D E F G 计算机科学与工程系计算机科学与工程系由二叉树的非空结点的由二叉树的非空结点的先序和中序序列建树先序和中序序列建树计算机科学与工程系计算机科学与工程系 一棵二叉树的先序遍历序列为一棵二叉树的先序遍历序列为ABCDEFG，它，它的中序遍

36、历序列能够是的中序遍历序列能够是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEGB 一棵二叉树的先序遍历序列为一棵二叉树的先序遍历序列为EFHIGJK，它，它的中序遍历序列为的中序遍历序列为HFIEJKG，那么该二叉树，那么该二叉树根节点的右孩子为根节点的右孩子为( ) A.EB.F C.GD.HB, DC计算机科学与工程系计算机科学与工程系 一棵二叉树的先序遍历序列为一棵二叉树的先序遍历序列为ABCDEF，它的中序遍历为它的中序遍历为CBAEDF，那么后序遍，那么后序遍历序列为历序列为( ) A.CBEFDAB.FEDCBA C.CBEDFAD.不确定不确

37、定 一棵二叉树的后序遍历序列为一棵二叉树的后序遍历序列为DABEC，中序遍历序列为中序遍历序列为DEBAC，那么先序遍，那么先序遍历序列为历序列为( ) A.ACBEDB.DECAB C.DEABCD.CEDBADA计算机科学与工程系计算机科学与工程系 任何任何n个不同结点的二叉树个不同结点的二叉树,都可由它的都可由它的中序序列和先序序列独一确定中序序列和先序序列独一确定 任何任何n个不同结点的二叉树个不同结点的二叉树,都可由它的都可由它的中序序列和后序序列独一确定中序序列和后序序列独一确定计算机科学与工程系计算机科学与工程系 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg 不能独一

38、确定一棵二叉树，不能独一确定一棵二叉树， 假好像时知二叉树的中序序列假好像时知二叉树的中序序列“cbdaegf,那么会如何？那么会如何？ 二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根计算机科学与工程系计算机科学与工程系a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列计算机科学与工程系计算机科学与工程系void CrtBT(BiTree& T, char pre, char ino, int ps, int is, in

39、t n ) / 知知preps.ps+n-1为二叉树的先序序列，为二叉树的先序序列， / inois.is+n-1为二叉树的中序序列，本算为二叉树的中序序列，本算 / 法由此两个序列构造二叉链表法由此两个序列构造二叉链表 if (n=0) T=NULL; else k=Search(ino, preps); / 在中序序列中查询在中序序列中查询 if (k= -1) T=NULL; else / / CrtBT 计算机科学与工程系计算机科学与工程系if (!(T= new BiTNode) exit(OVERFLOW);T-data = preps;if (k=is) T-Lchild = N

40、ULL;else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is );if (k=is+n-1) T-Rchild = NULL;else CrtBT(T-Rchild, pre, ino, ps+1+(k-is), k+1, n-(k-is)-1 );计算机科学与工程系计算机科学与工程系 知二叉树的中序遍历序列知二叉树的中序遍历序列char ino以及以及后序遍历序列后序遍历序列char post，请用算法生，请用算法生成该二叉树用二叉链表的方式存储。成该二叉树用二叉链表的方式存储。计算机科学与工程系计算机科学与工程系线索二叉树线索二叉树计算机科学与工程系计

41、算机科学与工程系线索二叉树线索二叉树定义：定义：遍历二叉树以一定规那么将二叉树中的结点陈列成遍历二叉树以一定规那么将二叉树中的结点陈列成一个线形序列一个线形序列,在二叉树的先序、中序或后序遍历序在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继列中两个相邻的结点互称为前驱与后继线索：指向前驱或后继结点的指针称为线索：指向前驱或后继结点的指针称为线索二叉树：加上线索的二叉链表表示的二叉树叫线索二叉树：加上线索的二叉链表表示的二叉树叫线索化：对二叉树按某种遍历次序使其变为线索二线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫叉树的过程叫实现实现在有在有n个结点的二叉链表中必

42、定有个结点的二叉链表中必定有n+1个空链域个空链域在线索二叉树的结点中添加两个标志域在线索二叉树的结点中添加两个标志域lt :假设假设 lt =0, lc 域指向左孩子；假设域指向左孩子；假设 lt=1, lc域指向域指向其前驱其前驱rt :假设假设 rt =0, rc 域指向右孩子；假设域指向右孩子；假设 rt=1, rc域指域指向其后继向其后继结点定义：结点定义： lc lt data rt rc计算机科学与工程系计算机科学与工程系ABCDE A B D C ET先序序列：先序序列：ABCDE先序线索二叉树先序线索二叉树00001111 11计算机科学与工程系计算机科学与工程系ABCDE

43、A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111计算机科学与工程系计算机科学与工程系ABCDE A B D C ET后序序列：后序序列：CBEDA后序线索二叉树后序线索二叉树0000111111计算机科学与工程系计算机科学与工程系二叉排序树二叉排序树计算机科学与工程系计算机科学与工程系 二叉排序树二叉排序树 定义：二叉排序树或是一棵空树，或是具有以下定义：二叉排序树或是一棵空树，或是具有以下性质的二叉树：性质的二叉树： 假设它的左子树不空，那么左子树上一切结点的假设它的左子树不空，那么左子树上一切结点的值均小于它的根结点的值值均小于它的根结点的

44、值 假设它的右子树不空，那么右子树上一切结点的假设它的右子树不空，那么右子树上一切结点的值均大于或等于它的根结点的值值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树它的左、右子树也分别为二叉排序树计算机科学与工程系计算机科学与工程系 二叉排序树二叉排序树 二叉排序树的插入二叉排序树的插入 插入原那么：假设二叉排序树为空，那么插插入原那么：假设二叉排序树为空，那么插入结点应为新的根结点；否那么，继续在其入结点应为新的根结点；否那么，继续在其左、右子树上查找，直至某个结点的左子树左、右子树上查找，直至某个结点的左子树或右子树为空为止，那么插入结点应为该叶或右子树为空为止，那么插入结点

45、应为该叶子结点的左孩子或右孩子子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排的查找、插入操作之后，可生成一棵二叉排序树序树计算机科学与工程系计算机科学与工程系插入算法插入算法例例 10， 18， 3， 8， 12， 2， 710101810183101838101838 12101838 122101838 1227中序遍历二叉排序树可得到一个关键字的有序序列中序遍历二叉排序树可得到一个关键字的有序序列计算机科学与工程系计算机科学与工程系Status SearchBST(BiTree T, KeyTyp

46、e key, BiTree f, BiTree &p) / 算法算法9.5(b) / 在根指针在根指针T所指二叉排序树中递归地查找其关键字等于所指二叉排序树中递归地查找其关键字等于key的数据的数据元素，元素， / 假设查找胜利，那么指针假设查找胜利，那么指针p指向该数据元素结点，并前往指向该数据元素结点，并前往TRUE， / 否那么指针否那么指针p指向查找途径上访问的最后一个结点并前往指向查找途径上访问的最后一个结点并前往FALSE， / 指针指针f指向指向T的双亲，其初始调用值为的双亲，其初始调用值为NULL if (!T) p = f; return FALSE; / 查找不胜利

47、查找不胜利 else if (EQ(key, T-data.key) p = T; return TRUE; / 查找胜利查找胜利 else if (LT(key, T-data.key) return SearchBST(T-lchild, key, T, p); / 在左子树中继续查找在左子树中继续查找 else return SearchBST(T-rchild, key, T, p); / 在右子树中继续查找在右子树中继续查找 / SearchBSTSearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)在在T为根的二为根的二叉

48、树中查找关键字等于叉树中查找关键字等于key的数据元素的数据元素(f指向指向T的双亲的双亲),查找胜利查找胜利,返返true,p指向该节点指向该节点,否那么否那么p指向查找途径上的最后一个节点指向查找途径上的最后一个节点,前往前往false计算机科学与工程系计算机科学与工程系Status InsertBST(BiTree &T, ElemType e)BiTNode *p;BiTNode *s;if(!SearchBST(T, e, NULL, p)s = (BiTNode *)malloc(sizeof(BiTNode);s-data = e;s-lchild = NULL;s-rc

49、hild = NULL;if(!p)T = s;else if(e data) p-lchild = s;else p-rchild = s;return TRUE;else return FALSE;SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)在在T为根的二为根的二叉树中查找关键字等于叉树中查找关键字等于key的数据元素的数据元素(f指向指向T的双亲的双亲),查找胜利查找胜利,返返true,p指向该节点指向该节点,否那么否那么p指向查找途径上的最后一个节点指向查找途径上的最后一个节点,前往前往false计算机科学与工程系计

50、算机科学与工程系 二叉排序树的删除二叉排序树的删除 要删除二叉排序树中的要删除二叉排序树中的p结点，分三种情况：结点，分三种情况： p为叶子结点，只需修正为叶子结点，只需修正p双亲双亲f的指针的指针f-lchild=NULL f-rchild=NULL p只需左子树或右子树只需左子树或右子树 p只需左子树，用只需左子树，用p的左孩子替代的左孩子替代p (1)(2) p只需右子树，用只需右子树，用p的右孩子替代的右孩子替代p (3)(4) p左、右子树均非空左、右子树均非空 沿沿p左子树的根左子树的根C的右子树分支找到的右子树分支找到S，S的右子树为空，的右子树为空，将将S的左子树成为的左子树成

51、为S的双亲的双亲Q的右子树，用的右子树，用S取代取代p (5)或者用或者用C替代替代p, p的右孩子成为的右孩子成为S的右孩子。的右孩子。 假设假设C无右子树，用无右子树，用C取代取代p (6)计算机科学与工程系计算机科学与工程系SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1)p只需左子树，用只需左子树，用p的左孩子替代的左孩子替代p计算机科学与工程系计算机科学与工程系中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)SPPRQ

52、中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SQPRPp只需右子树，用只需右子树，用p的右孩子替代的右孩子替代p计算机科学与工程系计算机科学与工程系p左、右子树均非空左、右子树均非空沿沿p左子树的根左子树的根C的右子树分支找到的右子树分支找到S，S的右子树为空，将的右子树为空，将S的左子树成为的左子树成为S的的双亲双亲Q的右子树，用的右子树，用S取代取代p (5)或者用或者用C替代替代p, p的右孩子成为的右孩子成为S的右孩的右孩子。子。假设假设C无右子树，用无右子树，用C取代取代p (6)计算机科学与工程系计算机科学与工程系FPCPRCL中序遍历：中序遍

53、历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C PR F(6)FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(5)FSCPRCLQQLSL计算机科学与工程系计算机科学与工程系l删除算法删除算法例例805012060110150557053删除删除508060120110150557053删除删除60805512011015053701042581365删除删除1084256135删除删除68425513计算机科学与工程系计算机科学与工程系Status

54、DeleteBST(BiTree &T, KeyType key) / 算法算法9.7 / 假设二叉排序树假设二叉排序树T中存在关键字等于中存在关键字等于key的数据元素时，的数据元素时， / 那么删除该数据元素结点那么删除该数据元素结点p，并前往，并前往TRUE；否那么前往；否那么前往FALSE if (!T) return FALSE; / 不存在关键字等于不存在关键字等于key的数据元素的数据元素 else if (EQ(key, T-data.key) / 找到关键字等于找到关键字等于key的数据元素的数据元素 return Delete(T); else if (LT(key

55、, T-data.key) return DeleteBST(T-lchild, key); else return DeleteBST(T-rchild, key); / DeleteBST计算机科学与工程系计算机科学与工程系Status Delete(BiTree &p) / 算法算法9.8 / 从二叉排序树中删除结点从二叉排序树中删除结点p，并重接它的左或右子树，并重接它的左或右子树 BiTree q, s; if (!p-rchild) / 右子树空那么只需重接它的左子树右子树空那么只需重接它的左子树 q = p; p = p-lchild; free(q); else if

56、(!p-lchild) / 只需重接它的右子树只需重接它的右子树 q = p; p = p-rchild; free(q); else / 左右子树均不空左右子树均不空 q = p; s = p-lchild; while (s-rchild) / 转左，然后向右到尽头转左，然后向右到尽头 q = s; s = s-rchild; p-data = s-data; / s指向被删结点的指向被删结点的“后继后继 if (q != p) q-rchild = s-lchild; / 重接重接*q的右子树的右子树 else q-lchild = s-lchild; / 重接重接*q的左子树的左子树

57、free(s); return TRUE; / Delete计算机科学与工程系计算机科学与工程系树和森林树和森林计算机科学与工程系计算机科学与工程系 6.4 树和森林树和森林 树的存储构造树的存储构造 双亲表示法双亲表示法 实现：定义构造数组存放树的结点，每个结点含两实现：定义构造数组存放树的结点，每个结点含两个域：个域： 数据域：存放结点本身信息数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难特点：找双亲容易，找孩子难typedef struct PTNode /节点构造节点构造 TElemType dat

58、a; int parent;PTNode;typedef struct /树构造树构造 PTNode nodesMAX_TREE_SIZE int r,n;abcdefhgiacdefghib-1011244406012345789dataparent如何找孩子结点如何找孩子结点计算机科学与工程系计算机科学与工程系 孩子表示法孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度结点不同构：结点指针个数不等，为该结

59、点的度ddata child1 child2 . childDdata degree child1 child2 . childd计算机科学与工程系计算机科学与工程系l孩子链表：每个结点的孩子结点用单链表存储，再用含孩子链表：每个结点的孩子结点用单链表存储，再用含n个个元素的构造数组指向每个孩子链表元素的构造数组指向每个孩子链表孩子结点：孩子结点：typedef struct CTNode int child; /该结点在表头数组中下标该结点在表头数组中下标 struct CTNode *next; /指向下一孩子结点指向下一孩子结点 *ChildPtr;表头结点：表头结点：typedef s

60、truct TElemType data; /数据域数据域 *ChildPtr firstchild; /指向第一个孩子结点指向第一个孩子结点 CTBox ; typedef struct /树构造树构造 CTBox nodesMAX_TREE_SIZE ; int r,n; CTree;计算机科学与工程系计算机科学与工程系abcdefhgi6012345789acdefghibdatafc1 2 34 8675如何找双亲结点如何找双亲结点计算机科学与工程系计算机科学与工程系l带双亲的孩子链表带双亲的孩子链表501234678acdefghibdatafc 12 34867 5012235551parentabcdefhgi计算机科学与工程系计算机科学与工程系 孩子兄弟表示法二叉树表示法孩子兄弟表示法二叉树表示法 实现：用二叉链