二叉树的遍历PPT课件

二叉树的遍历
• 前序和中序相同的二叉树,…… • 中序和后序相同的二叉树,……. • 前序和后序相同的二叉树,……
由二叉树的前序和中序可以唯一地确定一棵二叉树
前序：ABDEGCFH 中序：DBGEAFHC
由二叉树的中序和后序可以唯一地确定一棵二叉树 中序：DBGEAFHC 后序：DGEBHFCA
if (top!=NULL) { t=top->addr;
printf(“%c”,t->data); p=top; top=top->link; free(p); t=t->rchild;} } }
按后序遍历二叉树
• 首先按后序遍历根结点的左子树 • 然后按后序遍历根结点的右子树 • 最后访问根结点
判断两棵二叉树是否相等
• 两棵二叉树若都为空,则相等
• 两棵树的根结点的值相等,并且两棵树根 结点的左右子树分别相等,则两棵树相等
t1
t2
A
A
int equaltree(t1,t2) NODE *t1,*t2; { if (t1= =NULL&& t2==NULL) return(1);
if (t1!=NULL && t2!=NULL) if (t1->data= =t2->data)
是( )
如果某二叉树的前序为stuwv,中序为
uwtvs,则该二叉树的后序为(
).
如下图所示的二叉树是由有序树T1转换而 来的二叉树,则树T1有( )个叶子结点.
假设二叉树中所有非叶子结点都有左右子树, 若有n个叶子结点,则该二叉树共有( )个结点
若深度为h的二叉树上只有度为0和度为2的 结点,则此类二叉树中包含的结点数至少为( ).
if (t= =NULL) return(NULL); else {p=(NODE*) malloc(sizeof(NODE));
p->data=t->data; p->lchild=copy(t->lchild); p->rchild=copy(t->rchild); return(p); } }
在一非空二叉树的中序遍历序列中,根结 点的右边只有右子树上的所有结点
任何一棵二叉树的叶子结点在前序 中序和 后序遍历序列中的相对次序是不发生改变的.
已知某二叉树的后序遍历序列是dabec,
中序遍历序列是debac,则它的前序遍历是( )
某二叉树的前序遍历序列是abdgcefh,中
序遍历的序列是dgbaechf,则后序遍历的顺序
} }
按中序遍历二叉树
• 首先以中序遍历根结点的左子树 • 然后访问根结点 • 最后按中序遍历根结点的右子树
DBAECFG
按中序遍历二叉树
DB
AEC F G
void r_midorder(t) NODE *t; { if (t!=NULL)
{r_midorder(t->lchild); printf(“%c”,t->data); r_midorder(t->rchild);
DBEGFCA
void r_posorder(t) NODE *t; { if (t!=NULL)
{ r_posorder(t->lchild); r_posorder(t->rchild); printf(“%c”,t->data);
} }
前序：ABDEGCFH 中序：DBGEAFHC 后序：DGEBHFCA
若一棵二叉树,左右子树均有三个结点,其左 子树的前序序列与中序序列相同,右子树的中序 序列与后序序列相同,试构造该树
二叉树的遍历
• 按前序遍历 • 按中序遍历 • 按后序遍历
按前序遍历二叉树
• 首先访问根结点 • 然后按前序遍历根结点的左子树 • 最后按前序遍历根结点的右子树
ABDCEFG
void r_preorder(t) NODE *t; { if (t!=NULL)
{ printf(“%c”,t->data); r_preorder(t->lchild); r_preorder(t->rchild);
G^ top
^
E出栈,并输出.E的右孩子入栈 C出栈 C的右孩子进栈,再将该结点的所有左孩子入栈
F出栈 F的右孩子进栈,再将该结点的所有左孩子入栈
G出栈,并输出
#include <stdio.h> struct node {char data;
struct node *lchild; struct node *rchild; }; typedef struct node NODE; struct snode {NODE *addr; struct snode *link; }; typedef struct snode SNODE;
if (equaltree(t1->lchild,t2->lchild)) return( equaltree(t1->rchild,t2->rchild)); return(0); }
判断题:
二叉树的前序遍历序列中,任意一个结点 处在其子女结点的前面.
由于二叉树中每个结点的度最大为2,所以 二叉树就是二次有序树.
void s_midorder(t) NODE *t; {SNODE *top,*p; top=NULL; while(t!=NULL|| top!=NULL)
{while (t!=NULL) {p=(SNODE*) malloc(sizeof(SNODE)); p->addr=t; p->link=top; top=p; t=t->lchild;}
前序:ABCDEFGH
后序:CDBEGHFA 层次:ABEFCDGH
前序:ABCDEFGH
中序:CDBEGHFA 后序:CDHGFEBA
二叉树的遍历
• 将有序树转化为相应的二叉树 – 有序树的前序=二叉树的前序 – 有序树的后序=二叉树的中序
NODE *copy(t) NODE *t; {NODE *p;
} }
DBAECFGtopDBtop BA ^ 将树根的所有左孩子入栈
A^
D出栈,并输出
top B
A^
将D的右孩子入栈
top A^
top
^ top
E
B出栈,并输出.B的右孩子入栈 A出栈,并输出 C^
将A的右孩子入栈,再将此结点的所有左孩子入栈
top C^
top
^ top
F^ top
^ top