用递归非递归两种方法遍历二叉树

用递归 非递归两种方法遍历二叉树 1 数据结构 双语 数据结构 双语 项目文档报告项目文档报告 用递归 非递归两种方法遍历二叉树用递归 非递归两种方法遍历二叉树 专专 业 业 计算机科学与技术计算机科学与技术 班班 级 级 指导教师 指导教师 姓姓 名 名 学学 号 号 用递归 非递归两种方法遍历二叉树 2 目目 录录 一 设计思想 03 二 算法流程图 04 三 源代码 06 四 运行结果 12 五 遇到的问题及解决 14 六 心得体会 15 用递归 非递归两种方法遍历二叉树 3 一 设计思想一 设计思想 1 递归 1 主函数 main 主程序要包括 定义的二叉树 T 建树函数 先序遍 历函数 中序遍历函数 后序遍历函数 2 建树函数定义一个输入的数是字符型的 当 ch 为空时 T 就为空值 否则的话就分配空间给 T T 就指向它的结点 然后左指针域指向左孩子 右指 针指向右孩子 若还有 继续调用 依次循环下去 直到 ch 遇到空时 结束 最后要返回建立的二叉树 T 3 先序遍历函数根据先序遍历规则 当 T 为非空时 先输出结点处的数 据 指针指向左 右孩子 依次进行下去 4 中序遍历函数根据中序遍历规则 当 T 为非空时 先左指针指向左孩 子数据 然后输出结点处的数据 再右指针指向右孩子 依次进行下去 5 后序遍历函数根据后序遍历规则 当 T 为非空时 先右指针指向右孩 子 然后左指针指向左孩子 最后输出结点处的数据 依次进行下去 2 非递归 1 跟递归遍历二叉树的前提一样 首先应该创建一个二叉树 同样使 用先序递归的方式创建二叉树 2 然后是中序 先序 后序非递归遍历二叉树 3 中序非递归遍历二叉树的思想是 首先是根节点压栈 当根节点的 左子树不是空的时候 左子树压栈 直到左子树为空的时候 不再压栈 将栈 顶元素出栈 访问栈顶元素 并将栈顶的右子树进栈 当右子树的左子树不是 空的时候 左子树一直进栈 直到左子树为空 则不再进栈 重复上面的操作 直到栈空的时候 4 先序非递归遍历二叉树的思想是 首先是根节点进栈 然后当栈不为 空的时候 将栈顶元素出栈 然后访问 同时将出栈元素的右子树进栈 左子 树进栈 重复上面的操作 直到栈为空 5 后序非递归遍历二叉树的思想 首先是根节点进栈 当根节点的左子 树不为空的时候 左子树进栈 直到左为空的时候 左子树不再进栈 指针指 向的是右子树 当右子树为空的时候 直接访问根节点 当右子树不为空的时 候 则右子树的指针进栈 当右子树的左子树不为空的时候 则左也进栈 直 到左为空 重复上面的操作 直到栈为空的时候 则遍历树完成 用递归 非递归两种方法遍历二叉树 4 二 算法流程图二 算法流程图 1 1 递归递归 用递归 非递归两种方法遍历二叉树 5 2 非递归非递归 用递归 非递归两种方法遍历二叉树 6 三 源代码三 源代码 1 1 递归递归 include stdio h include conio h include include typedef struct node char data struct node lchild rchild BinTnode typedef BinTnode BinTree 定义二叉树类型的指针 先序创建二叉树 int CreateBinTree BinTree T char ch T BinTree malloc sizeof BinTnode if T printf overflow do ch getchar if ch T NULL return 0 else T data ch CreateBinTree CreateBinTree return 1 while ch 0 中序递归遍历 void InorderTransverse BinTree s if s InorderTransverse s lchild printf c s data InorderTransverse s rchild 先序递归遍历二叉树 用递归 非递归两种方法遍历二叉树 7 void PreOrderTranverseTree BinTree s if s printf c s data PreOrderTranverseTree s lchild PreOrderTranverseTree s rchild 后序递归遍历二叉树 void PostOrderTranverseTree BinTree s if s PreOrderTranverseTree s lchild PreOrderTranverseTree s rchild printf c s data 主方法 void main BinTree T printf 请按照先序的顺序输入要创建的树 n CreateBinTree 中序序列创建二叉树 printf 中序递归遍历的序列是 InorderTransverse T printf n 先序递归遍历 printf 先序递归遍历的序列是 PreOrderTranverseTree T printf n 后序递归遍历 printf 后序递归遍历的序列是 PostOrderTranverseTree T printf n 用递归 非递归两种方法遍历二叉树 8 2 2 非递归非递归 include stdio h include conio h include include typedef struct node char data struct node lchild rchild BinTnode typedef BinTnode BinTree 定义二叉树类型的指针 typedef struct BinTree data 100 int top SeqStack void initStack SeqStack S S top 1 void Push SeqStack S BinTree x if S top 100 1 printf the stack is overflow else S top S top 1 S data S top x int Pop SeqStack S BinTree p if S top 1 printf the stack is underflow return 0 else p S data S top S top return 1 int EmptyStack SeqStack S if S top 1 return 1 else return 0 栈不空的情况 int GetTop SeqStack S BinTree p 用递归 非递归两种方法遍历二叉树 9 if S top 1 printf the stack is empty return 0 else p S data S top return 1 char visit BinTree p return p data 创建二叉树 int CreateBinTree BinTree T char ch T BinTree malloc sizeof BinTnode if T printf overflow else do ch getchar if ch T NULL return 0 else T data ch CreateBinTree CreateBinTree return 1 while ch 0 中序非递归遍历 void InorderTransverse BinTree T SeqStack S BinTree p initStack 初始化栈 printf 中序非递归序列是 Push 根指针进栈 T 为指向二叉树的指针 while EmptyStack S 栈不是空的情况 while GetTop S gettop 得到的结果也必须是一棵子树才行 进 栈应该进的是树根的指针 Pop 用递归 非递归两种方法遍历二叉树 10 if EmptyStack S printf c visit p Pop printf c visit p Push 先序非递归遍历 void PreorderTransverse BinTree T SeqStack S BinTree p initStack 初始化栈 Push 根指针进栈 T 为指向二叉树的指针 printf 先序非递归序列是 while EmptyStack S Pop 根节点出栈 if p NULL printf c visit p Push Push 后序非递归遍历 void PostorderTransverse BinTree T SeqStack S BinTree p q initStack 初始化栈 p T printf 后序非递归序列是 while p EmptyStack S 跳出 while 循环的原因是因为左子树或者右子树 为空了 if p q while p NULL Push if p lchild NULL p p lchild else p p rchild if EmptyStack S break GetTop S if q rchild p 进栈的是右子树 Pop 用递归 非递归两种方法遍历二叉树 11 printf c visit p p q else p q rchild 主方法 void main BinTree T printf 请按照先序的顺序输入创建的树 n 创建树 CreateBinTree 中序非递归遍历 InorderTransverse T printf n 先序非递归遍历 PreorderTransverse T printf n 后序非递归遍历 PostorderTransverse T 四 运行结果四 运行结果 1 递归递归 输入 用递归 非递归两种方法遍历二叉树 12 结果 2 非递归非递归 输入 结果 用递归 非递归两种方法遍历二叉树 13 五 遇到的问题及解决五 遇到的问题及解决 经过一个星期的写代码 我遇到了很多问题 并一一解决了 比如 1 创建二叉树时 void createBiTree BiTNode T 和 void createBiTree BiTNode T 没分清楚区别 后来查找资料找到 void createBiTree BiTNode T 是将结点的指针 地址 传递 到函数中进行处理 void createBiTree BiTNode T 是将结点指针的引用传递到函数处理 才理解清楚 2 在写非递归算法时 一直逻辑混乱 后来查找了