算法与数据结构 树.ppt

1、6.1 树的基本概念及ADT 6.2 二叉树 6.2.1 二叉树的概念 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.2.4 二叉树的遍历 6.3 线索二叉树 6.4 树和森林 6.5 Huffman树和Huffman编码,第六章 树,树的应用,某些数据库管理系统含有分层结构的数据库；复杂的程序，采用的基本数据结构是树； 在编译系统中，编译程序把高级语言的语句或表达式分解为树结构加以分析和处理，然后生成机器代码的目的码指令； 操作系统的文件处理采用分级管理的办法，采用树结构，以提高文件的存取速度； 某些操作系统把主存也按树结构划分，树中的每个结点包含数据或代码段； 某些程序模块本

2、身近似于树型结构； 二叉排序树：特点是用非线性结构表示一个线性有序表； 决策树：在企业的数据处理和系统分析等领域中出现的决策问题：即要求根据一些给定条件来确定应采取什么行动，如保险公司的业务决策； 博弈树（Game Tree）：人机博弈； 堆（heap）排序：实际上是一棵完全二叉树结点的层次序列； Ldap： 轻量目录访问协议； Huffman树：信息检索； ,树例与特征,社会的组织结构 家族的族谱 计算机中的目录组织 描述层次结构，是一种一对多的逻辑关系,是一种非线性结构,6.1 树的基本概念及其ADT定义,树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。 有且仅有一个称为根的

3、结点（Root）； n1时，其余结点可分为m(m0)个互不相交的有限集T1Tm,其中每个集合又是一棵树，称为子树(SubTree),树定义,T1,T2,T3,树的抽象数据类型,ADT Tree 数据对象 D：D是具有相同性质的数据元素的集合。 数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root,则存在D-root的一个划分D1，D2Dm（m0）,对任意 jk(1j,km)有 DjDK=,且对任意的 i(1 i m ),存在唯一的数据元素xi Di ,H

4、; （3）对应于D-root的划分，H-,有唯一的一个划分H1, H2,Hm(m0),对任意jk(1j,km)有HjHk=,且对任意i(1 i m )，Hi是Di上的二元关系， (Di，Hi）是一棵符合本定义的树，称为根root的子树。,注意：“”是集合的补运算，“”是集合的交运算,基本操作： TreeInit(T); TreeChild (T,x,i); Treebuild(T,F); TreeClear(T); Traverse (T); TreeRoot(T); TreeParent(T,x); TreeRightBrother(T,x); TreeLeftBrother(T,x); T

5、reeInsert(T,y,i,x); ADT Tree,树的抽象数据类型,请看教材p.98.,树的其它逻辑表示方式,凹入表示法,嵌套集合表示法,广义表表示法,树型表示法,类似于书的编目,结点（Node）：一个数据元素及若干指向其子树的分支； 结点的度(Degree)：结点拥有的子树的数目。 叶子（终端结点Leaf)：度为0的结点； 分支结点（非终端结点）：度不为0的结点。除根结点之外的分支结点，也称内部结点； 树的度：树内各结点的度的最大值； 孩子（Child），双亲（Parent)，兄弟(Sibling):结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟。

6、,树的若干概念,概念,祖先(Ancestor)：从根结点到该结点所经分支上的所有结点。 子孙(Descendants)：以某结点为根的子树中的任一结点都称为该结点的子孙。 层次(Level)：结点在树结构中的层（根为第一层）。 深度（Depth）：树中结点的最大层次称为树的深度； 有序树：结点的子树在树中的位置固定，不能互换，称有序树 无序树：可以互换,有的教材规定为第0层,概念,森林（Forest)：m(m0)棵互不相交的树的集合。 删去一棵树的根就得到一个森林。反之加上一个结点做树根，森林就变成一棵树。,注意与自然界中的树和森林的概念不同。,任何一棵非空树是一个二元组 Tree=(root

7、,F) 其中：root被称为根结点 F被称为子树森林,概念示例,结点 结点的度(Degree) 叶子（Leaf)或终端结点 分支结点或非终端结点 树的度 层次(Level) 树的深度(Depth) 孩子（child) 双亲（Parent) 兄弟(Sibling) 祖先 子孙,树的基本操作,分为三大类： 查找 插入 删除,查找操作,分为特定的查找和按关系的查找 特定的查找 Root(T); Value(T,cur_e); 按关系的查找 Parent(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); 某些特性的判别 TreeEmpty(

8、T); TreeDepth(T); 特殊的操作 TraverseTree(T,Visit( );,查找树中值为cur_e的某个结点,查找树中值为cur_e的结点的最左边的孩子,插入操作,InitTree(,根据定义生成树，如给定树根和子树森林可以生成树,改变树上某个结点的值,插入一棵子树，如在树T中指针p所指的位置插入一棵以c为根的子树，并且作为第i棵子树,删除操作,ClearTree(,删除树T中某个结点的某个子树,一般讨论的是有向树（箭头略去不画）： 1） 有确定的根； 2） 树根和子树根之间为有向关系,树和其子树之间的次序,有序树和无序树之间的区别在于： 子树之间是否存在次序关系。,如果

9、讨论的是无序树，则这两棵树是等同的，否则是不等同的。 此书一般讨论无序树,树结构和线性结构的比较,线性结构,树结构,第一个数据元素 （无前驱）,根结点 （无前驱）,最后一个数据元素 （无后继）,多个叶子结点 （无后继）,其他数据元素 （一个前驱， 一个后继）,树中其他结点 （一个前驱， 多个后继）,一对一,一对多,6.2 二叉树,6.2.1 二叉树的概念 二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树。 特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒,许多实际问题抽象出来

10、的数据结构往往是二叉树的形式,根结点A的左子树,根结点A的右子树,二叉树的五种形态,空树,只有一个根结点的树,右子树为空,左子树为空,左右子树均非空,与有序树不同，即使只有一棵子树也要区分出是左子树还是右子树。,右子树为空,左子树为空,二叉树的抽象数据类型,ADT BinTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=，则R=，称二叉树为空二叉树； 若D，则R=H，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root,则存在D-root=D1,Dr,且D1Dr； （3）若D1，则D1中存在唯一的元素x1,H

11、,且存在D1上的关系 H1H；若Dr,则Dr中存在唯一的元素xr, H, 且存在Dr上的关系HrH；H=, H1, Hr; （4）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树， （Dr，Hr）是一棵符合本定义的二叉树，称为根的右子树。,二叉树的抽象数据类型,基本操作： BinTreeInit (BT); BinTreeRoot(BT); BinTreeParent(BT,x); BinTreeLeftChild (BT,x); BinTreeRightChild (BT,x); BinTreeBulid(BT,LBT,RBT); BinTreeInsertLeft(BT,y,x);

12、BinTreeInsertRight(BT,y,x); BinTreeDeleteLeft(BT,x); BinTreeDeleteRight(BT,x); BinTreeClear(BT); BinTraverse(BT); ADT BinTree,主要操作也是三类： 查找 插入 删除,6.2.2 二叉树的性质,1.一个非空二叉树的第i层上至多有2i-1个结点（i1） 证明(用数学归纳法)： i = 1, 只有根结点， 2i-1 201，显然成立 设i = k时成立，最多有2k-1 当i= k+1时，最多的结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1 2.

13、深度为k的二叉树至多有2k-1个结点(k1) 证明：由性质1 可知，只有每层的结点数达到最大时，其树的结点数为最多。二叉树的结点个数为： 20 +21 +22 +2k-1 =1 + 2 + + 2k-1= 2k-1,因为每个结点的度最多为2，所以乘以2,注意等比级数前n项的求和公式,二叉树的性质,3.对任意一棵非空二叉树BT，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 +1; 证明： 设n1为BT中度为1的结点数，则总结点数： n = n0 + n1 + n2 另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则 n=B+1 由于这些分支

14、是由度为1或2的结点射出的，所以又有： B=n1+2*n2 即： B=n1+2*n2 n-1； n= n1+2*n2 +1； 由式子 和 得到： n0 + n1 + n2 n1+2*n2 +1; n0 = n2 +1,填空题,如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。 【南京理工大学 2001 二、3（2分）】,答案为： 69 根据二叉树性质3,满二叉树（特殊形态的二叉树）,满二叉树（Full Binary Tree）：深度为k且有2k-1个结点的二叉树。 考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到

15、右。,满二叉树,其特点是每一层上的结点树都是最大结点数。 不存在度为1的结点,完全二叉树（特殊形态的二叉树）,完全二叉树(Completed Binary Tree)：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。 特征： 叶子结点只可能在层次最大的两层上出现 任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的最大层次为l或l+1.,完全二叉树,满二叉树是完全二叉树的 一种特殊情况,完全二叉树的性质,1.具有n个结点的完全二叉树的深度为： k = log2n +1 （x 表示不大于x的最大整数，如6.9=6 ） 证

16、明：设树的深度为k，则由完全二叉树的定义和性 质 2 可知： 2k-1 1 n 2k 1 或： 2k-1 n 2k 取对数后： k-1 log2n k 由于k是整数， k = log2n + 1,请看与教材p.103.的不同,填空题,一个有2001个结点的完全二叉树的高度为_。 【南京理工大学 1997 三、2（1分）】,答案为： 11 k = log2n + 1= log22001 + 1=10+1=11,完全二叉树的性质,2.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1、2、3n,则对任一结点i（1in）有： （a）如果i=1,此结点为根结点，无双亲；若i1,则

17、其双亲结点是i/2。 （b）如果2in,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。 （c）如果2i+1n，则结点i无右孩子，否则其右孩子是结点2i+1。,完全二叉树示意图,结点i和i1在同一层上,完全二叉树示意图,结点i和i+1不在同一层上,满二叉树是完全二叉树的一种特殊形式,练习题,在下述结论中，正确的是（ ） 【南京理工大学 1999 一、4 （1分）】 只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D,答案为： D,练习题,若一棵二叉树具有10个度为2的结点，5个度为

18、1的结点，则度为0的结点个数是（ ） A9 B11 C15 D不确定 【北京工商大学2001一.7(3分)】,答案为： B 二叉树性质 3,练习题,具有10个叶结点的二叉树中有（ ）个度为2的结点， 【北京航空航天大学2000 一、5（2分)】 A8 B9 C10 Dll,答案为： B 二叉树性质 3,练习题,有关二叉树下列说法正确的是（ ） 【南京理工大学 2000 一、11 （1.5分）】 A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2,答案为： B,练习题,二叉树的第I层上最多含有结点数为（ ） 【中山大学1998二、7

19、（2分）】 【北京理工大学 2001 六、5（2分）】 A2I B 2I-1-1 C 2I-1 D2I -1,答案为： C 二叉树性质1,练习题,一个具有1025个结点的二叉树的高h为（ ） 【南京理工大学 1999 一、19 （2分）】 A11 B10 C11至1025之间 D10至1024之间,答案为： C 注意可能是单支树,练习题,将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A4 B5 C6 D7 【南京理工大学2000一、5 1.5分）】,答案为： C 根据完全二叉树性质1 k = log3244 +1=5+1=6,判断题,二叉树是度为2的有序树。 【长

20、沙铁道学院1997一、3(1分)】 【中科院软件所1997一、9(1分)】,答案为： 错,判断题,完全二叉树一定存在度为1的结点。 【青岛大学 2002 一、4 （1分）】,答案为： 错,判断题,深度为K的二叉树中结点总数2k-1。 【南京航空航天大学 1995 五、1 （1分）】,答案为： 对,判断题,完全二叉树中，若一个结点没有左孩子，则它必是树叶。 【东南大学 2001一、1-8（1分）】 【中科院软件所1997一、2（1分）】 【山东大学2001一、4 (1分)】,答案为： 对,判断题,下面二叉树的定义只有一个是正确的，请在正确的地方画“”。 （1）它是由一个根和两株互不相交的、称为左

21、子树和右子树的二叉树组成。 （2）（a）在一株二叉树的级i上，最大结点数是2i-1（i1） （b）在一棵深度为k的二叉树中，最大结点数是2k-1+1 （k1）。 （3）二叉树是结点的集合，满足如下条件： （a）它或者是空集； （b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 【中科院自动化所1995一、2（6分）】,答案为： （3）,填空题,深度为k的完全二叉树至少有_(1)_个结点，至多有_(2)_个结点。 【厦门大学 2001 一、4 （5分）】 【南京理工大学 1999 二、5 （4分）】,答案为： （1） 2k-1 （2） 2k-1,填空题,深度为H 的完全二叉树

22、至少有_(1)_个结点；至多有_(2)_个结点；H和结点总数N之间的关系是 (3)_。 【中科院计算所1998 一、3（3分）1999 二、4（3分）】 【中国科技大学 1998 一、3(4分）】,答案为： （1）2H-1 （2）2H-1 （3）H = log2N +1,填空题,含4个度为2的结点和5个叶子结点的二叉树，可有_个度为1的结点。 【北京工业大学 2001 一、6 (2分)】,答案为： 0 至多个。 任意二叉树，度为1的结点个数没有限制。只有完全二叉树，度为1的结点个数才至多为1,选择题,一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） 【西安交通大学 1996 三、2

23、 (3分)】 A 250 B 500 C254 D505 E以上答案都不对,答案为： E 由二叉树的结点公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1,因为n1001，所以10022n0n1，在完全二叉树中，n1只能取1或0，在本题中只能取0（否则就是小数了），所以n0501,作业,6.16.8,6.2.3 二叉树的存储结构,顺序存储结构 链式存储结构,二叉树的顺序存储结构,整个二叉树可以按照从上到下，从左到右的顺序排序，做标号； 对于满/完全二叉树，可以从根结点开始按序号存放 对于一般的二叉树，可以参照满二叉树的编码方法进行编码，位置空的结点空置。,#define M

24、AX_TREE_SIZE 100 /二叉树的最大结点数 Typedef TElemType SqBiTreeMAX_TREE_SIZE; /零号单元存储根结点 SqBiTree bt；,0 1 2 3 4 5 6 7 8 9 10 11 12 13,顺序存储结构举例,完全二叉树,顺序存储结构举例,非完全二叉树,X,仅适用于完全二叉树,二叉树的链式存储结构,二叉链表 3. 双亲链表 2. 三叉链表 4. 线索链表,二叉树的链式存储结构,二叉链表 三叉链表,链式存储结构示例,二叉链表,三叉链表,二叉链表的C表示,二叉树的二叉链表存储表示 typedef struct BinNode ElemTyp

25、e data; struct BinNode *lchild, *rchild;左右孩子指针 BinTNode,*BinTree;,三叉链表的C表示,二叉树的三叉链表存储表示 typedef struct TriNode ElemType data; struct TriNode *lchild, *rchild;左右孩子指针 struct TriNode *parent；/双亲指针 TriTNode,*TriTree;,二叉树的双亲链表表示,Typedef struct BPTNode TElemType data； int *parent; /指向双亲的指针 char LRflag；/左、

26、右孩子标志 BPTNode Typedef struct BPTree BPTNode nodesMAX_TREE_SIZE; int num_node; /结点数目 int root; /根结点的位置 BPTree;,0 1 2 3,root=0 num_node=4,作业,6.31,6.2.4 二叉树的遍历,一、 问题的提出 二、 先左后右的遍历算法 三、 算法的递归描述 四、 中序遍历算法的非递归描述 五、 遍历算法的应用举例,一、 问题的提出,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息等。,“遍历”是任

27、何类型都有的操作。对线性结构而言，只有一条搜索路径（因为每个结点均只有一个后继），故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径： 先上后下的按层次遍历； 先左（子树）后右（子树）的遍历； 先右（子树）后左（子树）的遍历；,2. 先左（子树）后右（子树）的遍历；,二、 先左后右的遍历算法,先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法,二叉树的遍历,前序遍历二叉树 中序遍历二叉树 后序遍历二叉树,使得非线性结构二叉树的结点能够排列在一个线性序列上,如果规定从左到右和从右到左的遍历

28、顺序，则有6种，这三种是从左到右的遍历,三种遍历操作中，都首先判别二叉树是否为空树，如果是则执行空操作。,遍历图例,中序序列为：DBEACF,前序序列为：ABDECF,后序序列为：DEBFCA,三、 算法的递归描述,前、中、后序的递归遍历算法,中序遍历二叉树的递归算法,InOrderTraverse(BinTree T) /中序遍历二叉树的递归算法 if(T) 二叉树非空 InOrderTraverse(Tlchild);中序遍历左子树 print(Tdata);访问根结点 InOrderTraverse(T-rchild); 中序遍历右子树 if InOrderTraverse,图例,对每个

29、结点均途径了三次，去掉三种遍历中与递归无关的print语句，则三种遍历算法完全相同。,中序遍历二叉树,结果为DBEACF,课堂练习：写出三种遍历序列,前序：ABDEFCG 中序： DFEBAGC 后序： FEDBGCA,前序：ABCDEF 中序： CBEFDA 后序： CFEDBA,填空题,已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是_。 【青岛大学2000 六、3(2分）】,答案为： DGEBFCA,四、 中序遍历算法的非递归描述,设S为一个栈，p为指向根结点的指针， 其处理过程为： （1）当p非空时，将p所指结点的地址进栈，并将p指向该结点的左子树； （2）当p为空时

30、，弹出栈顶元素并访问之，并将p指向该结点的右子树； （3）重复（1）、（2）步骤，直到栈空且p 也为空。,教材p.107.,InOrderTraverse(BinTree T) 中序遍历二叉树的非递归算法 BinTree p, sM; p=T;i=0; do while(p!=NULL) 树非空，根结点进栈 si+=p; p=p-lchild; 指向P的左孩子 if(i0) p=si- -; printf(p-data); 访问结点 p=p-rchild; 指向右孩子 while(i0|p!=NULL); InOrderTraverse,非递归遍历算法,与教材p.107.描述不同,非递归中序遍

31、历栈S的变化,结束,教材p.107.,作业,6.9, 6.16, 6.18,五、遍历算法的应用举例,统计二叉树中叶子结点的个数（先序遍历） 叶子结点的左、右子树均为空； 分析问题：三种情况： 1): 空树：叶子结点个数为零； 2): 只有一个根结点，叶子数目为1； 3): 叶子结点的个数等于其左子树上的叶子数加上右子树上的叶子数；,统计二叉树中叶子结点的个数,void CountLeaf(BitTree T, int /if ,T指向二叉树的根结点,count为变参，初值为0,五、遍历算法的应用举例,求二叉树的深度（后序遍历） 分析二叉树深度的定义：叶子结点的最大的层次数。 二叉树为空：深度为

32、0； 二叉树只有一个根结点：深度为1； 一般的二叉树：左子树的深度为d1，右子树的深度为d2，则树的深度为：depth=maxd1,d2+1,求二叉树的深度（后序遍历）,int Depth(BitTree T) / 求二叉树的深度 if (!T) return 0; else DepthLeft=Depth(T-lchild); DepthRight=Depth(T-rchild); depthval=1+(DepthLeft DepthRight ? DepthLeft:DepthRight); return depthval; /if ,只能采用后序遍历的方法，因为只有求得了左、右子树的深

33、度后才能求得二叉树的深度,教材p.122.算法6.14,五、遍历算法的应用举例,3. 复制二叉树,newleftT,newrightT,复制二叉树,BitTree Copy(BitTree T) /复制二叉树 BitTree bt; if (T=NULL) bt=NULL; else bt=(BitTree)malloc(sizeof(BiTNode); bt-data=T-data; bt-lchild=Copy(T-lchild); bt-rchild=Copy(T-rchild); /else return(bt); /Copy,基于前序遍历,五、遍历算法的应用举例,4. 建立二叉树 C

34、reatBinTree(BinTree T) 按前序构造二叉链表表示的二叉树T scanf( 生成左子树 if CreatBinTree,利用二叉树的遍历可以实现二叉树的许多操作，如生成结点、建立二叉树,建立二叉树,如建立如下二叉树：,则按前序读入字符序列为： ABD E C F ,其中的为空格符,五、遍历算法的应用举例,5. 由二叉树的先序和中序序列建树 例如：已知二叉树的先序序列为：abcd 则可得到几棵不同的二叉树：,中序为：abcd,中序为：badc,中序为：acdb,不能由先序得到一棵惟一的二叉树,可由先序和中序得到一棵惟一的二叉树,五、遍历算法的应用举例,5. 由二叉树的先序和中序

35、序列建树 例如：已知二叉树的 先序序列：abcdefg 中序序列：cdbaegf 分析可得：根结点是a； 左子树是bcd 右子树是egf,*由二叉树的先序和中序序列建树算法,设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre1.n 和mid1.n 中，该算法建立该二叉树的二叉链表。 void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2) /根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一个和最后一个元素下标。 root=(BiTree)malloc(sizeof(B

36、iNode); /申请结点 root-data=prel1; /prel1是根 for(i=l2;ilchild=null; /无左子树 else PreInCreat(root-lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； /递归建立左子树 if(i=h2) root-rchild=null; /无右子树 else PreInCreat(root-rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) /递归建立右子树 /结束PreInCreat,教材p.124.算法6.18,选择题,对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其

37、左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 【北京理工大学 2000 一、4 （2分）】 A 先序 B. 中序 C. 后序 D. 从根开始按层次遍历,答案为： C,选择题,已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。 ACBEFDA B FEDCBA C CBEDFA D 不定 【浙江大学 1999 四、2 ( 4分)】,答案为： A,选择题,已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 Aacbed Bdecab Cdeabc

38、 Dcedba 【山东大学 2001 二、7 ( 1分)】,答案为： D,选择题,某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2， ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 【长沙铁道学院1998三、1(2分)】,答案为： B,选择题,下面的说法中正确的是（ ）. （1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A(1)(

39、2) B(1) C(2) D(1)、(2)都错 【南京理工大学 2001 一、10 （1.5分）】,答案为： B 三个结点的二叉树有5种,选择题,对于前序遍历与中序遍历结果相同的二叉树为（1）; 对于前序遍历和后序遍历结果相同的二叉树为（2）。 【中科院计算所 1999 一、4 （4分）】 A一般二叉树 B只有根结点的二叉树 C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树,答案为： （1） F （2） B,选择题,某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 【武汉大学2000二、4】 A空或只有一个结点

40、B任一结点无左子树 C高度等于其结点数 D任一结点无右子树,答案为： C 包括左、右单枝树,判断题,由一棵二叉树的前序序列和后序序列可以唯一确定它。 【中科院软件所 1997 一、3 （1分）】,答案为： 错 如：左单支树和右单支树的情况,判断题,非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 【合肥工业大学 2001 二、5 （1分）】,答案为： 对,中序序列为：debfac 如c的中序前驱a无右孩子,填空题,在二叉树中，指针p所指结点为叶子结点的条件是_。 【合肥工业大学1999 三、7（2分）】,答案为： plchild=null struct BiThrNode *

41、lchild, *rchild; 左、右孩子指针 int ltag, rtag; /线索 BinThrNode， *BinThrTree,/二叉树的二叉线索链表,二、线索链表的遍历算法,由于有了前驱和后继等信息，所以遍历就不需要用到栈了； 可以用下列循环实现其遍历； for (p=firstNode(T); p; p=succ(p) visit(p);,即从第一个结点开始依次访问该结点和其后继结点，一直到后继为空。,中序线索化链表的遍历算法,中序遍历的第一个结点？ 在中序线索化链表中结点的后继？,中序线索化链表的遍历算法,中序遍历的第一个结点？ 从根结点出发，沿着左子树一直找到没有左子树的结点

42、。,中序线索化链表的遍历算法,NULL,中序遍历的第一个结点是 D,中序线索化链表的遍历算法,在中序线索化链表中结点的后继？,在中序线索二叉树上找后继,以中序线索二叉树为例查找后继 分为两种情况： 情况1：结点p的右子树为空，则p的右链域为右线索，直接指示了其后继；,a) P的右子树为空,在中序线索二叉树上找后继,以中序线索二叉树为例查找后继 分为两种情况： 情况2：结点p的右子树不为空，则右链为指针，根据中序遍历的规律，结点的中序后继必定是其右子树中第一个遍历到的结点，即从p的右子树开始，沿左指针链向下查找，直到找到一个没有左子树的结点为止，该结点就是p的右子树中的最左下结点，即为p的中序后

43、继结点。,b) P的右子树不空,a) P的右子树为空,b) P的右子树不空,在中序线索树上查找后继时的两种情况,在中序线索二叉树上找后继算法实现,InorderNext(BiThrTree p) 在中序线索二叉树中找结点p的中序后继结点 BiThrTrree q; if (p-rtag=1) /结点的右子树为空 return(p-rchild)/ 结点的右指针域为右线索，指向其后继 else q=p-rchild;/p结点的右子树中最左边的结点是p结点的 中序后继 while(!(q-ltag) q=q-lchild; return(q); /if InorderNext,线索二叉树的遍历,I

44、norderTraverseThr(BiThrTree p) 中序遍历中序线索二叉树p while(p) /二叉树非空 while(p-ltag=0) p=p-lchild; /找中序序列的开始结点，即沿左孩子向下 printf(p-data); while(p /转向右子树 /while / InorderTraverseThr,时间复杂度为O(n) 但是不需要栈,教材p.111.算法6.8,在中序线索二叉树上找前驱算法,以中序线索二叉树为例查找前驱 分为两种情况： 情况1：若p的左孩子为空，则左指针域为左线索且直接指向其前驱结点；,P的前驱,a) P的左子树为空,在中序线索二叉树上找前驱算

45、法,以中序线索二叉树为例查找前驱 分为两种情况： 情况2：若p的左孩子不为空，则从p的左子树开始，沿右指针链向下查找，直到找到一个没有右子树的结点为止，即该结点为p的左子树中的最右下的结点，即是p的中序前驱结点。,P的前驱,在中序线索二叉树上找前驱算法实现,InorderPre(BiThrTree p) 在中序线索二叉树中找结点p的中序前驱结点 BiThrTree q; if (p-ltag=1) /结点的左子树为空 return(p-lchild)/ 结点的左指针域为左线索，指向其前驱 else q=p-lchild);/p结点的左子树中最右边的结点是p结点的 中序前驱 while(!(q-

46、rtag) q=q-rchild; return(q); /if InorderPre,关于中序线索二叉树,结论： 在中序线索二叉树上找前驱和后继都非常容易,后序线索二叉树上找前驱和后继,找前驱： 若结点有右子女，则右子女是其前驱；否则，lchild指向其前驱。,E为B的前驱，即是它的右孩子,D为B的前驱，即是它的左孩子,找后继： 困难，需要知道其双亲。 这种情况下，线索对于查找指定结点的后序后继用途并不大。,E为B的前驱，即是它的右孩子,D为B的前驱，即是它的左孩子,后序后继线索二叉树,前序线索二叉树上找前驱和后继,找前驱： 困难 找后继： 若结点有左子女，则左子女是后继；否则，rchild

47、指向后继。 请见教材p.111. 讨论,选择题,一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定 【合肥工业大学 2000 一、5 （2分）】,答案为：B,因为第一个结点为根结点，无前驱指针或线索，最后一个结点无后继（空链域）,线索二叉树的插入和删除,在二叉树上插入和删除结点时，都会破坏线索，这样一来，除了修改结点指针外，还必须相应地修改线索，与非线索二叉树相比，时间消耗大。 具体讨论略去。,三、如何建立线索链表,中序线索化二叉树 按某种顺序将二叉树线索化，实质上就是将二叉树中的空指针改为指向其前驱和后继的线索。在按该次序遍历

48、二叉树的过程中修改指针，用线索取代空指针即可。假设一个指针 pre 始终指向刚刚访问过的结点，而指针 p 指示当前正在访问的结点，则：*pre 是*p的前驱，*p是*pre的后继。,教材p.109.,中序线索化二叉树,在中序线索化算法中，访问当前结点*p所做的处理是： 若结点*p有空指针域，则将其相应线索标志置为1； 若结点*p的前驱*pre不为空，分为以下两种情况： 若*pre的右线索标志为1，令pre的右指针为指向中序后继结点*p的右线索； 若*p的左线索标志为1，令p的左指针为指向中序前驱结点*pre的左线索； 将pre指向刚刚访问过的结点*p,BiThrTree pre=null; v

49、oid InOrderThreat(BiThrTree p) 对二叉树进行递归中序线索化 if(p) InOrderThreat(p-lchild); 左子树中序线索化 if(p-lchild=null) p-ltag=1; p-lchild=pre; 左线索为pre if(pre!=null 右子树中序线索化 if InOrderThreat,教材p.109.算法6.6,中序线索化二叉树算法,中序线索化二叉树算法,void InorderThread(BiThrTree p) /中序遍历二叉树T，并将其中序线索化 if (p) 初始时，p指向根结点 T,pre的初值为NULL Inorder

50、Thread (p-lchild); 左子树线索化 if (!p-lchild) p-ltag=1 建立左线索标志 if (!p-rchild) p-rtag=1 建立右线索标志 if (pre) if (pre-rtag= =1) pre-rchild=p; pre的右线索指向*p if (p-ltag= =1) p-lchild=pre; p的左线索指向*pre if pre=p; InorderThread (p-rchild) 右子树线索化 if InorderThread,旧教材p.117.,选择题,引入二叉线索树的目的是（ ） A加快查找结点的前驱或后继的速度 B为了能在二叉树中方

51、便的进行插入与删除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一 【南京理工大学1998 一、5 （2分）】,答案为： A,选择题,n个结点的线索二叉树上含有的线索数为（ ） A2n Bnl Cnl Dn 【中山大学 1998 二、8 （2分）】,答案为： C,判断题,在中序线索二叉树中，每一非空的左线索均指向其祖先结点。 【合肥工业大学 2000 二、5 （1分）】,答案为： 对,判断题,二叉树中序线索化后，不存在空指针域。【青岛大学 2000 四、3 （1分）】,答案为： 错,填空题,线索二元树的左线索指向其_，右线索指向其_。 【哈尔滨工业大学 2000 二、3 (2分)】,答案为：

52、 前驱 后继,作业,6.16, 6.18, 6.19, 6.20, 6.23, 6.28, 6.32 6.40, 6.41, 6.43,6.4 树和森林的表示方法,树的存储结构 考虑存储结构时，主要考虑逻辑结构 数据元素 数据元素之间的关系 树的存储结构： 主要采用链式存储结构,树的存储结构,1. 双亲表示法,2. 孩子链表表示法,3. 树的二叉链表（孩子兄弟）表示法,1. 双亲表示法,一个静态数组，存放所有的结点 数组的每个数据元素，包括两部分：数据元素，整数表示该结点的双亲结点在数组中的位置；根结点的整数为-1。 特点： 方便找结点的双亲； 是一种静态链表，但是采用顺序存储结构；,任意一个

53、结点的双亲只有一个,双亲表示法类型定义,#define MAX_NODE 64 typedef struct Pnode ElemType data; 数据域 int parent; 双亲位置域 Ptnode； typedef struct Ptnode nodesMAX_NODE; int r,n; /根结点的位置和结点个数 Ptree;,双亲表示示例,便于找某结点的双亲和祖先。 找孩子结点需要遍历整个表,r=0 n=9,2. 孩子链表表示法,任一数据元素，有0个或多个孩子； 因此可以设计一个链式存储结构，其结点除放置数据元素外，还可以放置若干指针，分别用来指示该结点的所有孩子结点在存储空间

54、中的位置。,孩子链表表示法,方法1（链结点同构方式） 根据结点的度，设置结点的指针个数，比如若结点的度为d:,孩子链表表示法,方法1（链结点同构方式） 根据结点的度，设置结点的指针个数，比如若结点的度为d:,问题： 因degree为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间。 有n个结点的树的度为k，空指针域有n(k-1)+1个空链域,孩子链表表示法,有n个结点的树的度为k，空指针域有n(k-1)+1个空链域 证明： n个结点的树，除根结点外，每个结点有一个双亲，也就是树中有n-1个分支，即有n-1个链域（指针） 而按该结点定义，n个结点总的指针域有：nk个。 因此

55、空链域： nk (n-1) = n ( k - 1 ) + 1,孩子链表表示法,方法2 按照树的度定义结点。若树的度为d, 定义degree，表示该结点的度,孩子链表表示法,方法2 按照树的度定义结点。若树的度为d, 定义degree，表示该结点的度,问题： 不同的数据元素，结点构造不同； 操作不方便,一个静态数组，存放所有的结点 数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表，链表结点的数据域是一个整数，表示该结点的孩子在数组中的位置； 特点： 顺序+链式存储结构； 找孩子容易，找双亲难；,孩子链表表示法 之改进,孩子链表表示法之改进,树的孩子表示法的孩子链表表示法,孩子链

56、表表示法类型定义,typedef struct Ctnode 孩子结点 int child; struct Ctnode *next; *childlink; typedef struct 头结点 ElemType data; childlink firstchild; CTBox; CTBox nodesMAX_NODE；/树的孩子链表 存储表示,双亲孩子链表,在静态数组的结点增加一个域，表示该结点的双亲在该树组中的位置。 有利于寻找双亲结点。,树的孩子表示法的双亲孩子链表表示法,3. 孩子兄弟表示法,从向下的纵向和横向描述树； 考虑定义结点，除放数据元素外，放两个指针，一个指向该结点的第一

57、个孩子，另一个指向该结点的下一个兄弟；,二叉树的表示方法,孩子兄弟表示法,typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSLNode,*CSTree; 该表示方法又称二叉树表示法，或二叉链表表示法,孩子兄弟表示法,易于找孩子结点,若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。因此，在使用该存储结构下，树和二叉树是等价的，只是解释不同而已。 树转化为二叉树。,树和二叉树的转换,步骤 （1）连线：在所有的兄弟结点之间加一条连线。 （2）切线：对于每个结点，除了保留与其最左孩子的连线外，去掉该结点与其它孩子之间的连线。 （3）旋转：将按（1）、（2）的方法形成的二叉树，沿顺时针方向旋转450,就可以得到一棵形式上更为清楚的二叉树。,树和二叉树转化例,树转化为二叉树,树转换成的二叉树没有右子树,连线,切线