第7章树形结构7.1树的基本概念7.1.1树的定义形式化定义：树：T=(K,R)。K是包含n个结点的有穷集合(n>O),关系R满足以下条件(I）有且仅有一个结点kEK,它对于关系R来说没有前驱结点,结点kO称作树的根。(2)除结点kO外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。(3)K中每个结点对于关系R来说可以有多个后继结点。递归定义：树是由n(n≥0)个结点组成的有限集合(记为T)。其中，如果n=0,它是一棵空树,这是树的特例：如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分为m（m>0)个互不相交的有限集T1,T2,",Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。7.1.2树的表示(1）树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。下图就是采用这种表示法。(2）文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。(3）凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。(4）括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。7.1.3树的基本术语1.结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。2.分支结点与叶结点：度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点，其余类推。3.路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,kil,ki2,,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,kil,ki2,",ki)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见，路径就是从ki出发“自上而下”到达ki所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。4.孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点或父母结点)。具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系可以把每个结点的所有子树中的结点称为该结点的子孙结点，从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。5.结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。6.有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。7.森林：n(n>0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之，只要给n棵独立的树加上一个结点，并把这n棵树作43
43 第 7 章 树形结构 7.1 树的基本概念 7.1.1 树的定义 形式化定义： 树：T＝{K,R}。K 是包含 n 个结点的有穷集合(n>0),关系 R 满足以下条件: (1) 有且仅有一个结点 k0∈K,它对于关系 R 来说没有前驱结点,结点 k0 称作树的根。 (2) 除结点 k0 外,K 中的每个结点对于关系 R 来说都有且仅有一个前驱结点。 (3) K 中每个结点对于关系 R 来说可以有多个后继结点。 递归定义： 树是由 n(n≥0)个结点组成的有限集合(记为 T)。其中, 如果 n=0,它是一棵空树,这是树的特例； 如果 n>0,这 n 个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余 结点可分为 m (m>0)个互不相交的有限集 T1,T2,.,Tm,其中每一棵子集本身又是一棵符合 本定义的树,称为根 root 的子树。 7.1.2 树的表示 (1) 树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。 下图就是采用这种表示法。 (2) 文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。 (3) 凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。 (4) 括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗 号间隔来描述树结构。下图是树的括号表示法。 7.1.3 树的基本术语 1. 结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的 度的最大值称为树的度,通常将度为 m 的树称为 m 次树。 2. 分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的 结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度 为 1 的结点,其分支数为 1,被称为单分支结点；对于度为 2 的结点,其分支数为 2,被称为双分 支结点,其余类推。 3. 路径与路径长度：对于任意两个结点 ki 和 kj,若树中存在一个结点序列 ki,ki1,ki2,.,kin,kj, 使得序列中除 ki 外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由 ki 到 kj 的一条路径,用路径所通过的结点序列(ki,ki1,ki2,.,kj)表示这条路径。路径的长度等于 路径所通过的结点数目减 1(即路径上分支数目)。可见,路径就是从 ki 出发“自上而下”到达 kj 所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。 4. 孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点 (或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩 子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结 点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。 5. 结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始 定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所 在的层次加 1。树中结点的最大层次称为树的高度(或树的深度)。 6. 有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对 次序是不能随意变换的,则称为有序树,否则称为无序树。 7. 森林：n(n＞0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只 要把树的根结点删去就成了森林。反之,只要给 n 棵独立的树加上一个结点,并把这 n 棵树作
为该结点的子树，则森林就变成了树。7.1.4树的性质性质1树中的结点数等于所有结点的度数加1。性质2度为m的树中第i层上至多有mi-1个结点,这里应有i≥1。个结点。性质3高度为h的m次树至多有性质4具有n个结点的m次树的最小高度为logm(n(m-1)+1）。7.1.5树的基本运算树的运算主要分为三大类：第一类，寻找满足某种特定关系的结点，如寻找当前结点的双亲结点等；第二类插入或删除某个结点如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；第三类，遍历树中每个结点,这里着重介绍。树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历运算的算法主要有先根遍历和后根遍历两种。注意，下面的先根遍历和后根遍历算法都是递归的。1.先根遍历先根遍历过程为：(1)访问根结点；(2）按照从左到右的次序先根遍历根结点的每一棵子树。2.后根遍历后根遍历过程为：（1）按照从左到右的次序后根遍历根结点的每一棵子树；(2)访问根结点。7.1.6树的存储结构1.双亲存储结构2.孩子链存储结构3.孩子兄弟链存储结构7.2二叉树概念和性质7.2.1二叉树概念二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。在一棵二叉树中如果所有分支结点都有左孩子结点和右孩子结点并且叶结点都集中在二叉树的最下一层这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的结点进行连续编号约定编号从树根为1开始按照层数从小到大、同一层从左到右的次序进行。图中每个结点外边的数字为对该结点的编号。若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个结点进行连续编号，编号的方法同满二叉树相同。图中每个结点外边的数字为对该结点的编号。7.2.2二叉树性质性质1非空二叉树上叶结点数等于双分支结点数加1。证明：设二叉树上叶结点数为nO,单分支结点数为nl,双分支结点数为n2,则总结点数=nO+n1+n2。在一棵二叉树中,所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=nl+2n2。44
44 为该结点的子树,则森林就变成了树。 7.1.4 树的性质 性质 1 树中的结点数等于所有结点的度数加 1。 性质 2 度为 m 的树中第 i 层上至多有 mi-1 个结点,这里应有 i≥1。 性质 3 高度为 h 的 m 次树至多有 个结点。 性质 4 具有 n 个结点的 m 次树的最小高度为 logm(n(m-1)+1) 。 7.1.5 树的基本运算 树的运算主要分为三大类： 第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等； 第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i 个孩子结点等； 第三类,遍历树中每个结点,这里着重介绍。 树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历 运算的算法主要有先根遍历和后根遍历两种。注意,下面的先根遍历和后根遍历算法都是递 归的。 1. 先根遍历 先根遍历过程为： (1) 访问根结点； (2) 按照从左到右的次序先根遍历根结点的每一棵子树。 2. 后根遍历 后根遍历过程为： (1) 按照从左到右的次序后根遍历根结点的每一棵子树； (2) 访问根结点。 7.1.6 树的存储结构 1. 双亲存储结构 2. 孩子链存储结构 3. 孩子兄弟链存储结构 7.2 二叉树概念和性质 7.2.1 二叉树概念 二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个 根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉 树的最下一层,这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树 的结点进行连续编号,约定编号从树根为 1 开始,按照层数从小到大、同一层从左到右的次序 进行。图中每个结点外边的数字为对该结点的编号。 若二叉树中最多只有最下面两层的结点的度数可以小于 2,并且最下面一层的叶结点 都依 次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。如下图所示为一棵完全二 叉树。同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同。图中 每个结点外边的数字为对该结点的编号。 7.2.2 二叉树性质 性质 1 非空二叉树上叶结点数等于双分支结点数加 1。 证明：设二叉树上叶结点数为 n0,单分支结点数为 n1,双分支结点数为 n2,则总结点数 =n0+n1+n2。在一棵二叉树中,所有结点的分支数(即度数)应等于单分支结点数加上双分支结 点数的 2 倍,即总的分支数=n1+2n2
由于二叉树中除根结点以外,每个结点都有惟一的一个分支指向它，因此二叉树中有：总的分支数=总结点数-1。由上述三个等式可得：nl+2n2=n0+nl+n2-1即：nO=n2+1性质2非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。由树的性质2可推出。性质3高度为h的二叉树至多有2h-1个结点(h≥1)。由树的性质3可推出。性质4对完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数有：(1）若i≤n/2，即2i≤n,则编号为i的结点为分支结点,否则为叶子结点。(2)若n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为偶数,则编号最大的分支结点（编号为）只有左孩子结点，没有右孩子结点，其余分支结点都有左、右孩子结点。（3）若编号为i的结点有左孩子结点则左孩子结点的编号为2i：若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+1)。(4）除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为i/2，也就是说当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子结点当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子结点。性质5具有n个(n>0)结点的完全二叉树的高度为log2n+1或log2n+1。由完全二叉树的定义和树的性质3可推出。7.2.3二叉树与树、森林之间的转换1.森林、树转换为二叉树步骤如下：(1）在所有相邻兄弟结点(森林中每棵树的根结点可看成是兄弟结点)之间加一水平连线。(2）对每个非叶结点k,除了其最左边的孩子结点外,删去k与其他孩子结点的连线。（3）所有水平线段以左边结点为轴心顺时针旋转45度。通过以上步骤,原来的森林就转换为一棵二叉树。一般的树是森林中的特殊情况，由一般的树转换的二叉树的根结点的右孩子结点始终为空，原因是一般的树的根结点不存在兄弟结点和相邻的树。将森林转换为二叉树的过程2.二叉树还原为森林、树步骤如下：(1）对于一棵二叉树中任一结点k0,沿着k0的左孩子结点kl的右子树方向搜索所有右孩子结点,即搜索结点序列k2,k3,,km,其中ki+1为ki的右孩子结点(1≤i<m),km没有右孩子结点。(2）删去kl,k2,,km之间连线。(3）若kl有双亲结点k,则连接k与ki(2≤i≤m)。(4)将图形规整化,使各结点按层次排列。将一棵二叉树还原为树的过程7.3二叉树存储结构7.3.1二叉树的顺序存储结构二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号，其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中45
45 由于二叉树中除根结点以外,每个结点都有惟一的一个分支指向它,因此二叉树中有：总 的分支数=总结点数-1。 由上述三个等式可得：n1+2n2=n0+n1+n2-1 即：n0=n2+1 性质 2 非空二叉树上第 i 层上至多有 2i-1 个结点,这里应有 i≥1。 由树的性质 2 可推出。 性质 3 高度为 h 的二叉树至多有 2h-1 个结点(h≥1)。 由树的性质 3 可推出。 性质 4 对完全二叉树中编号为 i 的结点(1≤i≤n,n≥1,n 为结点数)有： (1) 若 i≤ n/2 ,即 2i≤n,则编号为 i 的结点为分支结点,否则为叶子结点。 (2) 若 n 为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若 n 为偶数,则 编号最大的分支结点(编号为)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩 子结点。 (3) 若编号为 i 的结点有左孩子结点,则左孩子结点的编号为 2i；若编号为 i 的结点有右孩子 结点,则右孩子结点的编号为(2i+1)。 (4) 除树根结点外,若一个结点的编号为 i,则它的双亲结点的编号为 i/2 ,也就是说, 当 i 为偶数时,其双亲结点的编号为 i/2,它是双亲结点的左孩子结点,当i 为奇数时,其双亲结点 的编号为(i-1)/2,它是双亲结点的右孩子结点。 性质 5 具有 n 个(n＞0)结点的完全二叉树的高度为 log2n+1 或 log2n +1。 由完全二叉树的定义和树的性质 3 可推出。 7.2.3 二叉树与树、森林之间的转换 1．森林、树转换为二叉树 步骤如下： (1) 在所有相邻兄弟结点(森林中每棵树的根结点可看成是兄弟结点)之间加一水平连 线。 (2) 对每个非叶结点 k,除了其最左边的孩子结点外,删去 k 与其他孩子结点的连线。 (3) 所有水平线段以左边结点为轴心顺时针旋转 45 度。 通过以上步骤,原来的森林就转换为一棵二叉树。一般的树是森林中的特殊情况,由一般的树 转换的二叉树的根结点的右孩子结点始终为空,原因是一般的树的根结点不存在兄弟结点和 相邻的树。 将森林转换为二叉树的过程 2. 二叉树还原为森林、树 步骤如下： (1) 对于一棵二叉树中任一结点 k0,沿着 k0 的左孩子结点 k1 的右子树方向搜索所有 右孩子结点,即搜索结点序列 k2,k3,.,km,其中 ki+1 为 ki 的右孩子结点(1≤i＜m),km 没有右 孩子结点。 (2) 删去 k1,k2,.,km 之间连线。 (3) 若 k1 有双亲结点 k,则连接 k 与 ki(2≤i≤m)。 (4) 将图形规整化,使各结点按层次排列。 将一棵二叉树还原为树的过程 7.3 二叉树存储结构 7.3.1 二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号,其编号 从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中
则该编号就是下标值加1(注意,C/C++语言中数组的起始下标为0)。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。二叉树的链式存储结构7.3.2在二叉树的链接存储中，结点的结构如下：typedef struct node1ElemTypedatastruct node *Ichild,*rchild;BTNode;其中.data表示值域用于存储对应的数据元素，Ichild和rchild分别表示左指针域和右指针域用于分别存储左孩子结点和右孩子结点（即左、右子树的根结点）的存储位置。二叉树及其链式存储结构7.4二叉树的遍历7.4.1二叉树遍历的概念二叉树的遍历是指按照一定次序访问树中所有结点并且每个结点仅被访问一次的过程。它是最基本的运算,是二叉树中所有其他运算的基础。1.先序遍历先序遍历二叉树的过程是：(1）访问根结点；(2）先序遍历左子树；（3）先序遍历右子树。2.中序遍历中序遍历二叉树的过程是：(1）中序遍历左子树：(2）访问根结点：(3）中序遍历右子树。3.后序遍历后序遍历二叉树的过程是：（1）后序遍历左子树：(2）后序遍历右子树：（3）访问根结点。2二叉树遍历递归算法7.4.2由二叉树的三种遍历过程直接得到如下三种递归算法如下：voidPreOrder(BTNode*b)/*先序遍历的递归算法*/if (b!=NULL)1printf("%c",b->data);/*访问根结点*/PreOrder(b->lchild);PreOrder(b->rchild);3/*中序遍历的递归算法*/void InOrder(BTNode *b)1if(bl=NULL)(InOrder(b->lchild);46
46 则该编号就是下标值加 1(注意,C/C++语言中数组的起始下标为 0)。树中各结点的编号与等 高度的完全二叉树中对应位置上结点的编号相同。 7.3.2 二叉树的链式存储结构 在二叉树的链接存储中,结点的结构如下: typedef struct node { ElemType data; struct node *lchild,*rchild; } BTNode; 其中,data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指 针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置。 二叉树及其链式存储结构 7.4 二叉树的遍历 7.4.1 二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的 过程。它是最基本的运算,是二叉树中所有其他运算的基础。 1. 先序遍历 先序遍历二叉树的过程是： (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。 2. 中序遍历 中序遍历二叉树的过程是： (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 3. 后序遍历 后序遍历二叉树的过程是： (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 7.4.2 二叉树遍历递归算法 由二叉树的三种遍历过程直接得到如下三种递归算法如下： void PreOrder(BTNode *b) /*先序遍历的递归算法*/ { if (b!=NULL) { printf("%c ",b->data); /*访问根结点*/ PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b) /*中序遍历的递归算法*/ { if (b!=NULL) { InOrder(b->lchild);
printf("%c",b->data);/*访问根结点*InOrder(b->rchild);3voidPostOrder(BTNode*b)/*后序遍历递归算法*1if (bl=NULL)PostOrder(b->lchild);PostOrder(b->rchild):printf("%c",b->data);/*访间根结点*/37.4.33二叉树遍历非递归算法1.先序遍历非递归算法（1）第一种方法（2）第二种方法（常规方法）2.中序遍历非递归算法（2）第二种方法（常规方法）由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描（并非访问）根结点的所有左结点并将它们一一进栈。然后出栈一个结点，显然该结点没有左孩子结点或者左孩子结点已访问过（进一步说明该结点的左子树均已访问），则访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此这样，直到栈空为止。3.后序遍历非递归算法（2）第二种方法（常规方法）由后遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点并一一进栈，出栈一个结点*b即当前结点，然后扫描该结点的右孩子结点并入栈，再扫描该右孩子结点的所有左结点并入栈。当一个结点的左右孩子结点均访问后再访问该结点，如此这样，直到栈空为止。7.5二叉树的基本运算及其实现7.5.1二叉树的基本运算概述归纳起来二叉树有以下基本运算：(1)创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。(2)查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。(3)找孩子结点LchildNode(p)和RchildNode(p)：分别求二叉树中结点*p的左孩子结点和右孩子结点。(4)求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为O：否则,其高度等于左子树与右子树中的最大高度加1。(5)输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。7.5.2二叉树的基本运算算法实现(1)创建二叉树CreateBTNode(*b,*str)用ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况：47
47 printf("%c ",b->data); /*访问根结点*/ InOrder(b->rchild); } } void PostOrder(BTNode *b) /*后序遍历递归算法*/ { if (b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); printf("%c ",b->data); /*访问根结点*/ } } 7.4.3 二叉树遍历非递归算法 1. 先序遍历非递归算法 （1）第一种方法 （2）第二种方法（常规方法） 2. 中序遍历非递归算法 （2）第二种方法（常规方法） 由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描（并非访问）根 结点的所有左结点并将它们一一进栈。 然后出栈一个结点，显然该结点没有左孩子结点或者左孩子结点已访问过（进一步 说明该结点的左子树均已访问），则访问它。然后扫描该结点的右孩子结点，将其进栈，再 扫描该右孩子结点的所有左结点并一一进栈，如此这样，直到栈空为止。 3. 后序遍历非递归算法 （2）第二种方法（常规方法） 由后遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所有左 结点并一一进栈，出栈一个结点*b 即当前结点，然后扫描该结点的右孩子结点并入栈，再 扫描该右孩子结点的所有左结点并入栈。当一个结点的左右孩子结点均访问后再访问该结 点，如此这样，直到栈空为止。 7.5 二叉树的基本运算及其实现 7.5.1 二叉树的基本运算概述 归纳起来,二叉树有以下基本运算： (1)创建二叉树 CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str 生成对 应的链式存储结构。 (2)查找结点 FindNode(*b,x)：在二叉树 b 中寻找 data 域值为 x 的结点,并返回指向该 结点的指针。 (3)找孩子结点 LchildNode(p)和 RchildNode(p)：分别求二叉树中结点*p 的左孩子结 点和右孩子结点。 (4)求高度 BTNodeDepth(*b)：求二叉树 b 的高度。若二叉树为空,则其高度为 0；否则,其高 度等于左子树与右子树中的最大高度加 l。 (5)输出二叉树 DispBTNode(*b)：以括号表示法输出一棵二叉树。 7.5.2 二叉树的基本运算算法实现 (1) 创建二叉树 CreateBTNode(*b,*str) 用 ch 扫描采用括号表示法表示二叉树的字符串。分以下几种情况：