二叉树基本操作
发布网友
发布时间：2022-04-22 07:52
共2个回答
热心网友
时间：2022-04-11 21:10
试试，挺好的！还有菜单！
#include <iostream>
using namespace std;
struct Node
{
char data;
Node *left;
Node *right;
}*BiTree;
class Tree
{
public:
void Setroot();//设置二叉树的根节点
void CreateTree(Node*); //先序递归创建二叉树函数
void DeleteTree(Node*);//二叉树的销毁函数
void PostOrderTraverse(Node*);//后续递归遍历二叉树函数
void InOrderTraverse(Node*);//中序非递归遍历二叉树函数
void LevelOrder(Node *);//层次遍历二叉树函数
void leaves1(Node *);//输出二叉树的叶子节点函数
void leaves2(Node *);//输出二叉树的二叉节点函数
void leaves3(Node *);//输出二叉树的一叉节点函数
//int Showleaves(Node *);//输出二叉树的叶子节点个数函数
int Depthoftree(Node *);//计算二叉树的深度函数
bool Iscomplete(Node *);//判断二叉树是否为完全二叉树函数
bool Isp(Node *);//判断二叉树是否已初始化
~Tree(){DeleteTree(root);}//Tree的析构函数
static Node *root;//定义二叉树的根节点为静态变量
};
Node* Tree::root=0;//初始化二叉树的根节点
void Tree::Setroot()//设置二叉树的根节点
{
cout<<"输入树的根节点(如果为空输入#):\t";
root=new Node;
cin>>root->data;
CreateTree(root);//调用CreateTree()函数生成二叉树
}
bool Tree::Isp (Node *p=root)//判断二叉树是否已存在
{
if(p){return true;}
else return false;
}
void Tree::CreateTree(Node *p)//先序递归创建二叉树
{
if(p)
{
char x,y; Node *q;
cout<<"输入节点"<<p->data<<"的左孩子和右孩子:\t";
cin>>x>>y;
if(x=='#')
p->left=0;
else
{
q=new Node;
q->data=x;
p->left=q;
}
if(y=='#')
p->right=0;
else
{
q=new Node;
q->data=y;
p->right=q;
}
CreateTree(p->left);
CreateTree(p->right);
}
}
void Tree::InOrderTraverse(Node *p=root)//中序非递归遍历二叉树
{
Node *q;
Node *stack[100];
int top=0;
q=p;
if(p)
{
while(q||top!=0)
{
while(q)
{
stack[top++]=q;
q=q->left ;
}
q=stack[--top];
cout<<q->data <<" ";
q=q->right ;
}
}
else{cout<<"请先建立二叉树!!!"<<endl;}
}
void Tree::LevelOrder(Node *p=root)//层次遍历二叉树
{
Node stack[100];//设置堆栈
int front=0,rear=0;
Node q;
if(p)
{
stack[rear]=*p;
rear=(rear+1)%100;
}
while(front!=rear)
{
p=&stack[front];
front=(front+1)%100;
cout<<p->data<<" ";
if(p->left )
{
stack[rear]=*p->left ;
rear=(rear+1)%100;
}
if(p->right )
{
stack[rear]=*p->right ;
rear=(rear+1)%100;
}
}
}
void Tree::PostOrderTraverse(Node *p=root)//后续递归遍历二叉树
{
if(p)
{
PostOrderTraverse(p->left);
PostOrderTraverse(p->right);
cout<<p->data<<" ";
}
}
void Tree::DeleteTree(Node *p=root)//销毁二叉树
{
if(p)
{
DeleteTree(p->left);
DeleteTree(p->right);
delete p;
}
}
int Tree::Depthoftree (Node *p=root)//计算二叉树的深度
{
if(p)
{
int h1=Depthoftree(p->left );
int h2=Depthoftree(p->right );
return(1+(h1>h2?h1:h2));
}
else return 0;
}
/*int Tree::Showleaves (Node *p=root)//计算二叉树的叶子结点个数
{
int rnum,lnum;
int i=0;
if(p)
{
if((p->left ==NULL)||(p->right==NULL))
{
return 1;
}
else
{
rnum=Showleaves(p->left);
lnum=Showleaves(p->right);
return rnum+lnum;
}
}
else return 0;
}*/
void Tree::leaves1 (Node *p=root)//输出二叉树的叶子节点
{
if(p)
{
if((p->left ==NULL)&&(p->right==NULL))
{
cout<<p->data <<" ";
}
leaves1(p->left );
leaves1(p->right );
}
}
void Tree::leaves2 (Node *p=root)//输出二叉树的二叉节点
{
if(p)
{
if((p->left !=NULL)&&(p->right!=NULL))
{
cout<<p->data <<" ";
}
leaves2(p->left );
leaves2(p->right );
}
}
void Tree::leaves3(Node *p=root)//输出二叉树的一叉节点
{
if(p)
{
if(((p->left !=NULL)&&(p->right==NULL))||((p->left==NULL)&&(p->right!=NULL)))
{
cout<<p->data <<" ";
}
leaves3(p->left );
leaves3(p->right );
}
}
bool Tree::Iscomplete(Node *p=root)//判断二叉树是否为完全二叉树
{
Node stack[100],*q,*r;/*定义队列*/
int front=0,rear=0;
if(p)
{
stack[rear]=*p;
rear=(rear+1)%100;
}
/*此while的作用是在根节点在队内的初始情况下开始*/
/*按层次遍历二叉树*/
/*只遍历左右子树都有的节点 while结束时 p指向第一个例外节点*/
while(rear!=front)
{
q=&stack[front];
front=(front+1)%100;
if((rear+1)%100!=front&&p->left!=NULL&&p->right!=NULL) /*当队不满，*/
{
stack[rear]=*p->left;
rear=(rear+1)%100;
stack[rear]=*p->right;
rear=(rear+1)%100;
}
else break;
}
/*经前面的while，p肯定指向第一个没有双子的节点*/
/*此时又分四种情况*/
if(p->left==NULL&&p->right!=NULL)return false; /*第一种:有右无左 肯定不是完全二叉树*/
else if(p->left!=NULL&&(p->left->left!=NULL||p->left->right!=NULL))
return false; /*第二种:有左无右但左子树还有子树 排除*/
/*第三种:有左无右 左也无子,*/
/*但在继续按层次遍历过程中*/
/*发现后来的某个节点有子树,排除*/
else
{
while(rear!=front)
{
q=&stack[front];
front=(front+1)%100;
if(p->left!=NULL||p->right!=NULL) return false;
}
} /*经过层层筛选,剩下的就是真金*/
//return true;
}
void main()
{
int /*leave=0,*/depth=0;
bool key,t=true;//key接受Isp()的返回值；t接受Iscomplete()的返回值
Tree tree;
int select=0;
while(select!=8)
{
cout<<endl;
cout<<" ————————————————————————"<<endl;
cout<<" ╭————————请选择操作号————————╮"<<endl;
cout<<" ∣ ∣"<<endl;
cout<<" ├——————————————————————┤"<<endl;
cout<<" ∣ 1.建立一棵二叉树（先序） ∣"<<endl;
cout<<" ∣ 2.递归后序遍历二叉树 ∣"<<endl;
cout<<" ∣ 3.中序非递归遍历二叉树 ∣"<<endl;
cout<<" ∣ 4.层次遍历二叉树 ∣"<<endl;
cout<<" ∣ 5.列出该树的叶子节点、二叉节点、一叉节点∣"<<endl;
cout<<" ∣ 6.求出树的深度 ∣"<<endl;
cout<<" ∣ 7.判断该树是否是完全二叉树 ∣"<<endl;
cout<<" ∣ 8.退出 ∣"<<endl;
cout<<" ╰——————————————————————╯"<<endl;
cout<<" ————————————————————————"<<endl;
cout<<" 请选择您要服务的类别: " ;
cin>>select;
switch(select)
{
case 1:
tree.DeleteTree ();
tree.Setroot (); break;
case 2:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的后序遍历结果为:";
tree.PostOrderTraverse ();
cout<<endl<<"***************************"<<endl;break;
case 3:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的中序遍历结果为:";
tree.InOrderTraverse ();
cout<<endl<<"***************************"<<endl;break;
case 4:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
cout<<"树的层次遍历结果为:";
tree.LevelOrder ();
cout<<endl<<"***************************"<<endl;break;
case 5:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树!!!"<<endl;break;}
/*leave=tree.Showleaves ();
cout<<"***************************"<<endl;
cout<<"叶子结点数为：";
cout<<leave<<endl;*/
cout<<"叶结点为：";
tree.leaves1 ();
cout<<endl;
cout<<"二叉结点为：";
tree.leaves2 ();
cout<<endl;
cout<<"一叉结点为：";
tree.leaves3 ();
cout<<endl<<"***************************"<<endl;break;
case 6:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树*******!!!"<<endl;break;}
depth=tree.Depthoftree();
cout<<"***************************"<<endl;
cout<<"树的深度为："<<depth<<endl;
cout<<endl<<"***************************"<<endl;break;
case 7:
key=tree.Isp ();
if(!key){cout<<"*****请先建立二叉树******!!!"<<endl;break;}
cout<<"***************************"<<endl;
t=tree.Iscomplete() ;
if(t){cout<<"是完全二叉树！"<<endl;}
else{cout<<"不是完全二叉树！"<<endl;}
cout<<endl<<"***************************"<<endl;break;
case 8:break;
default:
cout<<"警告!命令错误,请重新输入!!!"<<endl;
}
if(select == 8)
cout<<"系统已经退出!"<<endl;
break;
}
exit(1);
热心网友
时间：2022-04-11 22:28
晕，这些东东在数据结构课本上都有啊，照抄就可以啊，用递归只有几句代码而已
