数据结构 严蔚敏 -第6章 树和二叉树2-遍历二叉树(刘).ppt

第6章 树和二叉树 刘灵丽 湘南学院 6.3 遍历二叉树 二 几种遍历方法 先序遍历（DLR)： 若二叉树为空，则空操作；否则 (1)访问根结点 (2)先序遍历左子树 (3)先序遍历右子树 中序遍历： 后序遍历： 按层次遍历：从上到下、从左到右访问各结点。 三、 先序建立二叉树 5.3 建立二叉树的二叉链表 6 用队列实现层次遍历 可使用一个顺序存储的队列q[100],存放还没有处理的子树的根结点的地址。注意,队首和队尾指针分别指向队首结点和下次进队结点的存放位置。 首先把根节点入队。 然后访问队头的一个结点，再把该结点非空的左右子树入队。 如果队列不空，重复2)。 练习 当用栈非递归实现树的先序遍历时，写出遍历右边所表示的树的全过程。像讲义中那样，写出遍历每一步栈中的数据。不是写具体的实现代码。 作业7：二叉树 分别写一个函数，统计二叉树的节点个数；输出树的深度；最大元；最小元；用树形结构打印出该二叉树。 提示： 统计结点数也是一种遍历操作，要首先理解遍历，递归程序。 由于printf打印是一行行按顺序的，要打印出树形结构，必须按层次遍历，并且利用空格。关键是控制每一层次打印的空格的数量，以及子树为空的情形。 * * — 遍历二叉树 一 什么叫遍历 树中每个节点被访问有且仅有一次。 A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A 后序遍历: B void preorder(BiTree T) { if(T) { printf(%c ,bt-data); preorder(bt-lchild); preorder(bt-rchild); } } 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A C B D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 先序遍历算法的递归描述 - + / a * b - e f c d 先序遍历： 中序遍历： 后序遍历： 层次遍历： - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f 以字符串的形式表示一棵二叉树 A B C D 以字符串“■表示 空树 只含根结点的二叉树 A 以字符串“ A■■ 表示 以“ AB■ C■■ D■■表示 Status CreateBiTree(BiTree T) { scanf(ch); if (ch== ) T = NULL; else { T = (BiTNode *)malloc(sizeof(BiTNode)); T-data = ch; // 生成根结点 CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } return OK; } A B C D A B C D 上页算法执行过程举例如下： A T B C D ^ ^ ^ ^ ^ 3 中序遍历算法的非递归描述 1，根结点入栈 2，若栈空则转8 3，while(栈顶元素不是空指针)左孩子入栈 4，若栈顶元素为空指针，则空指针出栈 5，若栈不空，出栈，访问结点 6，右孩子入栈 7，转2 8，return void I