文档介绍：一、设计思想
在本次试验中,主要用两种方法遍历树,一种是递归方法遍历树,另一种是用非递归方法来遍历树。
递归遍历树:
先序遍历二叉树,若二叉树为空,则空操作否则执行,首先,访问根节点,然后先序遍历根结点的左子树,最后先序遍历根节点的右子树。
中序遍历二叉树,若二叉树为空,则空操作否则执行,首先,中序遍历根节点的左子树,然后访问根节点,最后中序遍历根节点的右子树。
后序遍历二叉树,若二叉树为空,则空操作否则执行,首先后序遍历根节点的左子树,然后后序遍历根节点的右子树,最后访问根节点。
非递归遍历:
先序遍历二叉树:①初始化一个栈,存放二叉结点指针。②t(为二叉树结点指针)当t不为空或者栈不为空,重复执行:输出t的数据,并将t入栈,t=t->lchild(循环直到遍历完当前子树的根结点和其左孩子)。③如果栈不为空,弹出栈顶并赋给t,,t=t->rchild。转步骤②。④若栈空,遍历结束。
中序遍历二叉树:①初始化一个栈,用来存放二叉结点指针。②t(为二叉结点指针)当t不为空或者栈不空时,重复执行③④。③当t不为空时,反复执行:将t入栈,t=t->lchild(子树根结点全部入栈)。④t为空但栈不为空,弹栈并赋给t,将t的数据输出,t=t->rchild。
后序遍历二叉树:①初始化一个栈(存放二叉结点)和一个数组(存放标志:进入右子树的标志),栈和数组的下标都为栈指针的值。②当t(为二叉结点指针)当t不为空或者栈不空时,重复执行③④⑤⑥。③当t不为空,反复执行:栈顶指针top加1,t入栈,数组赋值为0,t=t->lchild。④当(>-1)&&([]==1)成立时,反复执行:弹栈顶元素,赋给t,输出t的数据值,栈顶指针要减1。⑤如果栈不空,弹栈顶元素,赋给t,将数组下标为栈顶指针的元素的值设为1,t=t->rchild。⑥如果③④⑤都不成立时,将t赋值为空。
二、算法流程图
先序递归遍历:若二叉树为空,则空操作否则执行,首先,访问根节点,然后先序遍历根结点的左子树,最后先序遍历根节点的右子树。
输出t指向的数据
t为指向根节点的指针变量
开始
t!=null
t=t->lchild
t=t->rchild
是
否
结束
图1递归先序遍历二叉树算法流程图
后序递归遍历:若二叉树为空,则空操作否则执行,首先后序遍历根节点的左子树,然后后序遍历根节点的右子树,最后访问根节点。
输出t指向的数据
t为指向根节点的指针变量
开始
t!=null
t=t->lchild
t=t->rchild
是
否
结束
图2递归后序遍历二叉树算法流程图
先序非递归遍历:②t(为二叉树结点指针)当t不为空或者栈不为空,重复执行:输出t的数据,并将t入栈,t=t->lchild(循环直到遍历完当前子树的根结点和其左孩子)。③如果栈不为空,弹出栈顶并赋给t,,t=t->rchild。转步骤②。④若栈空,遍历结束。
开始
t!=null||!=-1
t!=null
++;t进栈,t=t->lchild
栈不空
弹栈赋给t, 输出t->data,t=t->lchild
是
否
是
是
否
结束
图3非递归先序遍历二叉树算法流程图
后