二叉树的遍历.ppt

二叉树的遍历按前序遍历按中序遍历按后序遍历

按前序遍历二叉树首先访问根结点然后按前序遍历根结点的左子树最后按前序遍历根结点的右子树ABCDFGEABDCEFG

voidr_preorder(t)NODE*t;{if(t!=NULL){printf(“%c”,t-data);r_preorder(t-lchild);r_preorder(t-rchild);}}

按中序遍历二叉树首先以中序遍历根结点的左子树然后访问根结点最后按中序遍历根结点的右子树ABCDFGEDBAECFG

ABCDFGEDBAECFG按中序遍历二叉树

voidr_midorder(t)NODE*t;{if(t!=NULL){r_midorder(t-lchild);printf(“%c”,t-data);r_midorder(t-rchild);}}

ABCDFGEDBAECFG

ABCDFGEA^BDtop将树根的所有左孩子入栈A^BtopD出栈,并输出

A^B将D的右孩子入栈A^B出栈,并输出.B的右孩子入栈^A出栈,并输出C^将A的右孩子入栈,再将此结点的所有左孩子入栈Etoptoptoptop

C^topE出栈,并输出.E的右孩子入栈^topC出栈F^topC的右孩子进栈,再将该结点的所有左孩子入栈^F出栈G^toptopF的右孩子进栈,再将该结点的所有左孩子入栈^topG出栈,并输出

#includestdio.hstructnode{chardata;structnode*lchild;structnode*rchild;};typedefstructnodeNODE;structsnode{NODE*addr;structsnode*link;};typedefstructsnodeSNODE;

voids_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;}

if(top!=NULL){t=top-addr;printf(“%c”,t-data);p=top;top=top-link;free(p);t=t-rchild;}}}

按后序遍历二叉树首先按后序遍历根结点的左子树然后按后序遍历根结点的右子树最后访问根结点ABCDFGEDBEGFCA

voidr_posorder(t)NODE*t;{if(t!=NULL){r_posorder(t-lchild);r_posorder(t-rchild);printf(“%c”,t-data);}}

ABCDFHEG前序：ABDEGCFH中序：DBGEAFHC后序：DGEBHFCA

二叉树的遍历前序和中序相同的二叉树,……中序和后序相同的二叉树,…….前序和后序相同的二叉树,……

ABCDFHEG前序：ABDEGCFH中序：DBGEAFHC由二叉树的前序和中序可以唯一地确定一棵二叉树

ABCDFHEG中序：DBGEAFHC后序：DGEBHFCA由二叉树的中序和后序可以唯一地确定一棵二叉树

ABEFCGHDABEFCDGH

ABEFCGHD前序:ABCDEFGH后序:CDBEGHFA层次:ABEFCDGH

ABEFCDGH前序:ABCDEFGH中序:CDBEGHFA后序:CDHGFEBA

二叉树的遍历将有序树转化为相应的二叉树有序树的前序=二叉树的前序有序树的后序=二叉树的中序

二叉树的前序遍历序列中,任意一个结点处在其子女结点的前面.(对)由于二叉树中每个结点的度