二叉树的遍历

目目 录录 一 设计思想 01 二 算法流程图 01 三 源代码 04 四 运行结果 08 五 遇到的问题及解决 09 六 心得体会 10 二叉树的遍历 1 一 一 设计思想设计思想 遍历二叉树首先有三种方法 即先序遍历 中序遍历和后序遍历 递归方法比较简单 首先获得结点指针如果指针不为空 且有左子 从左子递归 到下一层 如果没有左子 从右子递归到下一层 如果指针为空 则结束一层递归调 用 直到递归全部结束 下面重点来讲述非递归方法 首先介绍先序遍历 先序遍历的顺序是根 左 右 也就是说先访问根结点然后访问其左子再然后访问 其右子 具体算法实现如下 如果结点的指针不为空 结点指针入栈 输出相应结点 的数据 同时指针指向其左子 如果结点的指针为空 表示左子树访问结束 栈顶结 点指针出栈 指针指向其右子 对其右子树进行访问 如此循环 直至结点指针和栈 均为空时 遍历结束 再次介绍中序遍历 中序遍历的顺序是左 根 右 中序遍历和先序遍历思想差不多 只是打印顺序稍 有变化 具体实现算法如下 如果结点指针不为空 结点入栈 指针指向其左子 如 果指针为空 表示左子树访问完成 则栈顶结点指针出栈 并输出相应结点的数据 同时指针指向其右子 对其右子树进行访问 如此循环直至结点指针和栈均为空 遍 历结束 最后介绍后序遍历 后序遍历的顺序是左 右 根 后序遍历是比较难的一种 首先需要建立两个栈 一个用来存放结点的指针 另一个存放标志位 也是首先访问根结点 如果结点的指 针不为空 根结点入栈 与之对应的标志位也随之入标志位栈 并赋值 0 表示该结 点的右子还没有访问 指针指向该结点的左子 如果结点指针为空 表示左子访问完 成 父结点出栈 与之对应的标志位也随之出栈 如果相应的标志位值为 0 表示右 子树还没有访问 指针指向其右子 父结点再次入栈 与之对应的标志位也入栈 但 要给标志位赋值为 1 表示右子访问过 如果相应的标志位值为 1 表示右子树已经访 问完成 此时要输出相应结点的数据 同时将结点指针赋值为空 如此循环直至结点 指针和栈均为空 遍历结束 二 二 算法流程图算法流程图 下图是定义的二叉树的结构图 二叉树的遍历 2 图 1 二叉树结构图 下图是递归算法的流程图 首先的到当前根结点 判断结点指针是否空 如果非 空 判断左子指针是否为空 非空则指向左子 左子作为当前根结点 空则判断右 子指针是否为空 非空则指向右子 右子作为当前根结点 如果空 输出相应的数 据 结束递归 图 2 递归算法流程图 下图是非递归算法先序遍历的算法流程图 首先对结点指针进行判断 如果指针 不为空 结点指针入栈 输出数据 指针指向左子 访问左子树 如果结点指针 为空 栈顶结点指针出栈 指针指向右子 访问右子树 直至遍历整个二叉树 A BC D E G F 二叉树的遍历 3 图 3 非递归先序遍历算法流程图 下图是非递归中序遍历算法流程图 首先对结点指针进行判断 如果指针不为空 则指针入栈 指针指向其左子 对左子树进行访问 如果结点指针为空 栈顶结点指 针出栈 输出相应的数据 指针指向右子 对右子树进行访问 直至遍历整个二叉树 图 4 非递归中序遍历算法流程图 下图是非递归后序遍历二叉树算法流程图 首先对结点指针进行判断 如果指针 二叉树的遍历 4 不为空 结点指针和相应的标志位同时入栈 指针指向左子 对左子树进行遍历 如 果指针为空 栈顶指针和相应的标志位同时出栈 如果标志位的值为 0 则结点再次 入栈 标志位置 1 随之入栈 指针指向右子 访问右子树 如果标志位的值为 1 输 出相应结点的数据 并将结点指针置为 NULL 直至遍历结束 图 5 非递归后序遍历算法流程图 三 三 源代码源代码 include define MAX 100 表示栈的最大容量 define FULL 99 表示栈满 define EMPTY 1 表示栈空 typedef struct Tnode 定义结点 char data 存储结点数据 struct Tnode left 定义结点左子指针 struct Tnode right 定义右子指针 Tnode Pnode 声明 Tnode 类型的变量和指针 typedef struct Stack 定义栈 Pnode pnode MAX 存放数据 int p 栈顶指针 Stack Pstack 定义 Stack 类型的变量和指针 void Push Pstack pstack Pnode pnode 入栈 pstack p pstack pnode pstack p pnode 赋值 二叉树的遍历 5 Pnode Pop Pstack pstack 出栈 return pstack pnode pstack p Pnode Top Pstack pstack 看栈顶元素 return pstack pnode pstack p int Isempty Pstack pstack 栈判空 if pstack p EMPTY return 1 else return 0 int Isfull Pstack pstack 栈满 if pstack p FULL return 1 else return 0 void Initstack Pstack pstack 初始化栈 pstack p EMPTY void Inittnode Pnode root Pnode left Pnode right char data 初始化结点 root left left root right right root data data void PreorderR Pnode proot 递归先序遍历算法 if proot printf 2c proot data PreorderR proot left PreorderR proot right void InorderR Pnode proot 递归中序遍历算法 二叉树的遍历 6 if proot InorderR proot left printf 2c proot data InorderR proot right void PostorderR Pnode proot 递归后序遍历算法 if proot PostorderR proot left PostorderR proot right printf 2c proot data void PreorderI Pnode proot Pstack pstack 非递归先序遍历算法 Initstack pstack 初始化栈 while proot Isempty pstack 如果栈空并且结点指针空 则结束循环 if proot printf 2c proot data if Isfull pstack 如果栈满不能执行入栈操作 printf 栈满 不能执行入栈操作 return Push pstack proot 入栈 proot proot left 指针指向左子 else if Isempty pstack 栈空时不能出栈 printf 栈空 不能执行出栈操作 return proot Pop pstack 执行出栈操作 proot proot right 指针指向右子 二叉树的遍历 7 void InorderI Pnode proot Pstack pstack 非递归中序遍历算法 Initstack pstack 初始化栈 while proot Isempty pstack 循环结束条件 if proot if Isfull pstack printf 栈满 不能执行入栈操作 return Push pstack proot 执行入栈操作 proot proot left 指针指向左子 else if Isempty pstack printf 栈空 不能执行出栈操作 return proot Pop pstack 出栈 printf 2c proot data 打印数据 proot proot right 指针指向右子 void PostorderI Pnode proot Pstack pstack 非递归后续遍历算法 int flags MAX 定义标志位栈 int p 1 初始化标志位栈 int flag 存放标志位 Initstack pstack 初始化栈 while proot Isempty pstack 循环结束条件 if proot if Isfull pstack printf 栈满 不能执行入栈操作 return flags p 0 标志位置 0 并入栈 二叉树的遍历 8 Push pstack proot 结点入栈 proot proot left 指针指向左子 else proot Pop pstack 指针出栈 flag flags p 相应标志位出栈 if flag 0 如果标志位为 0 表示右子还未访问过 flag 1 将标志位置 1 右子已访问 flags p flag 标志位入栈 Push pstack proot 结点入栈 proot proot right 指针指向右子 else printf 2c proot data 打印数据 proot NULL 将结点指针置空 void main Tnode A B C D E F G 声明结点变量 Stack stack 声明栈 Inittnode 初始化结点 Inittnode Inittnode Inittnode Inittnode Inittnode Inittnode printf 你定义的树的结构是 n 一下是调用相应的函数输出遍历结果 printf A B D C E F G n printf 下面是遍历结果 n printf 递归先序遍历 n PreorderR printf n printf 非递归先序遍历 n PreorderI printf n printf 递归中序遍历 n 二叉树的遍历 9 InorderR printf n printf 非递归中序遍历 n InorderI printf n printf 递归后序遍历 n PostorderR printf n printf 非递归后序遍历 n PostorderI printf n 四 四 运行结果运行结果 定义的树的结构为 A B D C EF G 遍历的结果 图 6 程序运行结果 五 五 遇到的问题及解决遇到的问题及解决 这部分我主要遇到如下两个问题 其内容和解决方法如下所列 执行程序时程序停止运行 其效果如图 二叉树的遍历 10 图 7 问题一截图 解决方法 看到程序停止运行 推测可能的原因 遇到死循环 参数设置不合理 或者结构体没有造好 首先对结构体进行了检查 各个成员声明正常无误 在对程序 进行调试 程序正常跳出循环 因此最可能是自定义函数的参数设置的不合理 因此 对调用的自定义函数进行相应的改动 将参数由具体类型改为指针类型后 程序正常 运行 程序不停的输出同一个结点的数据 其效果入图 图 8 问题二截图 解决方法 分析运行结果可知 第一不停的输出证明遇到了死循环 第二输出的 是同一个结点的数据 表示指针没有按预期进行指向 首先对程序进行调试 发现程 序没有添加循环结束条件 添加循环结束条件后 只能输出树的部分结点的数据 对 标志位进行修改后 程序运行正常 也能正确输出遍历结果 六 心得体会六 心得体会 通过这次作业真的受益匪浅 感触良多 二叉树的遍历 11 首先 要提高编程能力 必须多动手 多实践 而不是仅仅局限在书本上 更不 能眼高手低 眼高手低 懒得动手 这就犯了编程人员的大忌 大一