数据结构-树-二叉树的基本操作(递归和非递归遍历,深度)
程序员文章站
2022-06-07 07:54:39
...
1.需求
- 递归实现层序、先序、中序、后序遍历
- 非递归实现层序、先序、中序、后序遍历
- 求树的深度
2.实现代码
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
using namespace std;
typedef struct BiTNode
{ char data; //使用字符串来建树
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//建树
void Create(BiTree &T)
{//例子ABD##E##CF###
char ch;
cin>>ch;
if(ch=='#')
T=NULL; //递归结束
else{
T=new BiTNode;
T->data=ch;
Create(T->lchild); //递归建左子树
Create(T->rchild); //递归建右子树
}
}
//层序遍历
void levleorder(BiTree T)
{
queue<BiTree> B; //队列辅助遍历
cout<<"层序遍历:";
BiTree front;
if(T==NULL) return;
B.push(T);
while(!B.empty())
{
front=B.front();
B.pop();
if(front->lchild)
B.push(front->lchild); //左孩子不为空,左孩子进入队列
if(front->rchild)
B.push(front->rchild); //右孩子不为空,右孩子进入队列
cout<<front->data<<"->";
}
cout<<endl;
}
//递归前序遍历
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
{
cout<<"#"<<"->";
return ;
}else{
cout<<T->data<<"->"; //访问根节点
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//非递归前序遍历
void PreOrderLoop(BiTree T)
{
stack<BiTree> s;
BiTree cur,top;
cur=T;
while(cur!=NULL||!s.empty())
{
while(cur!=NULL)
{
cout<<cur->data<<"->";
s.push(cur);
cur=cur->lchild;
}
top=s.top();
s.pop();
cur=top->rchild;
}
}
//递归中序遍历
void InOrderTraverse(BiTree T)
{
if(T==NULL)
{
cout<<"#"<<"->";
return;
}else{
InOrderTraverse(T->lchild);
cout<<T->data<<"->";
InOrderTraverse(T->rchild);
}
}
//非递归中序遍历
void InOrderLoop(BiTree T)
{
stack<BiTree>s;
BiTree cur;
cur=T;
while(cur!=NULL||!s.empty())
{
while(cur!=NULL)
{
s.push(cur);
cur=cur->lchild;
}
cur=s.top();
s.pop();
cout<<cur->data<<"->";
cur=cur->rchild;
}
}
//后序递归遍历
void PostOrderTraverse(BiTree T)
{
if(T==NULL){
cout<<"#"<<"->";
}else{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<"->";
}
}
//后序非递归遍历
void PostOrderLoop(BiTree T)
{
stack<BiTree> s;
BiTree cur ,top,last=NULL;
cur=T;
while(cur!=NULL||!s.empty())
{
while(cur!=NULL)
{
s.push(cur);
cur=cur->lchild;
}
top=s.top();
if(top->rchild==NULL||top->rchild==last){
s.pop();
cout<<top->data<<"->";
last=top;
}else{
cur=top->rchild;
}
}
}
//求树的深度
int TreeDeep(BiTree T)
{
int deep=0;
if(T)
{
int leftdeep=TreeDeep(T->lchild);
int rightdeep=TreeDeep(T->rchild);
deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
int NodeCount(BiTree T){
if(T == NULL ) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int main()
{
//建树
BiTree t;
cout<<"请输入建树序列:";
Create(t);
//层序遍历
levleorder(t);
//递归前序遍历
cout<<"递归前序遍历:";
PreOrderTraverse(t);
cout<<endl;
//非递归前序遍历
cout<<"非递归前序遍历:";
PreOrderLoop(t);
cout<<endl;
//递归中序遍历
cout<<"递归中序遍历:";
InOrderTraverse(t);
cout<<endl;
//非递归中序遍历
cout<<"非递归中序遍历:";
InOrderLoop(t);
cout<<endl;
//递归后序遍历
cout<<"递归后序遍历:";
PostOrderTraverse(t);
cout<<endl;
//非递归后续遍历
cout<<"非递归后序遍历:";
PostOrderLoop(t);
cout<<endl;
//树的深度
int d=TreeDeep(t);
cout<<"树的深度:"<<d<<endl;
//树的结点个数
int n=NodeCount(t);
cout<<"树的结点个数:"<<n<<endl;
return 0;
}
3.运行结果
上一篇: 数据结构——递归实现二叉树
下一篇: JVM内存结构、GC算
推荐阅读