数据结构与算法设计（第二版）课件 6章 树与二叉树

第六章树与二叉树西安科技大学计算机学院张小艳数据结构与算法设计

族谱就是一个家族所有人员构成的大名单，是一个用血缘联系起来的系统。通过绘制家谱树，记录家族成员的相互关系。

家谱树，是一种描绘家庭关系的树状结构图，树中的每个成员可以清楚的知道自己的家族起源、家族关系以及其他成员的基础信息。

通过家谱，可使子孙后辈知悉祖先的渊源、人口、迁徙、分布、名人传略、故事传说、先贤史迹等等。通过家谱，可激励子孙后辈传承家族美德，发扬优良传统，赓续家族源流。

要记得自己来自于哪里？根在哪里？爱父母、爱自己的家，热爱我们的大家-中国，我们拥有一个强大的国家，无论走到哪里，我们的根永远在中国。引例

家谱族谱系统把每一个成员都视为系统的一个要素，他们按照“祖—父—子—孙”的关系构成了树状结构。引例

家谱族谱系统引例

组织架构在树中，我们把数据元素称之为结点数据元素的关系层次分明，A第一层、BCD在的二层、EFGHIJ在第三层、KLM在第四层。树及二叉树--基本概念T3第一层第二层第三层第四层根结点结点A为树T的根结点，除根结点A之外的其余结点分为三个不相交的集合：T1T2抽象透过现象看本质类似于线性表，我们把树定义为一个二元组：

Tree=（D,R）

其中：D是具有相同特性的数据元素的集合；R是关系集合。

如果D=NULL,称这棵树为空树；

如果D只包含一个数据元素，则R为空集；树及二叉树--基本概念否则：关系描述R定义为：(1)在D中存在唯一的一个特殊的元素称为树的根结点root，根结点root没有前驱结点。(2)若D-{root}！=NULL，D-{root}=D1∪D2∪…∪Dm，D1∩D2∩…∩Dm=∮

对于任意一个Di,ti∈Di,<root,ti>∈R，root就有m个直接后继。(3)对应集合D1，D2，…，Dm，有R1,R2,…，Rm个关系，其中每一组二元组Ti=（Di,Ri）又是一棵满足上述定义的树。树T1，T2，…，Tm称为这个根结点root的子树。透过现象看本质森林:是零棵或多棵树组成的集合。树也可定义为：

n(n≥0)个结点的有限集，

若n=0，则为空树；

否则，树由一个根结点和m(m≥0)棵树组成的森林构成。

森林中的每棵树都是根的子树。树及二叉树--基本概念具有下面两个特点：(1)树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。(2)树中所有结点可以有零个或多个后继结点。树及二叉树--基本概念1）关于结点的概念根结点B、C、D是A的儿子结点A是B、C、D的双亲结点B、C、D互为兄弟B有两个儿子EFF是叶子结点度不为零的结点称为分支结点F和G之间是堂兄弟关系结点A的度就是三拥有子树的个数就是该结点的度。树中各个结点度的最大值称为这棵树的度度为0的结点称为叶结点度不为0的结点称为分支结点，或者称为非终端结点，A,B,C,DE,H是分支结点2）结点的层数及树的深度树及二叉树--基本概念结点在树中的层数约定为：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。若某个结点的层次为k，则其孩子结点的层次为k+1。树中叶结点的最大层次数定义为树的深度。如果一棵树的一串结点n1,n2,…,nk，如果结点ni是ni+1的双亲结点(1≤i＜k)，就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。树分：有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，这棵树就是有序树；反之，则称为无序树。结点的层数及树的深度结点在树中的层数约定为：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。树中叶结点的最大层次数定义为树的深度。如果一棵树的一串结点n1,n2,…,nk，如果结点ni是ni+1的双亲结点(1≤i＜k)，就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。K

B

C

D

E

F

G

H

I

J

A

L

M

第一层第二层第三层第四层A、B、E是K、L、F的祖先A、C是G的祖先，反之，称以A为根的树中所有结点是A的子孙树及二叉树--基本概念树分：有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，这棵树就是有序树；反之，则称为无序树。树及二叉树--基本概念6-2二叉树基本概念二叉树是另一种树形结构，可以简单理解二叉树就是每个结点最多有两棵子树的有序树。图中的二叉树含有10个结点，DACBGEFHIJ其中A是根，左子树TL由{C，B，G}构成，右子树TR由{D，E，F，H，J，I}构成；左子树TL中，C是根结点，TL的左子树为空，TL的右子树由{B，G}构成；右子树TR中，D是根结点，TR的左子树由{E，H}构成，TR的右子树由{F，J，I}构成，以此类推。二叉树的特点每个结点最多有两棵子树，且互不相交；左子树和右子树是有顺序的，次序不能颠倒。因此二叉树具有五种基本形态：左子树右子树左子树右子树(a)(b)(c)(d)(e)满二叉树和完全二叉树满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称做满二叉树。123456789101112131415(a)一颗满二叉树1234567891011(b)一颗非满二叉树满二叉树的三个特点123456789101112131415叶子只能出现在最下一层。非叶子结点的度一定是2。在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多。

从满二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号(1，2，…，n)。

图中的满二叉树的编号是(1到15)。

完全二叉树：一棵深度为k，有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i(1≤i≤n)的结点与深度为k的满二叉树中，编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。12345678910满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

一棵深度为4的完全二叉树。深度为4的拥有结点最多的完全二叉树123456789101112131415深度为4的拥有结点最少的完全二叉树（a）12345678（b）完全二叉树特点：叶子结点只能出现在最下两层。最下层的叶子一定集中在左部连续位置。倒数第二层若有叶子结点，一定都在右部连续位置。如果结点度为1，则该结点只有左孩子，即不存在只有右孩子的情况。同样结点数的二叉树，完全二叉树的深度最小。性质1：一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。通过数学归纳法论证，可以很容易得出第i层上至多有2i-1个结点。二叉树--五条性质20 = 122-1 = 223-1 = 424-1 = 820 = 1

性质2：一棵深度为k的二叉树中，最多具有2k-1个结点。

证明：深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加。

二叉树--五条性质

性质3：对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有n0 = n2 + 1。证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点数，那么就有n = n0 + n1 + n2(6-1)设B为二叉树中的分支数，那么有B = n - 1(6-2)

B = n1 + 2n2(6-3)综合式(6-1)、(6-2)、(6-3)可以得到：可以得到：n0 = n2 + 1

二叉树--五条性质性质4：具有n个结点的完全二叉树的深度k为。根据性质2，深度为k的二叉树最多的节点数目为2k - 1个结点拥有最多的结点数目，深度为4的完全二叉树形态，共有24-1-1+1=8个结点。拥有最少的结点数目，深度为4的完全二叉树形态，共有24- 1=15个结点。所以当一棵完全二叉树的深度为k、结点个数为n时，

2k-1 - 1＜n≤2k - 1变换后得到：2k-1 ≤n＜2k，对不等式取对数，有k-1≤lb n＜k由于k是整数，所以有k =二叉树--五条性质性质4：具有n个结点的完全二叉树的深度k为。根据性质2，深度为k的二叉树最多的节点数目为2k - 1个结点拥有最多的结点数目，深度为4的完全二叉树形态，共有24-1-1+1=8个结点。拥有最少的结点数目，深度为4的完全二叉树形态，共有24- 1=15个结点。所以当一棵完全二叉树的深度为k、结点个数为n时，

2k-1 - 1＜n≤2k - 1变换后得到：2k-1 ≤n＜2k，对不等式取对数，有k-1≤lb n＜k由于k是整数，所以有k =二叉树--五条性质性质5：对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，(1)如果i > 1，序号为i的结点的双亲结点的序号为i整除2；

如果i = 1，序号为i的结点是根结点。(2)如果2i≤n，序号为i的结点有左孩子，左孩子结点的序号为2i；

如果2i＞n，序号为i的结点无左孩子。(3)如果2i+1≤n，序号为i的结点的右孩子结点的序号为2i+1；

如果2i+1＞n，序号为i的结点无右孩子。二叉树--五条性质对于(1)，

i = 1时就是根结点。i＞1时，比如结点7，它的双亲是7/2 = 3；结点9，它的双亲是9/2 = 4。对于(2)，

结点6，因为2 × 6 = 12超过了结点个数10，

所以结点6没有左孩子，它是叶子结点；

结点5，因为2 × 5 = 10没有超过结点个数10，

所有它有左孩子，左孩子结点为10。对于(3)，

结点5，2 × 5 + 1 = 11超过了结点个数10，

所以结点5没有右孩子；结点3，2 × 3 + 1 = 7没有超过结点个数10，所以结点3有右孩子，右孩子是结点7。二叉树--五条性质复习树树：有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，这棵树就是有序树；反之，则称为无序树。二叉树的特点每个结点最多有两棵子树，且互不相交；左子树和右子树是有顺序的，次序不能颠倒。因此二叉树具有五种基本形态：左子树右子树左子树右子树(a)(b)(c)(d)(e)去粗取精、去伪存真、由表及里，准确地揭示出事物的本质和规律。满二叉树完全二叉树

二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。证明：用数学归纳法。性质2:深度为k的二叉树至多有2k-1个结点（k≥1）性质3:对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。性质4：具有n个结点的完全二叉树的深度为［log2n］+1。性质5:对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（1）如i=1，则i是根结点，无双亲；如i>1，则i的结点的双亲结点序号为［i/2］（2）如2i>n，则i的结点无左孩子；否则Lchild(i)=2i（3）如2i＋1>n，则i的结点无右孩子；否则Rchild(i)=2i+1事物的本质和规律每一结点最多可有两个后继。AGFEDCB二叉树的结构是非线性的，根结点没有前驱；除根之外任意一个结点只有唯一的一个前驱；6.2二叉树的存储结构

本质和规律提问：

用顺序存储结构可以存储二叉树吗？

链式存储结构可以吗？

二叉树--顺序存储结构ALKJIHGFEDCB132451211109876对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序存储到一维数组中(下标从1开始)。依据二叉树的性质5，对于存储位置为i的结点：如果i = 1，则该结点是根结点；

如果i＞1，则其双亲结点的存储位置为i/2；如果2i≤n，则其左孩子的存储位置为2i；如果2i＞n，则无左孩子；

如果2i+1≤n，则其右孩子的存储位置为2i+1；如果2i+1 > n，则无右孩子。最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。ALKJIHGFEDCB

123456789101112完全二叉树二叉树的顺序存储结构

二叉树--顺序存储结构ALKJIHGFEDCB132451211109876二叉树的顺序存储表示可描述为：

#defineMAXNODE /*二叉树的最大结点数*/typedefdatatypeSqBiTree[MAXNODE];/*0号单元存放结点数目*/SqBiTreebt;对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系；只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。

二叉树--顺序存储结构AFEDCBG

12345678910111213ABCVDEVVFVVVG注意:刚才添加的那些虚结点，在存储中设置为空。VVVVVV

ABCDD一棵深度为k的右单支树，只有k个结点，添加空结点使之成为深度为K的完全二叉树，就需要分配2k-1个存储单元。所以，二叉树的顺序存储结构仅适合于存储完全二叉树。

二叉树--顺序存储结构123456789101112131415ABCVDVVVVVVVVVVA最坏的情况:右单支树尺有所短，寸有所长《楚辞·卜居》：“夫尺有所短，寸有所长，物有所不足，智有所不明，数有所不逮，神有所不通。”双向链表，每一个结点有两个指针域，一个指向前驱，一个指向后继。二叉树的结构是非线性的，根结点没有前驱，除根之外任意一个结点只有唯一的一个前驱；每一结点最多可有两个后继。对于二叉树中的结点，可以增加两个指针域，一个指向左孩子，一个指向右孩子。

二叉树—二叉链表存储前驱指针后继指针datapriornext左孩子指针右孩子指针datalchildrchild也可以再增加一个指针指向双亲对于任意的二叉树来说，给每个结点设计一个存储结点本身信息的域和两个指针域分别指向该结点的左孩子、右孩子。lchilddatarchild

二叉树—二叉链表存储二叉链表结点的结构可以定义为一个结构体：typedefstructNode{datatypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;当左孩子或右孩子不存在时，相应指针域值为空(用符号∧或NULL表示)。结点的数据信息指向左孩子的指针指向右孩子的指针对于一棵二叉树的二叉链表，设一头指针指向根结点就可以了。这棵二叉树，用二叉链表存储，设头指针bt指向根结点。AGFEDCBVEFCGBDVVVVVAVV头指针bt

二叉树—二叉链表存储如果一个二叉树含有n个结点，那么它的二叉链表中必含有2n个指针域，其中必有n+1个空的链域。AGFEDCBVEFCGBDVVVVVAVV头指针bt

二叉树—二叉链表存储二叉树中除根结点之外，每个结点都有一个双亲，所以，含有n个结点的二叉树其分支数目B = n-1，即非空的链域有n-1个，故空链域有2n-(n-1) = n+1个。为了便于找到双亲结点，可增加一个parent域，parent域指向该结点的父结点，

就形成了三叉链表。头指针btAGVVVEVCBVDFVVVV

二叉树--三叉链表存储三叉链表中每个结点由四个域组成，具体结构为：其中，data、lchild以及rchild三个域的意义与二叉链表一样；

parent域是指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。lchilddatarchildparent

二叉树--三叉链表存储尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。

二叉树--存储结构尺有所短，寸有所长《楚辞·卜居》：“夫尺有所短，寸有所长，物有所不足，智有所不明，数有所不逮，神有所不通。”6.3二叉树的遍历二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。通过一次完整的遍历，可把二叉树中结点信息由非线性排列变为某种意义上的线性序列，这就给程序的实现带来了好处。一棵不空的二叉树由根结点D、左子树L和右子树R三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树了。DLR如果限定先左后右，那么就有三种遍历顺序：

①先访问根结点D；再遍历左子树L；最后遍历右子树R；LRD如果限定先左后右，那么就有三种遍历顺序：

①先访问根结点D；再遍历左子树L；最后遍历右子树R；

②先遍历左子树L；再访问根结点D；最后遍历右子树R；LRD如果限定先左后右，那么就有三种遍历顺序：

①先访问根结点D；再遍历左子树L；最后遍历右子树R；

②先遍历左子树L；再访问根结点D；最后遍历右子树R；

③先遍历左子树L；再遍历右子树R；最后访问根结点D。LR在这三种顺序中，只是访问根结点D的位置不同D如果限定先左后右，那么就有三种遍历顺序：

①先访问根结点D；再遍历左子树L；最后遍历右子树R；

②先遍历左子树L；再访问根结点D；最后遍历右子树R；

③先遍历左子树L；再遍历右子树R；最后访问根结点D。LR在这三种顺序中，只是访问根结点D的位置不同D先序遍历中序遍历后序遍历这三种遍历算法显然是递归的，根结点只有一个，所以访问根结点，就可以直接对根结点进行相应的操作了。比如输出根结点；左子树、右子树要么为空，要么依然是一棵二叉树，所以左子树、右子树的遍历就是递归的了。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。二叉树--先序遍历1、二叉树--先序遍历(DLR)算法的步骤：(0)如果二叉树为空，遍历结束；否则，(1)访问根结点；(2)先序遍历根结点的左子树；(3)先序遍历根结点的右子树。1voidPreOrder(BiTreebt)2{3if(bt==NULL)4return;5printf(“%c”,bt->data);6PreOrder(bt->lchild);7PreOrder(bt->rchild);8}先序遍历二叉树bt递归调用的结束条件输出bt的data递归调用先序遍历函数遍历bt的左子树递归调用先序遍历函数遍历bt的右子树二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}bt输出序列Abt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列AbtBbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABbtDbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);

6PreOrder(bt->rchild);7}输出序列ABDbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDbtGbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);

7}输出序列ABDGbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);

7}输出序列ABDGbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGbtCbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCbtEbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEbtFbtNULL二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEFbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEFbtbtNULL二叉树--先序遍历二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEFbtNULLbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEFbtbt二叉树--先序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4printf(“%c”,bt->data);5PreOrder(bt->lchild);6PreOrder(bt->rchild);7}输出序列ABDGCEFbtbt2.

中序遍历(LDR)中序遍历的递归过程为：(0)若二叉树为空，遍历结束；否则，(1)中序遍历根结点的左子树；(2)访问根结点；(3)中序遍历根结点的右子树。二叉树--中序遍历1voidInOrder(BiTreebt)2{3if(bt==NULL)4return; 5InOrder(bt->lchild); 6printf(“%c”,bt->data); 7InOrder(bt->rchild); 8}中序遍历二叉树bt递归调用的结束条件中序递归遍历bt的左子树访问结点的数据域中序递归遍历bt的右子树二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}btNULLbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列Dbtbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtNULLbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtNULLbtG二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);

7}输出序列DbtbtG二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);

7}输出序列DbtbtG二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtBbtNULLG二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DBbtNULLbtG二叉树--中序遍历二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DBbtbtGABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DBbtAbtG二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtbtGBA二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGBAbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGBAbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGBAEbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGBAEbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DbtGBAEbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAEbtCbt二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECbtbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild);

5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECbtbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECbtFbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECbtFbtNULL二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECbtFbt二叉树--中序遍历二叉树--中序遍历ABVCVDVEVVFVVGV1voidPreOrder(BiTreebt)2{3if(bt==NULL)return;4InOrder(bt->lchild); 5printf(“%c”,bt->data); 6InOrder(bt->rchild);7}输出序列DGBAECFbtbt3.后序遍历(LRD)后序遍历的递归过程为：(0)若二叉树为空，遍历结束；否则，(1)后序遍历根结点的左子树，(2)后序遍历根结点的右子树，(3)访问根结点。二叉树--后序遍历1voidPostOrder(BiTreebt)2{3if(bt==NULL)4 return; 5PostOrder(bt->lchild);6PostOrder(bt->rchild);7printf(“%c”,bt->data);8}后序遍历二叉树bt递归调用的结束条件后序递归遍历bt的左子树后序递归遍历bt的右子树访问结点的数据域二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbt二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);6printf(“%c”,bt->data);7}btbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}bt输出序列Gbt二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}输出序列GbtDbt二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}输出序列GDbtbtNULL二叉树--后序遍历ABVCVDVEVVFVVGV1voidPostOrder(BiTreebt)2{3if(bt==NULL) return; 4PostOrder(bt->lchild);

5PostOrder(bt->rchild);

6printf(“%c”,bt->data);7}输出序列GDbtbtNULL二叉树--后序遍历