二叉树及其遍历教材课件

二叉树遍历及其算法主讲人:程玉胜2008.06.17《数据结构》申报精品课程录像1/39内容提要

复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法2/39复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法内容提要3/39(一)

二叉树的定义度不大于2，且子树有左右之分，不能颠倒二叉树的5种基本形态DDLDLRDR(a)(b)(c)(d)(e)复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法4/39(一)

二叉树性质应用(1)如果一棵二叉树有10个叶子结点，有8个结点仅有左孩子，12个结点仅有右孩子，问该二叉树有多少个结点？复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法思考解易知：n=n0+n1+n2已知：n0＝10，n1＝8＋12＝20P124，性质3知：n2＝n0-1=9所以，n=10＋20＋9＝395/39(一)

二叉树性质应用(2）已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法思考解1P124，性质4知：树的深度1＋log2100＝7P124，性质2知：上面6层结点数26-1=63所以，第7层有100－63＝37个叶子它们是第6层中19个结点的孩子，因此第6层中没有孩子的结点是32－19＝13所以，叶子结点数37＋13＝50第6层26-1=326/39(一)

二叉树性质应用(2）已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法思考解2P124，性质5知：编号100的结点父亲是100/2=50因此从51～100是叶子结点所以，叶子结点数100－50＝50i2i+12ii/27/39内容提要

复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法复习二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法8/39

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法内容提要9/39(二)

二叉树存储结构(1)

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法顺序存储结构abcdabcd…二叉链表存储结构typedefchardatatypetypedef

struct

BiTNode{datatypedata;

struct

BiTNode*lchild,*rchild;//左右指针}10/39(二)

二叉树存储结构(2)

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法二叉链表存储结构a^b^c^^d^图有多少个空指针？5在n个结点的二叉链表中，空(^)指针数有多少个？思考解n个结点,共有2n个指针其中,n-1个结点有父亲（根除外）所以，2n-(n－1）=n+1n+111/39(二)

二叉树遍历方法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法遍历二叉树定义：指按照某种顺序访问二叉树的每个结点一次且仅被“访问”一次。常见“访问”的方法：voidvisit(datatypee){printf(e);}//实际使用时，加上格式控制符DLR遍历时，限定先左后右：

LDR；DLR；LRD12/39(二)

先序遍历算法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

先序(DLR)遍历

(2)遍历左子树(L)(3)遍历右子树(R)

(1)访问根结点(D)

voidPreOrder(struct

BiTNode*T){if(T!=NULL)

visit(T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}

13/39(二)

中序遍历算法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

中序(LDR)遍历

(1)遍历左子树(L)(3)遍历右子树(R)

(2)访问根结点(D)

voidInOrder(struct

BiTNode*T){if(T!=NULL)

InOrder(T->lchild);

visit(T->data);

InOrder(T->rchild);}

14/39(二)

后序遍历算法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

后序(LRD)遍历

(1)遍历左子树(L)(2)遍历右子树(R)

(3)访问根结点(D)

voidPostOrder(struct

BiTNode*T){if(T!=NULL)

PostOrder(T->lchild);

PostOrder(T->rchild);

visit(T->data);}

15/39内容提要

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法

复习

二叉树遍历及算法遍历序列求解遍历算法的拓展遍历非递归算法16/39

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法内容提要17/39(三)

由二叉树求序列

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法给出右图的遍历结果序列例1abcefd中序遍历：

(1)a

LR先序遍历：abdcef后序遍历：dbfeca

(2)

Lba

L

ca

LR结果：dbaefc18/39(三)

由序列求二叉树(1)

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法已知先序和中序结果，构造二叉树先序：abcdefghij中序：cdbfeaihgj例2由先序结果，二叉树根为a

acdbfeihgj解abgcdfejih19/39(三)

由序列求二叉树(2)

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法先序和后序结果，能构造唯一的二叉树吗？思考20/39(三)

算法实现

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法（1）建立二叉树struct

BiTNode*CreateBiTree(void){charch;struct

BiTNode*T;ch=getchar();if(ch=='@')T=NULL;else{T=(struct

BiTNode*)malloc(sizeof(struct

BiTNode));T->data=ch;T->lchild=CreateBranchTree();T->rchild=CreateBranchTree();}returnT;}}

上机实现步骤：21/39(三)

算法实现

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法（2）主程序中调用main(){struct

BiTNode*head;printf("pleaseinputthenode\n:");head=CreateBranchTree();printf("\n

pre_Order:");pre_Order(head);

printf("\n

mid_Order:");mid_Order(head);

printf("\nlast_Order:");last_Order(head);

getch();}算法实现步骤：[程序演示]22/39内容提要

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法

复习二叉树遍历及算法

遍历序列求解遍历算法的拓展遍历非递归算法23/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法内容提要24/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法(四)

拓展“访问”(1)设计算法按先序次序输出二叉树T中所有叶子结点的值。例3

voidPreOrder(struct

BiTNode*T){if(T!=NULL)

visit(T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);}

解相同：均为先序输出不同：此题有条件输出，叶子的条件是??If(T->lchild==NULL&&T->rchild==NULL)

visit(T->data);25/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法(四)

拓展“访问”(2)设计算法按后序次序输出二叉树T中前k个结点的值。例4解相同：均为后序输出不同：此题有条件输出，前k个结点的条件是??

n=n+1;If(n<=k)

visit(T->data);

voidPostOrder(struct

BiTNode*T){if(T!=NULL)

PostOrder(T->lchild);

PostOrder(T->rchild);

visit(T->data);}26/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法(四)

遍历算法拓展(1)设计算法求解给定二叉树的高度。例5解(1)如果T为空，则高度为0；(2)否则，其高度是左右子树中高度的最大值＋1int

PostTreeDepth(struct

BiTNode*bt){int

hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);}elsereturn(0);}后序遍历27/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法(四)

遍历算法拓展(2)设计算法按照先序次序依次输出二叉树结点值及其所在的层次。例6解先序遍历的拓展如果知道当前结点的层次，那么就知道其孩子结点的层次，因此，在先序遍历算法中增加层次参数voidPrintTree(struct

BiTNode*bt,int

nLayer){if(bt==NULL)return;printf("(%c,%d)",bt->data,nLayer);PrintTree(bt->LChild,nLayer+1);PrintTree(bt->RChild,nLayer+1);}28/39

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法(四)

遍历算法综合程序1、求二叉树结点数2、求二叉树叶子结点数思考[程序演示]综合程序29/39内容提要

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法

复习二叉树遍历及算法遍历序列求解

遍历算法的拓展遍历非递归算法30/39

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法内容提要31/39(五)

中序递归过程回顾下图的中序遍历结果例7

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法abcefd32/39(五)

中序递归过程mid()表示中序算法中序：dbaefc

mid(a)mid(b)amid(c)mid(d)mid(^)bmid(^)dmid(^)mid(e)cmid(^)mid(^)emid(f)fmid(^)mid(^)

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法33/39

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法(五)堆栈变化过程par0par0pbr1par0pbr1pdr1par0pbr1输出d……34/39

复习二叉树遍历及算法遍历序列求解遍历算法的拓展

遍历非递归算法(五)非递归算法实现[程序演示]P129,动态创建35/39

复习二叉树遍历及算法遍历序列求解遍历算法的拓展