数据结构二叉树相关操作代码

75 阅读 0 评论 50 点赞

我是靠谱客的博主现实发箍，最近开发中收集的这篇文章主要介绍数据结构二叉树相关操作代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include
#include
#define size 99
using namespace std;

typedef struct BiTNode{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;

}BiTNode,*BiTree;

typedef struct SeQueue
{
BiTree data[size]; // 二叉链表类型的指针数组
int front,rear; //队首指针、队尾指针
}SeQ,*SeQue;

// 初始化循环队列
void InitQue(SeQue Q)
{
Q->front=Q->rear=0;
}

// 判队列空
int EmptyQue(SeQue Q)
{
if(Q->front==Q->rear)
return 1;
else
return 0;
}

// 入队列
int EnQue(SeQue Q,BiTree T)
{
if((Q->rear+1)%size==Q->front)
{
printf(“队列已满！n”); // 队列满，入队失败。
return 0;
}
else
{
Q->rear=(Q->rear+1)%size;
Q->data[Q->rear]=T;
return 1; // 入队列成功
}
}
// 出队列
int OutQue(SeQue Q)
{
if(EmptyQue(Q)) // 判断队列是否为空
{
printf(“队列空！n”);
return 0;
}
else
{
Q->front=(Q->front+1)%size; // 不为空，出队列。
return 1;
}
}
// 取队列首元素
BiTree Gethead(SeQue Q)
{
if(EmptyQue(Q)) // 判断队列是否为空
return 0;
else
return Q->data[(Q->front+1)%size];
}

// 层次遍历二叉树
void LevelOrder(BiTree T)
{
BiTree p;
SeQ Q;
InitQue(&Q); //初始化队列
if(T!=NULL)
{
EnQue(&Q,T); // 根结点入队列
while(!EmptyQue(&Q))
{
p=Gethead(&Q);
OutQue(&Q); // 结点出队列
printf("%c ",p->data); // 被访问结点
if(p->lchild!=NULL)
EnQue(&Q,p->lchild);// 左孩子结点入队列
if(p->rchild!=NULL)
EnQue(&Q,p->rchild);// 右孩子结点入队列
}
}
}

// 初始化二叉树
void Init(BiTree &T)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->lchild = NULL;
T->rchild = NULL;
}

// 先序创建二叉树
void CreateBiTree(BiTree &T)
{
char ch;
cin>>ch;
if(ch == ‘#’)
T = NULL;
else
{
T = new BiTNode;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

// 先序遍历二叉树
void PreOrderTraverse(BiTree T)
{
if(T)
{
cout<data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

// 中序遍历二叉树
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<data;
InOrderTraverse(T->rchild);
}
}

// 后序遍历二叉树
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<data;
}
}

//统计树的叶子结点个数并输出叶子结点
int CountLeaves(BiTree T,int &NumOfLeaves)
{
if (T)
{
if(T->lchildNULL&&T->rchildNULL)
{
NumOfLeaves++;
cout<<“第”<<NumOfLeaves<<“个叶子结点为：”<data<<endl;
}
CountLeaves(T->lchild,NumOfLeaves);
CountLeaves(T->rchild,NumOfLeaves);
return 1;
}
else
return 0;
}

// 计算二叉树深度
int Depth(BiTree T)
{
int m = 0;
int n = 0;
if(T == NULL)
return 0;
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if(m>n)
return (m+1);
else
return (n+1);
}
}
// 菜单
int Menu_Select()
{
int s;
getchar();
cout<<“请选择要执行的操作：”<<endl<<endl;
cout<<“☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆◎★★★★★★★★★★★★★★★★★★★”<<endl;
cout<<“◆ 1. 先序遍历二叉树 ◇”<<endl;
cout<<“◆ 2. 中序遍历二叉树 ◇”<<endl;
cout<<“◆ 3. 后序遍历二叉树 ◇”<<endl;
cout<<“♀ 4. 按层次遍历二叉树 ♂”<<endl;
cout<<“◇ 5. 输出二叉树所有的叶子节点和叶子节点个数 ◆”<<endl;
cout<<“◇ 6. 输出二叉树的深度 ◆”<<endl;
cout<<“◇ 0. 退出程序 ◆”<<endl;
cout<<“★★★★★★★★★★★★★★★★★★★◎☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆”<<endl;
cin>>s;
return s;
}

// 主函数
int main()
{
BiTree bt;
char op;
int choice;
int n = 0; // 叶子结点书初始化为0

Init(bt);
cout<<"按先序次序输入二叉树中结点的值（一个字符），以'#'结束："<<endl;
CreateBiTree(bt);

do{
	choice = Menu_Select();
	switch (choice)
	{
		case 0:
			exit (0);
		case 1:
			cout<<"先序遍历二叉树的结果为："; 
            PreOrderTraverse(bt);
            cout<<endl;
            break;
        case 2:
            cout<<"中序遍历二叉树的结果为："; 
            InOrderTraverse(bt);
            cout<<endl;
            break;
        case 3:
        	cout<<"后序遍历二叉树的结果为：";
			PostOrderTraverse(bt);
			cout<<endl;
			break;
		case 4:
		    cout<<"按层次遍历二叉树的结果为："; 
            LevelOrder(bt);
            cout<<endl;
            break;
        case 5:
        	CountLeaves(bt,n);
        	cout<<"叶子结点总数为："<<n<<endl;
			break;
		case 6:
			 cout<<"二叉树的深度为："<<Depth(bt)<<endl; 
		     break;	
		default	:
			cout<<"输入有误！"<<endl; 
	} 
}while(choice); 

return 0;

}