《数据结构基本知识二叉树遍历》由会员分享，可在线阅读，更多相关《数据结构基本知识二叉树遍历（44页珍藏版）》请在金锄头文库上搜索。
1、,第5章第2节,二叉树的遍历,计算机科学系 张红军,1.树的定义及性质 树(tree)是n(n0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。,回顾上节课主要内容,2.二叉树的定义及性质 二叉树是n(n0)个结点的有限集，它或为空树(n =0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。,3.二叉树的存储结构 顺序存储结构 按满二叉树的结点层次编号，依次存放二叉树中的数据元素,链式存储结构 使用二叉链表存储，通
2、过指针指向左右子树。,typedef char ElemType; typedef struct BiTNode ElemType data; struct BiTNode *lchild, *rchild BiTNode, *BiTree; BiTree bt;,4.树与二叉树转换,遍历按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。 常用方法 先序遍历：先访问根结点,然后分别先序遍历左子树、先序遍历右子树。 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树。 后序遍历：先后序遍历左、后序遍历右子树，然后访问根
3、结点,5.2 二叉树的遍历,二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。,根 左 右,先序遍历序列：A B D C,先序遍历:,A,B,D,C,先序遍历:,算法过程描述如下： 1.若二叉树为空，则返回 2.否则依次执行 访问根结点 先序遍历左子树 先序遍历右子树,void PreOrder(BiTree T) if(T!=NULL) printf(“%3c“,T-data); PreOrder(T-lchild); PreOrder(T-rchild); ,typedef struct BiTNode ElemTyp
4、e data; struct BiTNode *lchild, *rchild BiTNode, *BiTree;,1. void pre(BiTree T) 2. if(T!=NULL) 3. printf(“%3c“,T-data); 4. pre(T-L); 5. pre(T-R); 6. 7. ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,例：对如下二叉树进行前序遍历的结果为,A,B,D,E,C,F,F,C,A,D,B,E,G,左 根 右,中序遍历序列：B D A C,中序遍历:,B,D,A,C,中序遍历:,算法过程描述如下： 1.若二叉树为空，则返回 2.
5、否则依次执行 中序遍历左子树 访问根结点 中序遍历右子树,void InOrder(BiTree T) if(T!=NULL) ,InOrder(T-lchild); printf(“%3c“,T-data); InOrder(T-rchild);,typedef struct BiTNode ElemType data; struct BiTNode *lchild, *rchild BiTNode, *BiTree;,例：对如下二叉树进行中序遍历的结果为,D,B,E,A,F,C,A,C,B,D,F,E,G,左 右 根,后序遍历序列： D B C A,后序遍历:,D,B,C,A,后序遍历:,
6、算法过程描述如下： 1.若二叉树为空，则返回 2.否则依次执行 后序遍历左子树 后序遍历右子树 访问根结点,void PostOrder(BiTree T) if(T!=NULL) ,PostOrder(T-lchild); PostOrder(T-rchild); printf(“%2c“,T-data);,例：对如下二叉树进行后序遍历的结果为,D,E,B,F,C,A,A,B,D,C,G,E,F,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,例1：已知一棵二叉树的先序序列
7、为CEDBA，中序序列为DEBAC，试构造该二叉树。 基本思想： 在先序序列中找根，在中序序列中分左右。,DEBA,先序序列为： 中序序列为：,C,E,D,A,B,D,E,B,C,A,E,C,BA,B,练习 先序序列为：A B D E C F H G 中序序列为：D B E A H F C G 构造一棵二叉树。 答案,例2：已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，试构造该二叉树。 基本思想： 在后序序列中找根，在中序序列中分左右。,DEBA,后序序列为： 中序序列为：,D,A,B,C,E,D,E,B,C,A,E,C,BA,B,练习 后序序列为：D E B H F G C A
8、 中序序列为：D B E A H F C G 构造一棵二叉树。 答案,2.二叉树遍历的非递归算法,2.二叉树遍历的非递归算法,2.二叉树遍历的非递归算法,2.二叉树遍历的非递归算法,2.二叉树先序遍历的非递归算法,(1)先序遍历的非递归算法 令p指向根结点。 若p不为空，访问p所指结点，并将p压入栈中。 若p为空，转4。 将p所指结点的左孩子压入栈，转2。 从栈中弹出栈顶结点，令p指向所弹出结点的右孩子；转2。,2.二叉树先序遍历的非递归算法,2.二叉树先序遍历的非递归算法,(2)中序遍历的非递归算法 令p指向根结点。 若p不为空，将p压入栈中。 若p为空，转4。 将p所指结点的左孩子压入栈，
9、转2。 从栈中弹出栈顶结点，访问所弹出结点，令p指向所弹出结点的右孩子；转2。,2.二叉树中序遍历的非递归算法,遍历算法应用 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C D E G F ,求二叉树深度算法,统计二叉树中叶子结点个数算法,3.二叉树的层次遍历,4. 树和森林的遍历 树的遍历 先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点,先序遍历：,后序遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,4. 树和森林的遍历 森林的遍历 先根（序）遍历： 先访问第一颗树的根结点 先根遍历第一颗树中根结点的子树森林 先根遍历除去第一颗树之后剩余树构成的森林 后根（序）遍历 后跟遍历第一颗树的根结点的子树森林 访问第一颗树的根结点 后跟遍历除去第一颗树之后剩余树构成的森林,
