[ppt模板]Ch_6 树和二叉树

1、1知识回顾知识回顾线性表 一般的线性表 特殊的线性表：栈、队列线性表的扩展：数组、广义表特点：有序前趋、后继2第六章第六章 树和二叉树树和二叉树树是以分支关系定义的层次结构。树是以分支关系定义的层次结构。树结构在客观世界广泛存在树结构在客观世界广泛存在: : 在自然科学，如地理学领域，水系、地貌（等高线）、行政区划等都具有树结构关系； 在社会人文领域，人类社会构成、组织机构等也具有树结构关系。树型结构：树型结构：非线性数据结构非线性数据结构4要求要求1. 熟练掌握二叉树的结构特性。熟练掌握二叉树的结构特性。2. 熟悉二叉树的各种存储结构的特点及适用范围。熟悉二叉树的各种存储结构的特点及适用范围

2、。3. 掌握各种遍历策略的递归算法，灵活运用遍历算法实掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。现二叉树的其它操作。4. 熟练掌握二叉树的线索化过程以及在中序线索化树上熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。找给定结点的前驱和后继的方法。5. 熟悉树的各种存储结构及其特点，掌握树和森林与二熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。叉树的转换方法。6. 了解最优树的特性，掌握建立最优树和哈夫曼编码的了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。方法。6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6

3、.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.5 6.5 赫夫曼树与其应用赫夫曼树与其应用主要内容66.1.1 6.1.1 树的定义树的定义树（树（tree）是）是n (n0)个结点的有限集。在任意一棵个结点的有限集。在任意一棵非非空树空树中：中：（1）有且仅有一个特定的称为）有且仅有一个特定的称为根根的结点；的结点；（2）当）当n1时，其余结点可分为时，其余结点可分为m (m0)个互不相交个互不相交的有限集的有限集t1,t2,tm，其中每一个集合本身又是一棵，其中每一个集合本身又是一棵树，并且称为根的树，并且称为根的子树子树

4、。a只有根结点的树abcdefghijklm有子树的树根子树树的表示法树的表示法v 图形表示法图形表示法v 嵌套集合表示法嵌套集合表示法v 广义表表示法广义表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法教师教师学生学生其他人员其他人员20012001级级 20022002级级 20032003级级20042004级级西安石油大学西安石油大学计算机系计算机系电信系电信系自控系自控系叶子叶子根根子树子树( a ( b ( e ( k, l ), f ), c ( g ), d ( h ( m ), i, j ) ) 约定：约定：根根作为由子树森林组成的作为由子树森林组成的

5、表的名字写在表的左边表的名字写在表的左边又称目录表示法又称目录表示法data左孩子左孩子 右兄弟右兄弟多叉树转为多叉树转为了二叉树了二叉树15数据对象数据对象 d：d是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若d为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在d中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集t1, t2, , tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为

6、根root的子树。的子树。 数据关系数据关系 r：adt tree16 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类17 root(t) / 求树的根结点求树的根结点 查找类：查找类：value(t, cur_e) / 求当前结点的元素值求当前结点的元素值 parent(t, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点leftchild(t, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 rightsibling(t, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟treeempty(t) / 判定树是否为空树判定树是否为空树 t

7、reedepth(t) / 求树的深度求树的深度traversetree( t, visit() ) / 遍历遍历18inittree(&t) / 初始化置空树初始化置空树 插入类：插入类：createtree(&t, definition) / 按定义构造树按定义构造树assign(t, cur_e, value) / 给当前结点赋值给当前结点赋值insertchild(&t, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树19 cleartree(&t) / 将树清空将树清空 删除类：删除类：destr

8、oytree(&t) / 销毁树的结构销毁树的结构deletechild(&t, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树20abcdefghijmkla( b(e, f(k, l), c(g), d(h, i, j(m) )t1t3t2树根例如例如: :21() 有确定的根；() 树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。22对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前

9、驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点6.1.2 6.1.2 基本术语基本术语25结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素+ +若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点

10、dhijm26子孙子孙: :以某结点为根的子树中的任一结点。以某结点为根的子树中的任一结点。abcdefghijmkl孩子孩子: :结点的子树的根。结点的子树的根。双亲双亲: :该结点称为孩子的双亲。该结点称为孩子的双亲。兄弟兄弟: :同一个双亲的孩子之间互称兄弟。同一个双亲的孩子之间互称兄弟。祖先祖先: :从根到该结点所经分支上的所有结点从根到该结点所经分支上的所有结点27有序树：有序树：子树之间存在确定的次序关系子树之间存在确定的次序关系无序树：无序树：子树之间不存在确定的次序关系子树之间不存在确定的次序关系树的深度：树的深度：树中结点的最大层次树中结点的最大层次堂兄弟堂兄弟: :其双亲在

11、同一层的结点其双亲在同一层的结点结点的层次结点的层次:假设根结点的层次为假设根结点的层次为1，第，第l 层的结点的子树根结点的层次为层的结点的子树根结点的层次为l+128a ab bc cd de ef fg gh hi ij jk kl lm m结点结点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的层次：的层次：1结点结点m的层次

12、：的层次：4树的深度：树的深度：4结点结点f，g为堂兄弟为堂兄弟29任何一棵非空树是一个二元组 tree = （root，f）其中：root 被称为根结点 f 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合arootbcdefghijmklf先研究最简单、最有规律的树，然先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。后设法把一般的树转化为简单树。解决思路：解决思路： 树的操作实现比较复杂。树的操作实现比较复杂。为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？ 二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强

13、； 可以证明，所有树都能转为唯一对应的二叉树，可以证明，所有树都能转为唯一对应的二叉树，不失一般性。不失一般性。 二叉树二叉树:或为空树，或是由一个或为空树，或是由一个根根结点结点加上两棵分别称为加上两棵分别称为左子树左子树和和右子右子树树的、的、互不相交互不相交的二叉树组成。的二叉树组成。abcdefghk根结点根结点左子树左子树右子树右子树二叉树的特点二叉树的特点（1 1）每个结点至多有二棵子树）每个结点至多有二棵子树( (即不存在度大于即不存在度大于2 2的结点的结点) )；（2 2）二叉树的子树有左、右之）二叉树的子树有左、右之分，且其次序不能任意颠倒。分，且其次序不能任意颠倒。二叉树

14、的五种基本形态：二叉树的五种基本形态：空树空树只含根结点只含根结点lrr右子树为空树右子树为空树l左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树34 二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类35 root(t); value(t, e); parent(t, e); leftchild(t, e); rightchild(t, e); leftsibling(t, e); rightsibling(t, e); bitreeempty(t); bitreedepth(t); preordertraverse(t, visit();

15、 inordertraverse(t, visit(); postordertraverse(t, visit(); levelordertraverse(t, visit();36 initbitree(&t); assign(t, &e, value); createbitree(&t, definition); insertchild(t, p, lr, c);37clearbitree(&t); destroybitree(&t);deletechild(t, p, lr);38二叉树二叉树的重要特性的重要特性39 性质性质 1 ： 在二叉树的第

16、 i 层上至多有2i-1 个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。40 性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于性质1，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。41 性质性质 3 ： 对任何一棵二叉树，若它含有对任何一棵二叉树，若它含有n0 个叶个叶子

17、结点、子结点、n2 个度为个度为 2 的结点，则必存在的结点，则必存在关系式：关系式：n0 = n2+1。二叉树中全部结点数二叉树中全部结点数nn0+n1+n2(叶子数叶子数1度结度结点数点数2度结点数度结点数)二叉树中全部结点数二叉树中全部结点数nb+1 ( 总分支数根结点总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一（除根结点外，每个结点必有一个直接前趋，即一个分支）个分支）总分支数总分支数b= n1+2n2 (1度结点必有度结点必有1个直接后继，个直接后继，2度结点必有度结点必有2个个)n0+n1+n2= n1+2n2 +1, 即即n0=n2+142两类两类特殊特殊的二

18、叉树：的二叉树：满二叉树满二叉树：深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij43123114589121367101415123114589126710123456712345644完全二叉树特点：完全二叉树特点：（1 1）叶子结点只可能在层次最大的两层上出现）叶子结点只可能在层次最大的两层上出现; ;（2 2）对任一结点，若其右分支下子孙的最大层次为）对任一结点，若其右分支下子孙的最大层次为i i，则其左分支下子孙的最

19、大层次必为则其左分支下子孙的最大层次必为i i或或i+1i+1。满二叉树与完全二叉树的区别满二叉树与完全二叉树的区别满二叉树是叶子一个也不少的树，而完全二叉树虽满二叉树是叶子一个也不少的树，而完全二叉树虽然前然前k-1k-1层是满的，但最底层却允许在右边缺少连续若干层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。个结点。满二叉树是完全二叉树的一个特例。为何要研究这两种特殊形式？为何要研究这两种特殊形式？45性质性质 4 ：具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1 。 x 表示表示= x的最大整数。的最大整数。证明：设

20、完全二叉树的深度为证明：设完全二叉树的深度为 k 则根据第二条性质得则根据第二条性质得 2k-1 (第第k层第一个结点的编号）层第一个结点的编号） n 2k（第（第k1层第一个结点的编号）层第一个结点的编号） 即即 k-1 log2 n = (2k-1-1)+1，根据第二条性质得 n 2k -1，因此：2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。123114589126710第第k层上最后一个结点的编号是层上最后一个结点的编

21、号是2k-1,它的右孩它的右孩子是第子是第k+1层上最后一个结点层上最后一个结点,编号是编号是2k+1-1,右右孩子编号是它的双亲结点编号的孩子编号是它的双亲结点编号的(2k-1)*2+1,左左孩子的编号是孩子的编号是(2k-1)*2所以，编号为所以，编号为 i 的结点的左孩子结点编号是的结点的左孩子结点编号是2i，右孩子结点编号是右孩子结点编号是2i+1,双亲结点编号双亲结点编号 i/2 49问问 题题 具有具有n n个结点的非空二叉树的最小深度个结点的非空二叉树的最小深度是多少？最大深度是多少？是多少？最大深度是多少？ 答1： 当是满二叉树时深度最小。最小深度： log2n +1 当每个节

22、点都只有左（右）子树时深度最大最大深度： n 50思考题1.具有n个结点的完全二叉树中有多少个叶子结点？有多少个度为2的结点？2.具有n0个叶子结点的完全二叉树中共有多少个结点？51二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、 二叉树的顺序二叉树的顺序 存储表示存储表示存储方式：用一组地址连续的存储单元依次存储方式：用一组地址连续的存储单元依次自上而下、自左至右自上而下、自左至右存储存储完全二叉树完全二叉树上的结上的结点元素，即将完全二叉树上编号为点元素，即将完全二叉树上编号为i的结点元的结点元素存储在一维数组中下标为素存储在一维数组中下标为i-1

23、的分量中。的分量中。一、一、 二叉树的顺序存储结构二叉树的顺序存储结构/-二叉树的顺序存储表示二叉树的顺序存储表示-#define max_tree_size 100/ 二叉树的最大结点数二叉树的最大结点数typedef telemtype sqbitreemax_ tree_size; / 0号单元存储根结点号单元存储根结点sqbitree bt;例如例如: :abcdef a b d 0 c 0 e 0 0 0 0 0 0 f 0 1 2 3 4 5 6 7 8 9 10 11 12 1314013260表示不存在此结点完全二叉树的数组表示完全二叉树的数组表示 一般二叉树的数组表示一般二叉

24、树的数组表示55特点：特点： 结点间关系蕴含在其存储位置中，浪费空间，适于结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树（在最坏情况下，深度为存满二叉树和完全二叉树（在最坏情况下，深度为k且只有且只有k个结点的单支树需要长度为个结点的单支树需要长度为2k-1的一维数组）的一维数组）。 由于一般二叉树必须仿照完全二叉树那样存储，可由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。能会浪费很多存储空间，单支树就是一个极端情况。二、二叉树的链式存储结构二、二叉树的链式存储结构（1 1）二叉链表）二叉链表（2）三叉链表三叉链表adebcf r

25、ootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表fabcde在在n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空指针域个空指针域typedef struct bitnode /结点结构结点结构 telemtype data; struct bitnode *lchild, *rchild; / 左右孩子指针 bitnode, *bitree;lchild data rchild结点结构结点结构:c 语言的类型描述如下语言的类型描述如下: :adebcf root 2三叉链表三叉链表parent lchild data rchild结点结

26、构结点结构:abcdef typedef struct tritnode / 结点结构结点结构 telemtype data; struct tritnode *lchild, *rchild; / 左右孩子指针 struct tritnode *parent; /双亲指针 tritnode, *tritree;parent lchild data rchild结点结构结点结构:c 语言的类型描述如下语言的类型描述如下: :二叉链存储结构的二叉树操作实现二叉链存储结构的二叉树操作实现 在二叉链存储结构下，针对一棵二叉树，主要涉及如下几在二叉链存储结构下，针对一棵二叉树，主要涉及如下几个功能模块

27、：个功能模块：v 二叉树的初始化操作；二叉树的初始化操作；v 二叉树中给某结点插入一个左结点的操作；二叉树中给某结点插入一个左结点的操作；v 二叉树中给某结点插入一个右结点的操作；二叉树中给某结点插入一个右结点的操作；v 删除二叉树中某结点的左子树操作；删除二叉树中某结点的左子树操作；v 删除二叉树中某结点的右子树操作。删除二叉树中某结点的右子树操作。 各算法的基本思想及程序实现如下：各算法的基本思想及程序实现如下： typedef structtypedef struct node node datatypedatatype data; data;struct node struct nod

28、e * *leftchildleftchild; ; struct node struct node * *rightchildrightchild; ; bitreenode bitreenode; /; /* *结点的结构体定义结点的结构体定义* */ /1.1.二叉树的初始化二叉树的初始化 算法的基本思想算法的基本思想: :创建二叉树的头结点。创建二叉树的头结点。 程序实现：程序实现： void initiate(bitreenodevoid initiate(bitreenode * * *root)root) * *root = (bitreenode root = (bitreen

29、ode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode););( (* *root)-leftchildroot)-leftchild=null;=null;( (* *root)-rightchildroot)-rightchild=null;=null; 2.2.二叉树中给某结点插入一个左结点的操作二叉树中给某结点插入一个左结点的操作 算法的基本思想算法的基本思想: : 若当前结点若当前结点( (假设为假设为currcurr）非空，在非空，在currcurr的左子的左子树插入元素值为树插入元素值为x x的新结点的新结点 ，原，原c

30、urrcurr所指结点的左所指结点的左子树成为新插入结点的左子树。若插入成功返回新子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回空指针。插入结点的指针，否则返回空指针。程序实现：程序实现： bitreenode bitreenode * *insertleftnode(bitreenode insertleftnode(bitreenode * *curr,datatype x) curr,datatype x) bitreenode bitreenode * *s, s, * *t;t; if(curr if(curr=null) return null;=null)

31、return null;t=curr-leftchildt=curr-leftchild; ;s=(bitreenode s=(bitreenode * *)malloc(sizeof(bitreenode)malloc(sizeof(bitreenode);); s-data=x; s-data=x;s-leftchilds-leftchild=t;=t; s-rightchild s-rightchild=null;=null;curr-leftchildcurr-leftchild=s;=s;return curr-leftchildreturn curr-leftchild; ; 3.

32、3.删除二叉树中某结点的左子树操作删除二叉树中某结点的左子树操作算法的基本思想算法的基本思想: :若若currcurr非空，删除非空，删除currcurr所指结点的左子树。若所指结点的左子树。若删除成功，返回删除结点的双亲结点指针，否则返回空指针。删除成功，返回删除结点的双亲结点指针，否则返回空指针。程序实现程序实现：bitreenode bitreenode * *deletelefttree(bitreenode deletelefttree(bitreenode * *currcurr) ) if(curr=null|curr-leftchildif(curr=null|curr-lef

33、tchild=null)=null) return null; return null;destroy(&curr-leftchilddestroy(&curr-leftchild););curr-leftchildcurr-leftchild=null;=null;return currreturn curr; ; 66知识回顾 树和二叉树的定义 二叉树的特点 二叉树的存储结构676.3.1二叉树的遍历二叉树的遍历68一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中序遍历算法的非递归描述四、中序遍历算法的非递归

34、描述五五、遍历算法的应用举例遍历算法的应用举例69 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。70 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。71 对对“二叉树二叉树”而言，可以有而言，可以有三条搜索路径：三条搜索路径：1先上后下先上后下的按层次遍历；

35、2先左先左（子树）后右后右（子树）的遍历；3先右先右（子树）后左后左（子树）的遍历。72二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法73 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：74 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：75 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍

36、历算法：后（根）序的遍历算法：76adbct l rat l rt l rbdct l r先序遍历序列：先序遍历序列：a b d c先序遍历:77adbcl t rbl t rl t radcl t r中序遍历序列：中序遍历序列：b d a c中序遍历:78adbc l r tl r tl r tadcl r t后序遍历序列：后序遍历序列： d b c a后序遍历:b79-+/a*b-efcd先序遍历：中序遍历：后序遍历：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f80三、算法的递归描述三、算法的递归描述void inordertraverse (

37、bitree t, status(*visit)(telemtype e) / 中中序遍历二叉树序遍历二叉树 if (t) inordertraverse (t-lchild, visit) ;/中中序遍历左子树序遍历左子树 visit(t-data) / 访问根结点访问根结点 inordertraverse (t-rchild, visit);/中序遍历右子树中序遍历右子树 见演示见演示81status inordertraverse(bitree t,status(*visit)(telemtype e)initstack(s); push(s,t); /根指针进栈根指针进栈while(!

38、stackempty(s) while(gettop(s,p)&p) push(s,p-lchild); /向左走到尽头向左走到尽头 pop(s,p); /空指针退栈空指针退栈 if(!stackempty(s) /访问结点访问结点,向右一步向右一步 pop(s,p); visit(p-data); push(s,p-rchild); /if /whilereturn ok;/inordertraverse算法算法1四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述82-b*ca-*anullnullbnullnullcnullnull中序遍历序列:a*b-cwhile(!sta

39、ckempty(s) while(gettop(s,p)&p)push(s,p-lchild); /向左走到尽头向左走到尽头 pop(s,p); /空指针退栈空指针退栈 if(!stackempty(s)/访问结点访问结点,向右一步向右一步 pop(s,p); if(!visit(p-data) return error; push(s,p-rchild); /if83status inordertraverse(bitree t, status (*visit)(telemtype e) initstack(s); p=t; while(p|!stackempty(s) if (p)

40、 push(s,p); p=p-lchild; /根指针进栈根指针进栈, ,遍历左子树遍历左子树 else/根指针退栈根指针退栈,访问根结点访问根结点,遍历右子树遍历右子树 pop(s,p); visit(p-data); p=p-rchild; / else / while return ok;/inordertraverse算法算法2中序遍历算法的非递归描述中序遍历算法的非递归描述84p=t; while(p|!stackempty(s) if (p) push(s,p); p=p-lchild;/根指针进栈根指针进栈,遍历左子树遍历左子树 else/根指针退栈根指针退栈,访问根结点访问根

41、结点,遍历遍历右子树右子树 pop(s,p);if(!visit(p-data)return error; p=p-rchild; / else / while-b*ca-*abc85+*a*/edcb先序遍历结果先序遍历结果+ * * / a b c d e前缀表示法前缀表示法中序遍历结果中序遍历结果a / b * c * d + e中缀表示法中缀表示法后序遍历结果后序遍历结果a b / c * d * e +后缀表示法后缀表示法层次遍历结果层次遍历结果+ * e * d / c a b用二叉树表示算术表达式用二叉树表示算术表达式void layerorder(bitreevoid laye

42、rorder(bitree t) t) /层序遍历二叉树层序遍历二叉树 if (t) if (t) initqueue(q initqueue(q); ); /建一个空队（初始化队列）建一个空队（初始化队列） enqueue(q,tenqueue(q,t); ); /将一个结点插入队尾的函数将一个结点插入队尾的函数 while(while( !queueempty(q!queueempty(q) ) ) ) dequeue(q dequeue(q, &p); , &p); /队首结点出队队首结点出队( (送入送入p)p) visit(p); visit(p); if(p-lch

43、ild) enqueue(q,p-lchild if(p-lchild) enqueue(q,p-lchild); ); /p/p的左孩子入队的左孩子入队 if(p-rchild) enqueue(q,p-rchildif(p-rchild) enqueue(q,p-rchild); ); /p/p的右孩子入队的右孩子入队 /layerorder/layerorder 当孩子为空时不要当孩子为空时不要将空指针入队将空指针入队遍历算法思想的应用-步骤 要明确所要编写的算法的功能描述（包括所涉及的各参数或要明确所要编写的算法的功能描述（包括所涉及的各参数或变量的含义）变量的含义）这在递归算法中尤其

44、要注意。在此基础上这在递归算法中尤其要注意。在此基础上按如下步骤讨论算法的实现：按如下步骤讨论算法的实现：v如果如果t为空，则按预定功能实现对空树的操作，以满足功为空，则按预定功能实现对空树的操作，以满足功能要求（包括对相应参数，变量的操作）。能要求（包括对相应参数，变量的操作）。v否则，假设算法对否则，假设算法对t的左右子树都能分别实现预定功能，的左右子树都能分别实现预定功能，在此基础上，通过按预定要求适当调用对左右子树的算在此基础上，通过按预定要求适当调用对左右子树的算法的功能，及对当前结点的操作实现对整个二叉树的功法的功能，及对当前结点的操作实现对整个二叉树的功能（包括对各变量、参数的操

45、作）。能（包括对各变量、参数的操作）。89例例1 1：统计二叉树中叶子结点的：统计二叉树中叶子结点的个数个数.(.(先序遍历先序遍历) )90算法基本思想算法基本思想: : 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。91void countleaf (bitree t, int& count) if ( t ) if (!t-lchild)& (!t-rchild) count+; / 对叶子结点计

46、数 countleaf( t-lchild, count); countleaf( t-rchild, count); / if / countleaf92例例2 2：求二叉树的深度：求二叉树的深度 ( (后序遍历后序遍历) )93算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右

47、子右子树深度树深度之间的关系。94int depth (bitree t ) / 返回二叉树的深度 if ( !t ) depthval = 0; else depthleft = depth( t-lchild ); depthright= depth( t-rchild ); depthval = 1 + (depthleft depthright ? depthleft : depthright); return depthval;95例例3 3：建立二叉树的存：建立二叉树的存储结构储结构96 以字符串的形式以字符串的形式 根根 左子树左子树 右子树右子树定义一棵二叉树定义一棵二叉树例如

48、:abcd以空白字符“ ”表示a(b( ,c( , ),d( , )空树空树只含一个根结点只含一个根结点的二叉树的二叉树a以字符串“a ”表示以下列字符串表示97status createbitree(bitree &t) scanf(&ch); if (ch= ) t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data = ch; / 生成根结点 createbitree(t-lchild); / 构造左子树 createbitree(t-rchild); / 构造右子

49、树 return ok; / createbitree98a b c d a bcd上页算法执行过程举例如下：atbcdstatus createbitree(bitree &t) scanf(&ch); if (ch= ) t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data = ch; createbitree(t-lchild); createbitree(t-rchild); return ok; 99问题 已知一棵二叉树的先序遍历序列，能否已知一棵二叉树的先序

50、遍历序列，能否得到这棵树？得到这棵树？100例：一棵树的先序序列为：1，2，3。请画出这棵树。101 9可以证明：可以证明：一棵二叉树的先序序列和中一棵二叉树的先序序列和中序序列可以唯一的确定这棵二叉树。序序列可以唯一的确定这棵二叉树。结论结论 仅已知一棵二叉树的先序遍历序列，仅已知一棵二叉树的先序遍历序列，不不能能唯一确定这棵树。唯一确定这棵树。已知一棵二叉树的中序序列和已知一棵二叉树的中序序列和后序序列后序序列分别是分别是bdceafhg bdceafhg 和和 decbhgfadecbhgfa，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序

51、遍历特征，根结点必在后序序列尾部（即（即a a）；由中序遍历特征，根结点必在其中间，而且其左部必由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙全部是左子树的子孙（即（即bdcebdce），其右部必全部是右，其右部必全部是右子树的子孙子树的子孙（即（即fhgfhg）；继而，根据后序中的继而，根据后序中的decbdecb子树可确定子树可确定b b为为a a的左孩子，的左孩子，根据根据hgfhgf子串可确定子串可确定f f为为a a的右孩子；以此类推。的右孩子；以此类推。105106 二叉树的遍历：以一定的次序排列二叉树的结点。-非线性结构的线性化。 传统的二叉链表存储结构只存储了

52、结点的左右孩子的信息，没有存储其前趋和后继信息。 这些信息只有在遍历过程中才能得到。 传统的二叉树遍历方法：-利用堆栈 效率低知识回顾知识回顾107-+/a*b-efcd先序遍历：中序遍历：后序遍历：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f108问题：问题：能否在遍历过程中把结点的能否在遍历过程中把结点的前趋和后继信息保存下来，并且提前趋和后继信息保存下来，并且提高算法的效率呢？高算法的效率呢？1096.3.2线索二叉树线索二叉树threaded binary treethreaded binary tree110主要内容（1）什么是线索二叉树

53、（2）基于线索二叉树的遍历方法（3）如何建立线索二叉树111线索二叉树的引入和定义线索二叉树的引入和定义所以，所以， 空指针数目空指针数目2n(n-1)=n+1个个。证明：证明：用二叉链表存储包含用二叉链表存储包含n n个结点的二叉树，结点必有个结点的二叉树，结点必有2n个链域。个链域。除根结点外，二叉树中每一个结点除根结点外，二叉树中每一个结点有且仅有一个双亲有且仅有一个双亲，即每个结点地址占用了双亲的一个直接后继，即每个结点地址占用了双亲的一个直接后继，n n个结点地址共个结点地址共占用了占用了n-1n-1个双亲的指针域个双亲的指针域。也就是说，只会有。也就是说，只会有n n1 1个结点的

54、个结点的链域存放指针。链域存放指针。用二叉链表法存储包含用二叉链表法存储包含n n个结点的二叉个结点的二叉树，结点的指针区域中会有树，结点的指针区域中会有n+1n+1个空指个空指针。针。112adebcf rootlchild data rchild结点结构结点结构:fabcde113思考：思考：二叉链表空间效率这么低，能否利用二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？这些空闲区存放有用的信息或线索？可以用它来存放当前结点的可以用它来存放当前结点的直接前驱和后直接前驱和后继继等线索，以加快查找速度。等线索，以加快查找速度。这就是这就是（threaded binary tr

55、ee） 对二叉树进行某种遍历之后，将得到一个对二叉树进行某种遍历之后，将得到一个线性有序的序列。线性有序的序列。例如对某二叉树的例如对某二叉树的中序遍历中序遍历结果是结果是b d c e a f h gb d c e a f h g，意味着，意味着已将该树转已将该树转为线性排列，显然其中结点为线性排列，显然其中结点具有唯一前驱和唯具有唯一前驱和唯一后继。一后继。讨论讨论1 1：二叉树是二叉树是1:21:2的非线性结构，如的非线性结构，如何定义其直接后继？何定义其直接后继？先定义遍历规则，然后才能定义先定义遍历规则，然后才能定义直接前驱和后继。直接前驱和后继。115讨论讨论2 2：如何获得这种如

56、何获得这种“直接前驱直接前驱”或或“直接后继直接后继”？有何意义？有何意义？二叉树中容易找到结点的二叉树中容易找到结点的左右孩子左右孩子信息，信息，但该结点的直接前驱和直接后继只能在某种但该结点的直接前驱和直接后继只能在某种遍历过程中遍历过程中动态动态获得。获得。先依先依遍历规则遍历规则把每个结点对应的把每个结点对应的前驱前驱和和后继线索后继线索预存预存起来，这叫做起来，这叫做“线索化线索化”。意义：意义：从从任一结点任一结点出发都能快速找到其出发都能快速找到其前驱和后继，且前驱和后继，且不必借助堆栈。不必借助堆栈。 每个结点增加两个域：每个结点增加两个域：fwd和和bwd；存放前驱指针存放前

57、驱指针存放后继指针存放后继指针如何预存这类信息？如何预存这类信息？ 与原有的左右孩子指针域与原有的左右孩子指针域“复用复用”，充分利用那，充分利用那n+1个空链域。个空链域。规规 定：定：1）若结点有左子树，则）若结点有左子树，则lchild指向其指向其左孩子；否则，左孩子；否则， lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右指向其右孩子；否则，孩子；否则，rchild指向其直接后继指向其直接后继(即即线索线索) 。datalchildrchildfwdbwddatalchildrchild缺点：空间效率太低！缺点：空

58、间效率太低！问题：计算机如何问题：计算机如何判断是孩子指针还判断是孩子指针还是线索指针？是线索指针？如何区别？如何区别？lchildltagdatartag rchild约定约定:当当tag域为域为0时时,表示表示正常正常情况情况;当当tag域为域为1时时,表示表示线索线索情况情况.前驱前驱(后继后继)左左(右右)孩子孩子为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：各各1bit1bit1. 有关线索二叉树的几个术语有关线索二叉树的几个术语 线索链表：线索链表： 线线 索：索：线索二叉树：线索二叉树： 线线 索索 化：化：用用含含tag的结点样式所构成的二叉链表。

59、的结点样式所构成的二叉链表。指向结点前驱和后继的指针。指向结点前驱和后继的指针。在二叉树的结点上加上线索的二叉树。在二叉树的结点上加上线索的二叉树。对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程。叉树的过程。线索化过程就是在遍历过程中修改空指针的过程：线索化过程就是在遍历过程中修改空指针的过程：将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。非空指针仍然指向孩子结点（称为非空指针仍然指向孩子结点（称为“正常情况正常情况”）119typedef struct

60、 bithrnod telemtype data; struct bithrnode *lchild, *rchild; / 左右指针 pointerthr ltag, rtag; / 左右标志 bithrnode, *bithrtree; typedef enum link, thread pointerthr; / link=0:指针，thread=1:线索二叉树的二叉线索存储表示二叉树的二叉线索存储表示在二叉树的线索链表上添加一个头结点，并在二叉树的线索链表上添加一个头结点，并令其令其lchild域域的指针指向二叉树的的指针指向二叉树的根结点根结点，其，其rchild域域的指针指向中序遍历时访问的的指针指向中序遍历时访问的最后一最后一个结点个结点。令二叉树中序序列中的第一个结点的令二叉树中序序列中的第一个结点的lchild域域指针和最后一个结点指针和最后一个结点rchild域域的