树和二叉树的有关概念

第6章树和二叉树6.1树的有关概念6.1树的有关概念一．树的应用学生档案管理的组织方式组织机构图、家谱图、编译中的语法树等DOS／Windows文件系统6.1树的有关概念二．树的定义

树是n(n≥0)个结点的有限集合，当n=0时，集合为空集，称为空树；在任意一棵非空树T中：①有且仅有一个称为根(Root)的结点；②当n>1时，除根结点外的其余结点可分成m(m>0)个互不相交的有限T1、T2、……、Tm集合，其中每一个集合本身又是一棵树，并称其为根的子树。6.1树的有关概念JIACBDHGFEKLMA只有根结点的树树的一般表示6.1树的有关概念例如树T如对于根A，其余结点可分为3个互不相交的集合：

T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M}，其中的每一集合都本身又是一棵树，称为根A的子树。6.1树的有关概念JIACBDHGFEKLM在树中：

①只有根结点没有前驱；

②除根外，其余结点均有且仅一个前驱；③结点可以有0个或多个后继；

④其余结点均只有唯一条从根到该结点的路径。6.1树的有关概念JIACBDHGFEKLM⑴根：没有前驱的结点；⑵结点：包含一个数据元素及若干指向其子树的分支；⑶双亲与孩子：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲；⑷兄弟：同一双亲的孩子之间称为兄弟；祖先：从根到该结点所经分支上的所有结点；

子孙：以某结点为根的子树中的任一结点称为其子孙；堂兄弟：其双亲在同一层的结点；三．树的基本术语6.1树的有关概念JIACBDHGFEKLM三．树的基本术语⑸结点的层次：根为第一层，根的孩子为第二层……；⑹树的深度：树中结点的最大层次；⑺结点的度：结点拥有的子树数；⑻叶结点：度为0的结点；分支结点：度不为0的结点；⑼树的度：树中各结点的度的最大值；6.1树的有关概念JIACBDHGFEKLM三．树的基本术语⑽有序树：将树中各子树看成有次序的，称为有序树；否则称为无序树；⑾森林：m(m≥0)棵互不相交的树的集合。对树中每个节点而言，其子树的集合即为森林。6.1树的有关概念JIACBDHGFEKLM第6章树和二叉树6.2二叉树6.2二叉树(BinaryTree)一、二叉树的基本概念1.二叉树的定义二叉树的特点是树中每个结点至多只有二棵子树，并且二叉树的子树有左右之分，其次序不能颠倒。

A

F

G

E

D

C

B说明：①二叉树中结点的度≤2；②子树有左右之分——有序树；

A

F

G

E

D

C

B(a)左子树有四个结点(b)左子树有两个结点(a)

A

G

E

D

B

C

F(b)6.2二叉树(BinaryTree)2.二叉树的基本形态二叉树有五种基本形态：(1)(2)(3)(4)(5)6.2二叉树(BinaryTree)二、二叉树性质性质1

在二叉树的第i层上至多2i-1个结点(i≥0)用数学归纳法证明：当i=1时，2i-1=20=1，成立；设i=k时，命题成立，即第k层上至多有2k-1个结点；因为二叉树每个结点的度≤2，故在第k+1层上最大结点数为第k层上最大结点数的2倍，即为2×2k-1＝2(k+1)-1

。命题得到证明。6.2二叉树(BinaryTree)二、二叉树性质性质2

深度为k的二叉树最多有2k-1个结点(i≥1)深度为k的二叉树的最大结点数为：

=(第1层的)+(第2层的)+……+(第k层的)=21-1+22-1+23-1+……+2k-1=20+21+22+……+2k-1

=2k-111111111876543216.2二叉树(BinaryTree)二、二叉树性质性质3

对任何一棵二叉树，如果其叶结点数为n0

，度为2的结点数为n2

，则n0=n2+1设度为1的结点数为n1

。由于二叉树中所有结点的度≤2，则结点总数为：

n=n0+n1+n2...........(6-1)

二叉树中除根结点外，其余结点均有一个分支进入，则结点总数n=(分支数)+1，而所有分支都是由度为1和2的结点发出的，所以(分支数)=n1+2*n2，从而有：

n=n1+2×n2+1...........(6-2)由式(6-1)和(6-2)得：n0+n1+n2=n1+2*n2+1

n0＝n2+16.2二叉树(BinaryTree)二、二叉树性质性质3

对任何一棵二叉树，如果其叶结点数为n0

，度为2的结点数为n2

，则n0=n2+16.2二叉树(BinaryTree)两种特殊形态的二叉树满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。特点：每一层上结点的个数都是最大结点数。6.2二叉树(BinaryTree)两种特殊形态的二叉树完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。6.2二叉树(BinaryTree)两种特殊形态的二叉树6.2二叉树(BinaryTree)二、二叉树性质性质4

具有n个结点的完全二叉树的深度为设其深度为k，则：

2k-1-1＜n≤2k-12k-1＜n≤2kk-1≤log2n＜k6.2二叉树(BinaryTree)二、二叉树性质性质5

如果对一棵有n个结点的完全二叉树的结点按层次从左到右进行编号，则对任一结点i(1≤i≤n)：⑴如果i=1，则结点i为二叉树的根，无双亲；

如果i>1，则结点i的双亲是结点。i[i/2]6.2二叉树(BinaryTree)二、二叉树性质性质5

如果对一棵有n个结点的完全二叉树的结点按层次从左到右进行编号，则对任一结点i(1≤i≤n)：⑵如果2i≤n，则结点i的左孩子为2i；

否则结点i无左孩子。2ii6.2二叉树(BinaryTree)二、二叉树性质性质5

如果对一棵有n个结点的完全二叉树的结点按层次从左到右进行编号，则对任一结点i(1≤i≤n)：⑶如果2i+1≤n，则结点i的右孩子为2i+1；

否则结点i无右孩子。2ii2i+16.2二叉树(BinaryTree)结点数为j层j+1层j-1层6.2二叉树(BinaryTree)结点数为j层j+1层j-1层6.2二叉树(BinaryTree)结点i和i+1在同一层上6.2二叉树(BinaryTree)结点i和i+1不在同一层上6.2二叉树(BinaryTree)三、二叉树的存储结构1.顺序存储结构structBT{

ElemType

bt[MaxSize];

int

btnum;}将完全二叉树上编号为

i的结点元素存储在一维数组中下标为i

的位置上，即bt[i]。完全二叉树编号为

i的结点存储在bt[i]中6.2二叉树(BinaryTree)三、二叉树的存储结构1.顺序存储结构对于一个一般的二叉树，将其“转化”为完全二叉树后，按照完全二叉树的顺序存储方式将结点存入到数组中。6.2二叉树(BinaryTree)三、二叉树的存储结构1.顺序存储结构转化方法：在非完全二叉树的“残缺”位置上增设“虚结点”。对于一个一般的二叉树，将其“转化”为完全二叉树后，按照完全二叉树的顺序存储方式将结点存入到数组中。非完全二叉树非完全二叉树增设“虚结点”非完全二叉树按照完全二叉树顺序存储6.2二叉树(BinaryTree)三、二叉树的存储结构1.顺序存储结构structBT{

ElemType

bt[MaxSize];

int

btnum;}顺序存储结构仅适用于完全二叉树，对于非完全二叉树会有较大的存储空间的浪费。6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构二叉树的链式存储结构通常有二叉链表和三叉链表两种形式。6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构structBTnode

{

ElemType

data;structBTnode*lchild,*rchild;};二叉链表6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构structBTnode

{

ElemType

data;structBTnode*lchild,*rchild,*parent;};三叉链表6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构6.2二叉树(BinaryTree)三、二叉树的存储结构2.链式存储结构第6章树和二叉树6.3遍历二叉树6.3遍历二叉树遍历二叉树按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。6.3遍历二叉树遍历二叉树按某种规律周游二叉树，对树中的每个结点访问一次且仅访问一次。按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。6.3遍历二叉树二叉树是由根结点、左子树、右子树三个基本单元组成。一、遍历二叉树的操作定义6.3遍历二叉树二叉树是由根结点、左子树、右子树三个基本单元组成。一、遍历二叉树的操作定义遍历二叉树就是依次遍历这三部分。6.3遍历二叉树二叉树是由根结点、左子树、右子树三个基本单元组成。一、遍历二叉树的操作定义根据遍历二叉树的顺序不同，有三种遍历方法：先序(根)遍历（DLR）

中序(根)遍历（LDR）

后序(根)遍历（LRD）D—表示访问根结点L—表示遍历左子树R—表示遍历右子树遍历二叉树就是依次遍历这三部分。6.3遍历二叉树若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。一、遍历二叉树的操作定义1.先序(根)遍历（DLR）6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：A若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：AB若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：ABD若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：ABDE若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：ABDEC若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义1.先序(根)遍历（DLR）先序遍历序列：ABDECF若二叉树为空，则空操作；否则

⑴访问根结点；⑵先序遍历左子树；

⑶先序遍历右子树。6.3遍历二叉树若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。一、遍历二叉树的操作定义2.中序(根)遍历（LDR）6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：D若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DB若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DBE若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DBEA若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DBEAF若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DBEAFG若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树一、遍历二叉树的操作定义2.中序(根)遍历（LDR）中序遍历序列：DBEAFGC若二叉树为空，则空操作；否则

⑴中序遍历左子树；⑵访问根结点；

⑶中序遍历右子树。6.3遍历二叉树若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。一、遍历二叉树的操作定义3.后序(根)遍历（LRD）6.3遍历二叉树一、遍历二叉树的操作定义3.后序(根)遍历（LRD）后序遍历序列：若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：D3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DE3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DEB3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DEBG3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DEBGF3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DEBGFC3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义后序遍历序列：DEBGFCA3.后序(根)遍历（LRD）若二叉树为空，则空操作；否则

⑴后序遍历左子树；⑵后序遍历右子树；

⑶访问根结点。6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-c中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/e中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：a例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：ab例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abc例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+e例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef/例：6.3遍历二叉树一、遍历二叉树的操作定义先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef/-例：6.3遍历二叉树一、遍历二叉树的操作定义思考题：先序遍历序列：1245367中序遍历序列：4251673请画出该二叉树二叉树的遍历如下：6.3遍历二叉树一、遍历二叉树的操作定义思考题：先序遍历序列：1245367中序遍历序列：4251673请画出该二叉树二叉树的遍历如下：structBTnode

{

ElemType

data;structBTnode*lchild,*rchild;};二叉链表的存储表示二、遍历二叉树的递归算法6.3遍历二叉树回顾：二、遍历二叉树的递归算法6.3遍历二叉树回顾：6.3遍历二叉树二、遍历二叉树的递归算法voidpreorder(struct

BTnode*root){if(root!=NULL){

printf("%c",root->data)；

preorder(root->lchild);preorder(root->rchild);}}1.先序遍历递归算法6.3遍历二叉树二、遍历二叉树的递归算法voidinorder(struct

BTnode*root){if(root!=NULL){

inorder(root->lchild);

printf("%c",root->data);

inorder(root->rchild);}}2.中序遍历递归算法6.3遍历二叉树二、遍历二叉树的递归算法voidpostorder(struct

BTnode*root){if(root!=NULL){

postorder(root->lchild);

postorder(root->rchild);

printf("%c",root->data);}}3.后序遍历递归算法6.3遍历二叉树三、遍历二叉树的非递归算法递归算法相对简明直观，清晰易懂，容易写出，但其效率较低，相比之下，非递归算法执行效率更高。基本思路：栈s保存已访问过的结点；指针p=root；如果栈s非空或p非空，做如下操作：6.3遍历二叉树三、遍历二叉树的非递归算法1.先序遍历非递归算法基本思路：栈s保存已访问过的结点；指针p=root；如果栈s非空或p非空，做如下操作：6.3遍历二叉树三、遍历二叉树的非递归算法1.先序遍历非递归算法①若p非空，则访问根结点，p进栈；令

p指向该结点的左子树的根，继续遍历；基本思路：栈s保存已访问过的结点；指针p=root；如果栈s非空或p非空，做如下操作：6.3遍历二叉树三、遍历二叉树的非递归算法1.先序遍历非递归算法②若p为空，应返回到上层结点：

(i)若从左子树返回，将p指向当前结点的右子树的根，继续遍历；

(ii)若从右子树返回，继续出栈；①若p非空，则访问根结点，p进栈；令

p指向该结点的左子树的根，继续遍历；基本思路：栈s保存已访问过的结点；指针p=root；如果栈s非空或p非空，做如下操作：6.3遍历二叉树三、遍历二叉树的非递归算法1.先序遍历非递归算法如果栈s空且p空，则遍历结束。②若p为空，应返回到上层结点：

(i)若从左子树返回，将p指向当前结点的右子树的根，继续遍历；

(ii)若从右子树返回，继续出栈；①若p非空，则访问根结点，p进栈；令

p指向该结点的左子树的根，继续遍历；voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}6.3遍历二叉树1.先序遍历非递归算法6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}6.3遍历二叉树1.先序遍历非递归算法Avoidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}A6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}A6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}A6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}AB6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}AB6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}AB6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}AB6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABD6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}while(!Empty(s)||p!=NULL);}ABDE6.3遍历二叉树1.先序遍历非递归算法voidpreorder(struct

BTnode*root){p=root;InitStack(s);do{

while(p!=NULL){

printf(“%c”,p->data);

push(s,p);p=p->lchild;}

if(!Empty(s)){p=pop(s);p=p->rchild;}}}wh