网页设计茶叶网站建设,动易 网站顶部导航 sitefactory,wordpress极验,微信小程序开发视频完整教程引言:
遍历二叉树#xff1a;指按某条搜索路径巡访二叉树中每个结点#xff0c;使得每个结点均被访问一次#xff0c;而且仅被访问一次。 除了层次遍历外#xff0c;二叉树有三个重要的遍历方法#xff1a;先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后…引言:
遍历二叉树指按某条搜索路径巡访二叉树中每个结点使得每个结点均被访问一次而且仅被访问一次。 除了层次遍历外二叉树有三个重要的遍历方法先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后序遍历
1先序遍历
void PreOrderTraverse(BiTree T)
{if(T){coutT-data;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}
}2中序遍历
void InOrderTraverse(BiTree T)
{ if(T){InOrderTraverse(T-lchild);coutT-data;InOrderTraverse(T-rchild);}
}
3后序遍历
void PostOrderTraverse(BiTree T)
{ if(T){ PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutT-data; }
} 2.非递归算法实现先序、中序、后序遍历
采用非递归算法则需要利用栈来实现对二叉树的遍历 1先序遍历非递归算法
void PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法
{LinkStack S;InitStack (S); BiTree p,q;pT;while(p||!StackEmpty(S)){if(p){Push(S,*p); coutp-data; //访问根节点 pp-lchild; //遍历左子树 }else{Pop(S,*q);pq-rchild; //遍历右子树 }}
}2中序遍历非递归算法
void InOrder_non_recursion(BiTree T)//中序遍历的非递归算法
{LinkStack S;InitStack (S); BiTree p; BiTree q; pT;while(p||!StackEmpty(S)){if(p){Push(S,*p); pp-lchild; //遍历左子树 }else{Pop(S,*q);coutq-data; //访问根节点 pq-rchild; //遍历右子树 }}
}3后序遍历非递归算法 采用非递归算法实现对二叉树的后序遍历会稍微复杂一些本算法借用了两个栈结构
void PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q; pT;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q-lchild){Push(l_S, *q-lchild);}if(q-rchild){Push(l_S,*q-rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);coutq-data;}
}3.完整代码
1、采用按照先序遍历的顺序建立二叉链表用‘#’表示空树。如图所示 2、先序遍历的递归与非递归算法的对比
#includeiostream
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{ //二叉树的存储结构TElemType data; // 数据域struct BiTNode *lchild; //左孩子指针struct BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode { //栈的存储结构BiTNode data; //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack S) { //栈初始化S NULL;return OK;
}Status Push(LinkStack S, BiTNode e) { //入栈LinkStack p;p new StackNode; //生成新结点if (!p) {return OVERFLOW;}p-data e; //将新结点数据域置为ep-next S; //将新结点插入栈顶S p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack S, BiTNode e) { //出栈LinkStack p;if (S NULL)return ERROR; //栈空e S-data; //将栈顶元素赋给ep S; //用p临时保存栈顶元素空间以备释放S S-next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) { //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree T){ //以先序次序创建二叉树 char ch; cinch;if(ch#)TNULL; else{Tnew BiTNode; //生成根结点T-datach; //根结点的数据域置为chCreateBiTree_PreOrder(T-lchild);//构造左子树CreateBiTree_PreOrder(T-rchild); //构造右子树}}void PreOrder(BiTree T){ //先序遍历的递归递归算法if(T){coutT-data;PreOrder(T-lchild);PreOrder(T-rchild);}
}void PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法
{LinkStack S;InitStack (S); BiTree p,q;pT;while(p||!StackEmpty(S)){if(p){Push(S,*p); coutp-data; //访问根节点 pp-lchild; //遍历左子树 }else{Pop(S,*q);pq-rchild; //遍历右子树 }}
}int main() {BiTree T;cout以先序次序创建二叉链表以#表示空子树endl;CreateBiTree_PreOrder(T);cout先序序列递归算法; PreOrder(T); cout\n先序序列非递归算法; PreOrder_non_recursion(T);return 0;
}
实验结果 3、中序遍历的递归与非递归算法的对比
#includeiostream
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{ //二叉树的存储结构TElemType data; // 数据域struct BiTNode *lchild; //左孩子指针struct BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode { //栈的存储结构BiTNode data; //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack S) { //栈初始化S NULL;return OK;
}Status Push(LinkStack S, BiTNode e) { //入栈LinkStack p;p new StackNode; //生成新结点if (!p) {return OVERFLOW;}p-data e; //将新结点数据域置为ep-next S; //将新结点插入栈顶S p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack S, BiTNode e) { //出栈LinkStack p;if (S NULL)return ERROR; //栈空e S-data; //将栈顶元素赋给ep S; //用p临时保存栈顶元素空间以备释放S S-next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) { //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree T){ //以先序次序创建二叉树 char ch; cinch;if(ch#)TNULL; else{Tnew BiTNode; //生成根结点T-datach; //根结点的数据域置为chCreateBiTree_PreOrder(T-lchild);//构造左子树CreateBiTree_PreOrder(T-rchild); //构造右子树}}void InOrder(BiTree T){ //中序遍历的递归递归算法if(T){InOrder(T-lchild);coutT-data;InOrder(T-rchild);}
}void InOrder_non_recursion(BiTree T)//中序遍历的非递归算法
{LinkStack S;InitStack (S); BiTree p; BiTree q; pT;while(p||!StackEmpty(S)){if(p){Push(S,*p); pp-lchild; //遍历左子树 }else{Pop(S,*q);coutq-data; //访问根节点 pq-rchild; //遍历右子树 }}
}int main() {BiTree T;cout以先序次序创建二叉链表以#表示空子树endl;CreateBiTree_PreOrder(T);cout中序序列递归算法; InOrder(T); cout\n中序序列非递归算法; InOrder_non_recursion(T);return 0;
}
实验结果
4、后序遍历的递归与非递归算法的对比
#includeiostream
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{ //二叉树的存储结构TElemType data; // 数据域struct BiTNode *lchild; //左孩子指针struct BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode { //栈的存储结构BiTNode data; //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack S) { //栈初始化S NULL;return OK;
}Status Push(LinkStack S, BiTNode e) { //入栈LinkStack p;p new StackNode; //生成新结点if (!p) {return OVERFLOW;}p-data e; //将新结点数据域置为ep-next S; //将新结点插入栈顶S p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack S, BiTNode e) { //出栈LinkStack p;if (S NULL)return ERROR; //栈空e S-data; //将栈顶元素赋给ep S; //用p临时保存栈顶元素空间以备释放S S-next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) { //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree T){ //以先序次序创建二叉树 char ch; cinch;if(ch#)TNULL; else{Tnew BiTNode; //生成根结点T-datach; //根结点的数据域置为chCreateBiTree_PreOrder(T-lchild);//构造左子树CreateBiTree_PreOrder(T-rchild); //构造右子树}}void PostOrder(BiTree T){ //后序遍历的递归递归算法if(T){PostOrder(T-lchild);PostOrder(T-rchild);coutT-data;}
}void PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q; pT;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q-lchild){Push(l_S, *q-lchild);}if(q-rchild){Push(l_S,*q-rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);coutq-data;}
}int main() {BiTree T;cout以先序次序创建二叉链表以#表示空子树endl;CreateBiTree_PreOrder(T);cout后序序列递归算法; PostOrder(T); cout\n后序序列非递归算法; PostOrder_non_recursion(T);return 0;
}
实验结果
4.结语
对于先序、中序和后序遍历如果采用非递归算法则需要借助栈来实现。对于二叉树而言还有一种大家更为熟知的遍历方式那就是层次遍历。实现对二叉树的层次遍历则需要借助队列来实现。实现对二叉树的层次遍历可以参考C实现二叉树的层次遍历 欢迎大家一起来交流~
