二叉树操作
发布网友
发布时间：2022-05-02 11:15
共2个回答
热心网友
时间：2022-06-19 17:05
源文件名：P3.cpp
功能：二叉树操作
*/
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stack>
using namespace std;
typedef int DataType;
const max=100;
typedef struct
{ DataType data[max];
int top;
}SeqStack;
struct BiTNode //二叉树结点类型
{
int data; //数据
int tem1,tem2; //辅助数据（实习题不用）
BiTNode *left; //左子树指针
BiTNode *right; //右子树指针
};
BiTNode *Tree; //本程序操作的二叉树根指针
int elem[max]; //存放原始数据
//从键盘输入个数和随机数种子，在数组elem中生成指定个数的数据，供其他程序使用，0表示数据结束
void init0(int list[]);
//在本程序所在的位置生成文本文件Map.txt，其中显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree);
//从键盘输入个数和随机数种子，以Tree为根指针，生成指定结点个数的二叉树，供其他程序使用
BiTNode *init1();
//主函数，显示功能菜单（包括生成二叉树、显示二叉树），键盘选择后执行对应功能
void Preorder(BiTNode *Tree);//先序遍历
void Inorder(BiTNode *Tree); //中序遍历
void Postorder(BiTNode *Tree); //后序遍历
int leafs(BiTNode *Tree); //总叶子数
void swap(BiTNode *Tree); //交换左右子树
int depth(BiTNode *Tree); //计算二叉树的深度
void search(BiTNode *T); //查找结点
BiTNode *CreatBST(int A[],int n) ;/
void insert(BiTNode *Tree);
int ELEM(int A[]);/
void del(BiTNode *Tree);/
void preorderl(BiTNode *Tree);/
void main()
{
//int list[max];
char choice;
while (1)
{
system("cls");
cout << "\n\n\n\n";
cout << "\t\t 二叉树操作 \n";
cout << "\t\t======================================";
cout << "\n\n";
cout << "\t\t a：生成二叉树 \n";
cout << "\t\t b：显示 \n";
cout << "\t\t c：先序遍历 \n";
cout << "\t\t d：中序遍历 \n";
cout << "\t\t e：后序遍历 \n";
cout << "\t\t f：计算二叉树中叶子结点的数目 \n";
cout << "\t\t g：计算二叉树的深度 \n";
cout << "\t\t h：左、右子树相互交换 \n";
cout << "\t\t i：构建以Tree为根指针的二叉排序树 \n";
cout << "\t\t j：查找结点 \n";
cout << "\t\t k：删除结点 \n";
cout << "\t\t l：不用递归，先序遍历以Tree为根指针的二叉树。 \n";
cout << "\t\t m：凹入表示法的表示以Tree为根指针的二叉树 \n";
cout << "\t\t n：用广义表表示以Tree为根指针的二叉树 \n";
cout << "\t\t o：从根结点开始，逐层从左到右输出各结点的数据 \n";
cout << "\t\t p：生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度 \n";
cout << "\t\t 0：退出 \n";
cout << "\n";
cout << "\t\t请选择：" << flush;
choice = getch();
system("cls");
switch(choice)
{
case 'a':
Tree=init1();
break;
case 'b':
showBinTree(Tree);
break;
case 'c':
cout<<"先序遍历："<<endl;
Preorder(Tree);
cout <<flush;
getch();
break;
case 'd':
cout<<"中序遍历："<<endl;
Inorder(Tree);
cout <<flush;
getch();
break;
case 'e':
cout<<"后序遍历："<<endl;
Postorder(Tree);
cout <<flush;
getch();
break;
case 'f':
cout<<"二叉树的总叶子结点数为："<<leafs(Tree)<<endl;
cout <<flush;
getch();
break;
case 'g':
cout<<"二叉树的深度为："<<depth(Tree)<<endl;
cout <<flush;
getch();
break;
case 'h':
swap(Tree);
cout<<"交换成功！"<<endl;
showBinTree(Tree);
cout <<flush;
getch();
break;
case 'i':
init0(elem);
Tree=CreatBST(elem,ELEM(elem));
break;
case 'j':
cout<<"请输入要查找的元素：";
search(Tree);
cout <<flush;
getch();
break;
case 'k':
cout<<"请输入需要删除的元素：";
del(Tree);
Tree=CreatBST(elem,ELEM(elem));
showBinTree(Tree);
cout <<flush;
getch();
break;
case 'l':
break;
case 'm':
break;
case 'n':
break;
case 'o':
break;
case 'p':
break;
case 'q':
break;
case 'r':
break;
case '0':
exit(0);
}
}
}
#include "BinT.h"
//公用的等待函数
void wait()
{
cout << "\n\n请按任意键继续" << flush;
getch();
}
void Preorder(BiTNode *T)//先序遍历
{
if(T)
{
cout<<T->data<<" ";
Preorder(T->left);
Preorder(T->right);
}
}
void Inorder(BiTNode *T)//中序遍历
{
if(T)
{
Inorder(T->left);
cout<<T->data<<" ";
Inorder(T->right);
}
}
void Postorder(BiTNode *T)//后序遍历
{
if(T)
{
Postorder(T->left);
Postorder(T->right);
cout<<T->data<<" ";
}
}
int leafs(BiTNode *T)//总叶子数
{
if(T==NULL)
return 0;
if((T->left==NULL) && (T->right==NULL))
return 1;
else
return leafs(T->left) + leafs(T->right);
}
int depth(BiTNode *T)//计算二叉树的深度
{
int n1,n2;
if(!T)
return 0;
else
{
n1=depth(T->left);
n2=depth(T->right);
if(n1>n2)
return n1+1;
else
return n2+1;
}
}
void swap(BiTNode *T)//交换左右子树
{
BiTNode *Q;
if(T)
{
Q = T->left ;
T->left = T->right ;
T->right = Q;
swap(T->left);
swap(T->right);
}
}
int InsertBST(BiTNode *&T,int k)
{
if (T==NULL)
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=k;
T->left=T->right=NULL;
return 1;
}
else if (k==T->data)
return 0;
else if (k<T->data)
return InsertBST(T->left,k);
else
return InsertBST(T->right,k);
}
BiTNode *CreatBST(int A[],int n)
{
BiTNode *bt=NULL;
int i=0;
while (i<n)
{
InsertBST(bt,A[i]);
i++;
}
return bt;
}
void search(BiTNode *T)//查找结点
{
int x,count=0;
cin>>x;
while(T!=NULL)
{
if(T->data==x)
{
count++;break;
}
else if(x<T->data)
{
T=T->left;
}
else
{
T=T->right;
}
}
if(count>0)
{
cout<<"查找到该元素。"<<endl;
}
else
{
cout<<"不存在该元素。"<<endl;
}
}
int ELEM(int A[])
{
int i;
for(i=0;elem[i]!=0;i++);
return i;
}
void del(BiTNode *T)
{
int x,i=0,j=-1;
cin>>x;
for(i;elem[i]!=0;i++)
{
if(elem[i]==x)
{
j=i;break;
}
}
if(j>=0)
{
for(j;elem[j]!=0;j++)
{
elem[j]=elem[j+1];
}
cout<<"删除成功。"<<endl;
}
else
{
cout<<"删除元素不存在。"<<endl;
}
}
void preorderl(BiTNode T) //不用递归，先序遍历以Tree为根指针的二叉树
{
SeqStack s;
s.top= -1;
while(T||s.top!= -1) //当前处理的子树不为空或栈不为空则循环
{
while(T)
{printf(“%c”,T->data);
s.top++;
s.data[s.top]=T;
T=T->left;
}
If(s.top>-1)
{T=pop(&s);
T=T->right;
}
}
}
/*
2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树。
3、编写递归算法，计算二叉树中叶子结点的数目。
4、编写递归算法，计算二叉树的深度。
5、编写递归算法，将二叉树中所有结点的左、右子树相互交换。
6、使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树。
7、在以Tree为根指针的二叉排序树中查找结点。
8、从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）。
9、不用递归，先序遍历以Tree为根指针的二叉树。
提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能。
10、用凹入表示法的表示以Tree为根指针的二叉树，例如：
// 324
// 123
// 746
// 690
// 567
11、用广义表表示以Tree为根指针的二叉树，例如
// (324(123(746(),()),(690(),())),(567(),()))
12、对以Tree为根指针的二叉树，从根结点开始，逐层从左到右输出各结点的数据。
提示：用数组 BiTNode *queue[max] 构成队列，利用这个队列实现功能
提高题：
13*、根据Huffman编码原理，使用数组elem中的随机数序列（以0表示结束，不包括0）作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。
14*、（1）随机生成二叉树。 （2）生成并保存先（后）序、中序输出序列。 （3）按照保存的一对输出序列恢复出二叉树。（4）生成先（后）序输出序列。
*/
热心网友
时间：2022-06-19 17:05
