数据结构二叉树1第第6 6章章 二叉树和树二叉树和树数据结构二叉树2【重点掌握重点掌握】：1.二叉树的结构特性二叉树的结构特性;2.二叉树的各种存储结构的特点及适用范围二叉树的各种存储结构的特点及适用范围;3.二叉树各种遍历策略的递归算法，且能灵活运用遍历算二叉树各种遍历策略的递归算法，且能灵活运用遍历算法实现二叉树的其它操作；法实现二叉树的其它操作；4.最优二叉树的特性，建立最优树和哈夫曼编码的方法最优二叉树的特性，建立最优树和哈夫曼编码的方法掌掌 握握】：1.线索二叉树的建立、使用；线索二叉树的建立、使用；2.树的各种存储结构及其特点；树的各种存储结构及其特点；3.树、森林与二叉树之间的转换；树、森林与二叉树之间的转换；4.树、森林的遍历树、森林的遍历数据结构二叉树3 线性结构线性结构的特点是逻辑结构简单，易于进行查找、删除、插入等操的特点是逻辑结构简单，易于进行查找、删除、插入等操作其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描作其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述非线性结构非线性结构是指在该结构中至少存在一个数据元素有两个或两个以是指在该结构中至少存在一个数据元素有两个或两个以上的直接前驱或直接后继。
上的直接前驱或直接后继树形结构树形结构是一类重要的非线性结构树形结构是结点之间有分支、是一类重要的非线性结构树形结构是结点之间有分支、并且具有并且具有层次关系层次关系的结构，它非常类似于自然界中的树树结构在客观的结构，它非常类似于自然界中的树树结构在客观世界是大量存在的，例如世界是大量存在的，例如家谱家谱、行政组织机构行政组织机构都可用树形象地表示树都可用树形象地表示树在计算机领域中也有着广泛的应用，例如在在计算机领域中也有着广泛的应用，例如在编译程序编译程序中，用树来表示源中，用树来表示源程序的语法结构；在程序的语法结构；在数据库系统数据库系统中，可用树来组织信息；在中，可用树来组织信息；在分析算法分析算法的的行为时，可用树来描述其执行过程等等行为时，可用树来描述其执行过程等等图形结构图形结构是十分重要的非线性结构，可以用来描述客观世界中广泛是十分重要的非线性结构，可以用来描述客观世界中广泛存在的网状结构的关系存在的网状结构的关系数据结构二叉树46.1 6.1 二叉树二叉树6.1.2 6.1.2 二叉树的基本概念二叉树的基本概念1.1.二叉树二叉树(Binary Tree)(Binary Tree)(1)(1)定义：二叉树是定义：二叉树是n n（n=0n=0）个数据元素的集合，该集合或为空，或个数据元素的集合，该集合或为空，或含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为左子树和右子树。
子集自身也是一棵二叉树，分别称为左子树和右子树说明说明:1 1）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念2 2）二叉树中每个结点最多有两棵子树）二叉树中每个结点最多有两棵子树,二叉树每个结点度小于等于二叉树每个结点度小于等于2 2ABCDEFG数据结构二叉树53 3）左、右子树不能颠例）左、右子树不能颠例 二叉树结点的子树要区分左子树和右子树：二叉树结点的子树要区分左子树和右子树：即使只有一棵子树也要即使只有一棵子树也要进行区分，说明它是左子树，还是右子树这是二叉树与树的最主要进行区分，说明它是左子树，还是右子树这是二叉树与树的最主要的差别ABAB两棵不同的二叉树两棵不同的二叉树(2)(2)二叉树的二叉树的 5 5 种基本形态种基本形态空二叉树空二叉树根和空的根和空的左右子树左右子树根和左子树根和左子树根和右子树根和右子树 根和左右子树根和左右子树数据结构二叉树62.2.二叉树的基本术语二叉树的基本术语 1)孩子孩子(child)(child)：结点的子树的根称为该结点的孩子；左孩子，右孩子：结点的子树的根称为该结点的孩子；左孩子，右孩子。
2)2)双亲双亲(parents)(parents)：孩子结点的上层结点孩子结点的上层结点3)3)兄弟兄弟(sibling)(sibling)：同一双亲的孩子结点；堂兄弟、祖先结点、子孙：同一双亲的孩子结点；堂兄弟、祖先结点、子孙结点结点 4)4)叶子叶子(leaf)(leaf)：终端结点，左右子树均为空的结点；反之，分支结点：终端结点，左右子树均为空的结点；反之，分支结点5)5)结点的度结点的度(degree)(degree)：结点拥有的子树数结点拥有的子树数6)6)二叉树的度：二叉树的度：树中最大的结点度树中最大的结点度7)7)结点层结点层(level)(level)：从根结点开始算起，根为第一层；根的孩子为第：从根结点开始算起，根为第一层；根的孩子为第2 2层结点；层结点；8 8）二叉树的深度）二叉树的深度(depth)(depth)：二叉树中叶子结点的最大层次数二叉树中叶子结点的最大层次数数据结构二叉树7二叉树的基本性质二叉树的基本性质性质性质1 1：一棵非空二叉树的第一棵非空二叉树的第i i层上最多有层上最多有2 2i-1i-1个结点（个结点（i1i1）数据结构二叉树8性质性质2 2：一棵深度为一棵深度为k k的二叉树中，最多有的二叉树中，最多有2 2k k-1-1个结点（个结点（k1)k1)。
深度为深度为k k的二叉树取最多结点时，二叉树中的每层上均应取最多结的二叉树取最多结点时，二叉树中的每层上均应取最多结点根据性质点根据性质1 1得到每层上的最大结点数为得到每层上的最大结点数为2 2i-1i-1，则二叉树中的总结点，则二叉树中的总结点数为：数为：20+2 1+2 k-1=2k-14 2 3 1 6 7 8 9101112131415 5此树的深度此树的深度k=4k=4，共有，共有2 24 4-1=15-1=15个结点个结点数据结构二叉树9性质性质3 3：对于非空二叉树，如果叶子结点数为对于非空二叉树，如果叶子结点数为n n0 0，度为，度为2 2的结点数为的结点数为n n2 2，则有则有n n0 0=n=n2 2+1+1证明：设二叉树中度为证明：设二叉树中度为1 1的结点数为的结点数为n n1 1，二叉树中总结点数为，二叉树中总结点数为N N，因为二，因为二叉树中所有结点均小于或等于叉树中所有结点均小于或等于2 2，所以有：，所以有：N Nn n0 0n n1 1n n2 2 (6-1)(6-1)再看二叉树中的分支数，除根结点外，其余结点都由一个分支与其再看二叉树中的分支数，除根结点外，其余结点都由一个分支与其双亲相连接，设双亲相连接，设B B为二叉树中的分支总数，则有：为二叉树中的分支总数，则有：N NB B1 1 （6-2)6-2)由于这些分支都是由度为由于这些分支都是由度为1 1和和2 2的结点射出的，所以有：的结点射出的，所以有：B Bn n1 1+2+2*n n2 2 （6-3)6-3)即：即：N NB B1 1n n1 12 2n n2 21 1 由式（由式（6-16-1）得到：）得到：n n0 0+n+n1 1+n+n2 2=n=n1 1+2+2*n n2 2+1+1 即：即：n n0 0n n2 21 1n n0 0=3=3n n2 2=2=2ABCDEFG数据结构二叉树10 两种特殊的二叉树两种特殊的二叉树(1)(1)满二叉树满二叉树：如果深度为：如果深度为k k的二叉树有的二叉树有2 2k k-1-1个结点，则称为满二叉树。
个结点，则称为满二叉树特点：每一层上都含有最大结点数特点：每一层上都含有最大结点数k=4k=4的满二叉树的满二叉树 423167891011121314155数据结构二叉树11（2 2）完全二叉树完全二叉树：如果二叉树除最后一层外每一层都是满的，且最后一：如果二叉树除最后一层外每一层都是满的，且最后一层或者是满的，或者结点都连续地集中在该层的最左端，则称其为完全二层或者是满的，或者结点都连续地集中在该层的最左端，则称其为完全二叉树123114589126710特点：特点：1)1)所有的叶子结点都出现在第所有的叶子结点都出现在第k k层或层或k-1k-1层层;2)2)对任一结点，如果其右子树的最大层次为对任一结点，如果其右子树的最大层次为L L，则其左子树的最，则其左子树的最 大层次为大层次为L L或或L+1L+1数据结构二叉树12123456 非完全二叉树非完全二叉树123114589121367101415满二叉树（完全二叉树满二叉树（完全二叉树)123114589126710 完全二叉树完全二叉树1234567 非完全二叉树非完全二叉树数据结构二叉树13性质性质4 4：具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：loglog2 2n+1n+1。
符号符号x x 表示不大于表示不大于x x的最大整数）的最大整数）4231678542316789 10 11 12 13 14 155n2k-1n2k-1 2k-1n2k-1 取对数得到：k-1log2n1i1，则其双亲，则其双亲是结点是结点i/2i/2 ；（2 2）如果）如果2in2in，则其左孩子是结点，则其左孩子是结点2i2i；否则；否则i i无左孩子、为叶子结无左孩子、为叶子结点；点；（3 3）如果）如果2i+1n2i+1n，则其右孩子是结点，则其右孩子是结点2i2i1 1；否则结点；否则结点i i无右孩子无右孩子ABCDEFG1234568D7数据结构二叉树156.2 6.2 二叉树的存储结构二叉树的存储结构 1.1.顺序存储结构顺序存储结构 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的结点一般是按照从上至下、从左至右的顺序存储但是，这样存储后结点一般是按照从上至下、从左至右的顺序存储但是，这样存储后结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接关系关系，只有通过一些方法能够确定结点在逻辑上的前驱和后继结点，这，只有通过一些方法能够确定结点在逻辑上的前驱和后继结点，这种存储才有意义。
种存储才有意义1)(1)完全二叉树的顺序存储完全二叉树的顺序存储 完全二叉树按照这种编号方式时，所有结点编号时连续的；完全二叉树按照这种编号方式时，所有结点编号时连续的；，这，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系所以比较适合于采用顺序结点在二叉树中的位置以及结点之间的关系所以比较适合于采用顺序存储方式存储方式数据结构二叉树16若父结点在数组中若父结点在数组中 i 下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处；处；结点结点i的双亲是的双亲是 i/2i/2例如下完全二叉树：例如下完全二叉树：数据结构二叉树17(2)(2)一般二叉树的顺序存储一般二叉树的顺序存储 对于一般二叉树，如果仍按从上至下、从左至右的顺序将树中的对于一般二叉树，如果仍按从上至下、从左至右的顺序将树中的结点顺序地存储在一维数组中可，则数组元素下标之间的关系不能反结点顺序地存储在一维数组中可，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系，只有映二叉树中结点之间的逻辑关系，只有，使其成为一棵完全二叉树，再用一维数组存储。
使其成为一棵完全二叉树，再用一维数组存储1111ABCFED 1 1 2 2 4 4 8 8 9 91010 5 5 6 6 3 3 7 71514131211109876543210FE000DC0BA0 表示该处没有元素存在表示该处没有元素存在数据结构二叉树18 这种存储方式对于需增加结点才能将一棵二叉树改造成一棵完全二这种存储方式对于需增加结点才能将一棵二叉树改造成一棵完全二叉树的存储时叉树的存储时,会造成空间的大量浪费，不宜采取顺序结构最坏的情况会造成空间的大量浪费，不宜采取顺序结构最坏的情况是单支树是单支树ABDCABDC 数据结构二叉树192.2.链式存储结构链式存储结构 用链表来表示一棵二叉树，即用链来指示元素的逻辑关系用链表来表示一棵二叉树，即用链来指示元素的逻辑关系1 1）二叉链表）二叉链表 链表中每个结点包含三个域，除数据域外，还有两个指针域，分别用链表中每个结点包含三个域，除数据域外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的结点的存储地址来给出该结点的左孩子和右孩子所在的结点的存储地址结点的存储结构为：结点的存储结构为：lchilddatarchild结点存储结构的描述：结点存储结构的描述：typedef struct BiTNode datatype data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;数据结构二叉树20ABCDEFG在在n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空指针域。
个空指针域AB C D E F G数据结构二叉树21(2)(2)三叉链表存储结构三叉链表存储结构 三叉链表中每个结点由三叉链表中每个结点由4 4个域组成：个域组成：、rchilddatalchildparent 域为指向该结点双亲结点的指针域为指向该结点双亲结点的指针这种结构既便于查找孩子结点，又便于查找双亲结点；但是，相这种结构既便于查找孩子结点，又便于查找双亲结点；但是，相对二叉链表而言它增加了空间开销对二叉链表而言它增加了空间开销尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序结构还节结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序结构还节省空间因此，省空间因此，是最常用的二叉树存储方式是最常用的二叉树存储方式数据结构二叉树22ABCDEFG A B C D E F G三叉链表示意图三叉链表示意图数据结构二叉树236.2 6.2 二叉树的遍历二叉树的遍历6.2.1 6.2.1 二叉树的遍历算法及递归实现二叉树的遍历算法及递归实现 遍历：按某种搜索路径访问二叉树的每个结点，使每个结点被访问一遍历：按某种搜索路径访问二叉树的每个结点，使每个结点被访问一次且仅被访问一次。
次且仅被访问一次遍历是二叉树经常要用到的一种操作因为在实际应用问题中，常要遍历是二叉树经常要用到的一种操作因为在实际应用问题中，常要按一定次序对二叉树中的每个结点做逐一访问，或查找具有某个特点的按一定次序对二叉树中的每个结点做逐一访问，或查找具有某个特点的结点，然后对这些满足条件的结点进行处理遍历是各种数据结构最基结点，然后对这些满足条件的结点进行处理遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现本的操作，许多其他的操作可以在遍历基础上实现访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据结点数据如何访问二叉树，如何访问二叉树，使每个结点仅被访问一次？使每个结点仅被访问一次？数据结构二叉树24 由二叉树的定义可知，一棵二叉树是由根结点、根结点的左子树、根由二叉树的定义可知，一棵二叉树是由根结点、根结点的左子树、根结点的右子树三部分组成因此，只要依次遍历这三部分，就可以遍历整结点的右子树三部分组成因此，只要依次遍历这三部分，就可以遍历整个二叉树个二叉树二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树。
二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L：遍历左子树：遍历左子树 D：访问根结点：访问根结点 R：遍历右子树：遍历右子树 有六种遍历方法：有六种遍历方法：DLR，LDR，LRD，DRL，RDL，RLD 约定先左后右约定先左后右,有三种遍历方法：有三种遍历方法：DLR、LDR、LRD ，分别称为，分别称为先序遍历、中序遍历、后序遍历先序遍历、中序遍历、后序遍历DLRLDR、LRD、DLRRDL、RLD、DRL数据结构二叉树25 1.1.先序遍历（先序遍历（DLR）若二叉树空，遍历结束否则，若二叉树空，遍历结束否则，（1 1）访问根结点；）访问根结点；（2 2）先序遍历根结点的左子树；）先序遍历根结点的左子树；（3 3）先序遍历根结点的右子树；）先序遍历根结点的右子树；先序遍历序列为：先序遍历序列为：A,B,D,E,G,C,F例：先序遍历右图所示的二叉树例：先序遍历右图所示的二叉树 （1 1）访问根结点）访问根结点A （2 2）先序遍历）先序遍历A的左子树：即按的左子树：即按DLR顺序遍历顺序遍历A的左子树的左子树 （3 3）先序遍历）先序遍历A的右子树：即按的右子树：即按DLR顺序遍历顺序遍历A的右子树的右子树ABCDEFG数据结构二叉树26ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历过程示例:数据结构二叉树27void PreOrder(BiTree T)/采用二叉链表结构，采用二叉链表结构，visit()是访问结点的函数是访问结点的函数 if(T)/若若T=NULL时时,递归调用结束递归调用结束visit(T)；/访问根结点访问根结点PreOrder(T-lchild);/先序遍历左子树先序遍历左子树PreOrder(T-rchild);/先序遍历右子树先序遍历右子树 先序遍历递归算法先序遍历递归算法 对于根结点，最简单的对于根结点，最简单的“访问访问”是输出处理是输出处理。
数据结构二叉树28例例.求二叉树中的叶子结点数求二叉树中的叶子结点数需要对二叉树中的每个结点都进行判断需要对二叉树中的每个结点都进行判断 借用遍历算法（如：先序遍历算法）借用遍历算法（如：先序遍历算法）方法：当访问到某个结点时，进行是否是叶子结点的判断；方法：当访问到某个结点时，进行是否是叶子结点的判断；如果是叶子结点，则将计数器加如果是叶子结点，则将计数器加1 1看先序遍历算法看先序遍历算法数据结构二叉树29 应用遍历算法求二叉树中的叶子结点数应用遍历算法求二叉树中的叶子结点数void PreOder(BiTree T)if (T)Visit(T)；PreOrder(T-lchild);PreOrder(T-rchild);本算法中的本算法中的访问是什么？访问是什么？判断判断T是否为叶子结点是否为叶子结点T-lchilid=NULL&T-rchild=NULL是叶子结点则计数器加是叶子结点则计数器加1N+;数据结构二叉树30void PreOder(BiTree T)if (T)Visit(T)；PreOrder(T-lchild);PreOrder(T-rchild);void PreOder(BiTree T)if (T)if(T-lchilid=NULL&T-rchild=NULL)N+;PreOrder(T-lchild);PreOrder(T-rchild);可以为函数可以为函数换个名字换个名字（见名知义）（见名知义）数据结构二叉树31void Countleaf(BiTree T)if(T)if(T-lchild=NULL&T-rchild=NULL)N+;/*若若T为叶子，则累加为叶子，则累加*/Countleaf(T-lchild);/*统计左子树中的叶子统计左子树中的叶子*/Countleaf(T-rchild);/*统计右子树中的叶子统计右子树中的叶子*/调用前调用前N的初值的初值为为0数据结构二叉树32void Countleaf(BiTree T)if(T)if(T-lchild=NULL&T-rchild=NULL)N+;/*若若T为叶子，则累加为叶子，则累加*/Countleaf(T-lchild);/*统计左子树中的叶子统计左子树中的叶子*/Countleaf(T-rchild);/*统计右子树中的叶子统计右子树中的叶子*/int N=0;main()BiTree T;/*建立二叉链表结构*/Countleaf(T);printf(“the numbers of leaf:%d n”,N);数据结构二叉树332.2.中序遍历（中序遍历（LDR）若二叉树为空，遍历结束。
否则，若二叉树为空，遍历结束否则，（1 1）中序遍历根结点的左子树）中序遍历根结点的左子树（2 2）访问根结点）访问根结点（3 3）中序遍历根结点的右子树）中序遍历根结点的右子树 中序遍历序列：中序遍历序列：D,B,G,E,A,C,F例：中序遍历右图所示的二叉树：例：中序遍历右图所示的二叉树：（1 1）中序遍历）中序遍历A的左子树：即按的左子树：即按LDR的顺序遍历的顺序遍历A的左子树的左子树 （2 2）访问根结点）访问根结点A （3 3）中序遍历）中序遍历A的右子树：即按的右子树：即按LDR的顺序遍历的顺序遍历A的右子树的右子树ABCDEFG问题问题：如何确定中序遍历过程中的第一个结点：如何确定中序遍历过程中的第一个结点?从根结点向左子树查找，第一个左子树为空的结点从根结点向左子树查找，第一个左子树为空的结点数据结构二叉树34 void InOrder(BiTree T)if(T=NULL)return;/*递归遍历结束递归遍历结束*/InOrder(T-lchild);/*中序遍历中序遍历T的左子树的左子树*/Visit(T-data)；/*访问根结点访问根结点*/InOrder(T-rchild);/*中序遍历中序遍历T的右子树的右子树*/中序遍历递归算法：中序遍历递归算法：数据结构二叉树35ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历过程示例中序遍历过程示例:数据结构二叉树363.3.后序遍历（后序遍历（LRD）若二叉树为空，则遍历结束。
否则，若二叉树为空，则遍历结束否则，（1 1）后序遍历根结点的左子树）后序遍历根结点的左子树（2 2）后序遍历根结点的右子树）后序遍历根结点的右子树（3 3）访问根结点）访问根结点 后序遍历序列：后序遍历序列：G,D,B,E,F,C,A例：后序遍历右图所示的二叉树例：后序遍历右图所示的二叉树 （1 1）后序遍历）后序遍历A的左子树：即按的左子树：即按LRD的顺序遍历的顺序遍历A的左子树的左子树 （2 2）后序遍历）后序遍历A的右子树：即按的右子树：即按LRD的顺序遍历的顺序遍历A的右子树的右子树 （3 3）访问根结点）访问根结点A问题：问题：如何确定后序遍历过程中的第一个结点如何确定后序遍历过程中的第一个结点?从根结点向左子树查找，找到第一个左子树为空的结点，接着向右子树从根结点向左子树查找，找到第一个左子树为空的结点，接着向右子树找，至一叶子结点找，至一叶子结点ABEFDGC数据结构二叉树37void PostOrder(BiTree T)if(T=NULL)return;PostOrder(T-lchild);PostOrder(T-rchild);Visit(T-data);后序遍历递归算法：后序遍历递归算法：数据结构二叉树38ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C A后序遍历过程示例后序遍历过程示例:B数据结构二叉树396.2.2 6.2.2 由遍历序列恢复二叉树由遍历序列恢复二叉树 任意一棵二叉树结点的先序序列和中序序列都是惟一的。
反过任意一棵二叉树结点的先序序列和中序序列都是惟一的反过来，若已知结点的先序序列和中序序列，也能惟一地确定这棵二叉树来，若已知结点的先序序列和中序序列，也能惟一地确定这棵二叉树在先序序列中，第一个结点一定是二叉树的根结点在先序序列中，第一个结点一定是二叉树的根结点 中序序列必然以根为界分割成两个子序列，前一个子序列是根结点中序序列必然以根为界分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列 在先序序列中，左子序列的第一个结点是左子树的根结点，右子序在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列中的第一个结点是右子树的根结点列中的第一个结点是右子树的根结点 左子树和右子树的根结点又在中序序列中分别把左子序列和右子序左子树和右子树的根结点又在中序序列中分别把左子序列和右子序列划分成两个子序列列划分成两个子序列 ，如此递归下去，当取尽先序序列中的结点时，便可以得到一，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树棵二叉树先序序列先序序列中序序列中序序列数据结构二叉树40例：已知一棵二叉树的先序序列和中序序列分别为例：已知一棵二叉树的先序序列和中序序列分别为:先序序列：先序序列：ABCDEFGHI 中序序列：中序序列：BCAEDGHFI 试恢复该二叉树。
试恢复该二叉树A先：先：BC中：中：BC先：先：DEFGHI中：中：EDGHFIABDCE先：先：FGHI中：中：GHFIABDCEF先：先：GH中：中：GHIABDCEFIGH数据结构二叉树41二叉树中的所有结点二叉树中的所有结点 借用遍历算法借用遍历算法 问题问题1：使用哪种遍历算法？：使用哪种遍历算法？先序遍历算法先序遍历算法 问题问题2：“访问访问”所对应的运算是什么？所对应的运算是什么？建立该结点（分配存储空间），对其赋值建立该结点（分配存储空间），对其赋值例例1 1】建立二叉树的存储结构建立二叉树的存储结构-二叉链表二叉链表6.2.3 遍历算法的应用数据结构二叉树42方法：方法：输入先序序列（在空子树处添加字符输入先序序列（在空子树处添加字符#），按先序遍历），按先序遍历的顺序，在遍历过程中建立二叉链表的所有结点并完成相应的顺序，在遍历过程中建立二叉链表的所有结点并完成相应结点的链接结点的链接输入序列：输入序列：A B D#F#C E#AFEDCB*数据结构二叉树43BiTree CreatBiTree(BiTree&T)/在先序遍历二叉树过程中输入结点字符在先序遍历二叉树过程中输入结点字符,建立二叉建立二叉链表存储结构链表存储结构 /指针指针T指向所建二叉树的根结点指向所建二叉树的根结点 cinch;if(ch=#)T=NULL;/建空树建空树 else T=new BiTNode;/生成根结点生成根结点 T-data=ch;CreatBiTree(T-lchild);/构造左子树构造左子树CreatBiTree(T-rchild);/构造右子树构造右子树 ADBC输入序列：输入序列：A B#D#C#数据结构二叉树44 通常，一个表达式由一个运算符和两个操作数构成。
通常，一个表达式由一个运算符和两个操作数构成即，表达式即，表达式=(=(第一操作数第一操作数)()(运算符运算符)()(第二操作数第二操作数)其中，操作数本身也可以是表达式其中，操作数本身也可以是表达式 其结构类似于二叉树，因此可以用二叉树表示表达式（递归）其结构类似于二叉树，因此可以用二叉树表示表达式（递归）运算符：根结点；运算符：根结点；第一操作数第一操作数：L L；第二操作数第二操作数：R R 表达式求值过程：后序遍历表达式二叉树表达式求值过程：后序遍历表达式二叉树 【例例2 2】求存于二叉树中算数表达式的值求存于二叉树中算数表达式的值数据结构二叉树456.2.4 线索二叉树线索二叉树遍历具有重要性遍历具有重要性遍历存在的问题遍历存在的问题（建立线索二叉树的必要性）建立线索二叉树的必要性）(1)遍历将二叉树中所有结点排成一个线性序列，但每个结遍历将二叉树中所有结点排成一个线性序列，但每个结点在这个序列中的前驱和后继结点并没有直接在二叉点在这个序列中的前驱和后继结点并没有直接在二叉树的存储结构中反映出来；只能在对二叉树遍历的动树的存储结构中反映出来；只能在对二叉树遍历的动态过程中得到这些信息。
态过程中得到这些信息2)用递归的方式、利用栈或队列对二叉树遍历，都会存在用递归的方式、利用栈或队列对二叉树遍历，都会存在栈或队列的额外空间的消耗栈或队列的额外空间的消耗为了提高遍历的效率，保存结点在某种遍历序列中的为了提高遍历的效率，保存结点在某种遍历序列中的前驱和后继的位置信息，利用二叉树的二叉链表存储结构前驱和后继的位置信息，利用二叉树的二叉链表存储结构建立线索二叉树建立线索二叉树数据结构二叉树46线索二叉树的定义线索二叉树的定义（1 1）前驱和后继：前驱和后继：在二叉树的先序、中序或后序遍在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱和后继历序列中两个相邻的结点互称为前驱和后继2 2）线索：线索：指向前驱或后继结点的指针指向前驱或后继结点的指针3 3）线索二叉树：线索二叉树：加上线索的二叉链表表示的二叉加上线索的二叉链表表示的二叉树4 4）线索化：线索化：对二叉树按某种遍历次序使其变为线对二叉树按某种遍历次序使其变为线索二叉树的过程索二叉树的过程数据结构二叉树47方法：索二叉树的结点中增加两个域方法：索二叉树的结点中增加两个域ltag lchild data rchild rtag 0 lchild 域指示结点的左孩子域指示结点的左孩子 1 lchild 域指示结点的前驱域指示结点的前驱 0 rchild 域指示结点的右孩子域指示结点的右孩子 1 rchild 域指示结点的后驱域指示结点的后驱 rtag=ltag=数据结构二叉树48索二叉链表上增加头结点索二叉链表上增加头结点目的：为了将二叉树中的所有空指针域都利用上，以及目的：为了将二叉树中的所有空指针域都利用上，以及操作便利的需要，在存储线索二叉树时往往增设一头操作便利的需要，在存储线索二叉树时往往增设一头结点，其结构与其他线索二叉树的结点结构相同，只结点，其结构与其他线索二叉树的结点结构相同，只是其数据域不存储信息。
是其数据域不存储信息。