二插树的创建和递归遍历和非递归遍历
二插树的创建和遍历(非递归形式实现:中序遍历 先序遍历 后续遍历 层次遍历 )#include<iostream>#include<cstdio>using namespace std;const int Maxsize=1000;typedef struct node{char ch;struct node *lchild,*rchild;bool flag;///标记后
二插树的创建和遍历(非递归形式实现:中序遍历 先序遍历 后续遍历 层次遍历 )
核心思想:
非递归先序遍历:由于先序遍历二叉树节点的次序是 根左右;所以利用我们按照根左右的次序访问。
(1) 当访问到一个A节点,就将A节点压入栈中,然后打印栈顶A节点的信息,然后访问A节点左子树左子树(假设他A在左子树),
一次重复(1)的操作(压入栈中,然后访问),直到出现一个节点没有左子树结束。
(2)将栈顶元素弹出栈,然后在取栈顶B,然后将B弹出栈,队B的右孩子进行(1)的操作,即压栈,然后访问左子树,最后在执行(2). 依次类推。
(需要注意的是当左子树走完后,会进行两次弹出栈的操作,分别是叶子节点和叶子的父亲节点)。
非递归中序:中序遍历二叉树的次序是 左根右
(1)首先是根节点压入栈中,然后依次访问节点的左子树,并将这些节点压入栈中
(2)当一条路径访问到叶子节点(就是依次走节点左子树这条路径)。
(3)访问栈顶节点的信息。并出栈///这里访问信息,你可以打印啥的
(4)对刚刚出栈的节点的右孩子节点执行(1)的操作后,然后执行(2)(3)(4)操作。
非递归的后序遍历:中序遍历二叉树的次序是 左右根
核心思想就是:对一个节点我们需要访问两次后 才能将其弹出栈。并访问它的信息。
所以我们在节点区域中加入了flag.
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=1000;
typedef struct node
{
char ch;
struct node *lchild,*rchild;
bool flag;///标记后序遍历中第几次被访问
} BTree_node;
BTree_node *Create_Tree()///创建二叉树
{
char ch;
BTree_node *Q[Maxsize];
int Front,Rear;
Front=1;
Rear=0;
BTree_node *root,*s;
root=NULL;
while((ch=getchar())!='#'){
s=NULL;
if(ch!='@')
{
s=(BTree_node*)malloc(sizeof(BTree_node));
s->ch=ch;
s->lchild=NULL;
s->rchild=NULL;
}
Q[++Rear]=s;
if(Rear==1)
root=s;
else
{
if(Q[Front]&&s)
{
if(Rear%2==0)
Q[Front]->lchild=s;
else
Q[Front]->rchild=s;
}
if(Rear%2==1)
Front++;
}
}
return root;
}
void Layer(BTree_node *root)
{
BTree_node *Q[Maxsize];
BTree_node *s;
int Rear=1,Front=0;
Q[Rear]=root;///根节点入队
while(Front<Rear)
{
Front++;
s=Q[Front];///去队头的节点信息
cout<<s->ch<<" ";
if(s->lchild!=NULL)
{
Rear++;
Q[Rear]=s->lchild;///与队头相连左孩子入队
}
if(s->rchild!=NULL)
{
Rear++;
Q[Rear]=s->rchild;///与对头相连的右孩子入队
}
}
}
void Nin_Order(BTree_node *root) ///非递归序中遍历
{
BTree_node *Stack[Maxsize];
BTree_node *s=root;///记录根节点
int top=-1;///栈顶
while(top!=-1||s!=NULL)
{
while(s!=NULL)
{
if(top==Maxsize) ///栈满
{
cout<<"overflow"<<endl;
return ;
}
else
{
top++;
Stack[top]=s;///节点入队
s=s->lchild;
}
}
s=Stack[top];
top--;
cout<<s->ch<<" ";
s=s->rchild;
}
}
void Per_Order(BTree_node *root){///非递归先序遍历, 根左右
BTree_node *Stack[Maxsize];
BTree_node *s=root;
int top=-1;
Stack[++top]=root;
while(top!=-1){
while((s=Stack[top])!=NULL){///取栈顶,找栈顶的左子树
cout<<s->ch<<" ";
if(top==Maxsize-1){
cout<<"overflow"<<endl;
return ;
}
else{
s=s->lchild;
Stack[++top]=s;
}
}
top--;///当一条左子树子树路劲遍历到叶节点,就出栈
if(top!=-1){
s=Stack[top];///取刚的叶节点的父节点
top--;///然后把父亲节点出栈,
Stack[++top]=s->rchild;///把父亲节点右孩子入栈
}
}
}
void Post_Order(BTree_node *root){///非递归后序遍历
BTree_node *p=root;///将根节点赋值给 p
BTree_node *Stack[Maxsize];///定义栈
BTree_node *temp;
int top=-1;///栈顶
while(p!=NULL||top!=-1){
while(p!=NULL)///遍历左子树路径
{
p->flag=true;///入栈标记一次
Stack[++top]=p;
p=p->lchild;
}
if(top!=-1){
temp=Stack[top];
top--;
if(temp->flag==true){///判断是第几次被访问到,则需要访问其节点的右子树。 才能符合 左右根 保证根 在其孩子节点后出栈
temp->flag=false;
Stack[++top]=temp;///所以还不能出栈,在一次入栈 , 还需要访问其右子树,
p=temp->rchild;///进入右子树
}
else///如果已经访问了两次,证明已经将左右子树访问, 则出栈
{
cout<<temp->ch<<" ";
p=NULL;
}
}
}
}
int main()
{
BTree_node *t=Create_Tree();
cout<<"层次遍历:";
Layer(t);///层次遍历or广度优先遍历
cout<<endl;
cout<<"非递归中序遍历:";
Nin_Order(t);
cout<<endl;
cout<<"非递归先序遍历:";
Per_Order(t);
cout<<endl;
cout<<"非递归后序遍历:";
Post_Order(t);
cout<<endl;
return 0;
}
二插树的创建和遍历:(递归形式实现: 中序遍历 先序遍历 后续遍历 层次遍历 )
#include<iostream>
#include<cstdio>
using namespace std;
const int Maxsize=10000;
typedef struct node{
char ch;
struct node *lchild,*rchild;
}Btree_node;
Btree_node* Create_Tree(){///利用对列创建二叉树
char ch;
Btree_node *Q[Maxsize];///节点队列
int Front,Rear;///队列的头尾指针
Btree_node *root,*s;
root =NULL;
Front=1,Rear=0;
while(scanf("%c",&ch)!=EOF){
if(ch=='#')
{
getchar();
break;
}
s=NULL;
if(ch!='@'){///为输入字符创建节点,需节点就不需要开空间
s=(Btree_node*)malloc(sizeof(Btree_node));
s->ch=ch;
// cout<<s->ch<<endl;
s->lchild=NULL;
s->rchild=NULL;
}
Rear++;///队列从 存值的索引从 1开始
Q[Rear]=s;
if(Rear==1){///此时还是空树
root=s;
}
else
{
if(s&&Q[Front]){///节点信息不为空,并且队列也不为空,连接
if(Rear%2==0)///偶数点左孩子节点
Q[Front]->lchild=s;
else///奇数点为右孩子节点
Q[Front]->rchild=s;
}
if(Rear%2==1)///连接完两个后,队头出队,开始为下一个节点连接孩子节点; 可以理解为 一对孩子
Front++;///出队
}
}
// cout<<"fdf";
return root;
}
void Per_Order(Btree_node *root){///先序遍历,根左右
if(root!=NULL){
// cout<<"fdf";
cout<<root->ch<<" ";
Per_Order(root->lchild);
Per_Order(root->rchild);
}
// cout<<"fdf";
}
void In_Order(Btree_node *root){///中序遍历,左根右
if(root!=NULL){
In_Order(root->lchild);
cout<<root->ch<<" ";
In_Order(root->rchild);
}
}
void Post_Order(Btree_node *root){///后续遍历
if(root!=NULL){
Post_Order(root->lchild);
Post_Order(root->rchild);
cout<<root->ch<<" ";
}
}
int main()
{
Btree_node*t=Create_Tree();
cout<<"先序遍历:";
Per_Order(t);
cout<<endl;
cout<<"中序遍历:";
In_Order(t);
cout<<endl;
cout<<"后序遍历:";
Post_Order(t);
cout<<endl;
return 0;
}
更多推荐
所有评论(0)