/*
源文件名: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>
struct BiTNode //二叉树结点类型
{
int data; //数据
int tem1,tem2; //辅助数据(实习题不用)
BiTNode *left; //左子树指针
BiTNode *right; //右子树指针
}; BiTNode *Tree; //本程序操作的二叉树根指针
const max=100;
int elem[max]; //存放原始数据
int a=1,b=1,c;int i=0,j=0;int x;
BiTNode *stack[max];
//从键盘输入个数和随机数种子,在数组elem中生成指定个数的数据,供其他程序使用,0表示数据结束
void init0(int list[]);
void Preorder(BiTNode *Tree); //先序遍历
void Inorder(BiTNode *Tree); //中序遍历
void Postorder(BiTNode *Tree); //后序遍历
int leafs(BiTNode *Tree); //计算总叶子数
int depth(BiTNode *Tree); //二叉树的深度
void swap(BiTNode *Tree); //交换左右子树
void BuildBST(BiTNode **Tree); //建立二叉排序树
void search(BiTNode *Tree);
void del(BiTNode *Tree);
void delUsing(BiTNode *Tree);
void ListBinTree(BiTNode *Tree);//用广义表表示二叉树
void DisplayBinTree(BiTNode *Tree,int j);//用凹入表表示二叉树
//在本程序所在的位置生成文本文件Map.txt,其中显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree); //从键盘输入个数和随机数种子,以Tree为根指针,生成指定结点个数的二叉树,供其他程序使用
//BiTNode *init1(); #include "BinT.h"
//主函数,显示功能菜单(包括生成二叉树、显示二叉树),键盘选择后执行对应功能
void main()
{
char choice;
while (1)
{
system("cls");
cout << "\n\n\n\n";
cout << "\t\t 二叉树操作 \n";
cout << "\t\t=========================================";
cout << "\n\n";
cout << "\t\t 1:建立二叉树 \n";
cout << "\t\t 2:遍历二叉树 \n";
cout << "\t\t 3:计算总叶子数 \n";
cout << "\t\t 4:计算二叉树的深度 \n";
cout << "\t\t 5:交换左右子树 \n";
cout << "\t\t 6:生成二叉排序树 \n";
cout << "\t\t 7:在二叉排序树中查找结点 \n";
cout << "\t\t 8:在二叉排序树中删除结点 \n";
cout << "\t\t a:用凹入表表示二叉树 \n";
cout << "\t\t b:用广义表表示二叉树 \n";
cout << "\t\t 0:退出 \n"; cout << "\n";
cout << "\t\t请选择:" << flush; choice = getch();
system("cls");
switch(choice)
{
case '1'://init1()和showBinTree(Tree)已在头文件BinT.h中定义好
Tree=init1();
cout<<"二叉树创建成功!"<<endl;
showBinTree(Tree);
getch();
break;
case '2':
cout<<"先序遍历:"<<endl;
Preorder(Tree);
getch();
cout<<"中序遍历:"<<endl;
Inorder(Tree);
getch();
cout<<"后序遍历:"<<endl;
Postorder(Tree);
getch();
break;
case '3':
a=leafs(Tree);
cout<<"输出叶子个数:"<<a<<endl;
getch();
break;
case '4':
b=depth(Tree);
cout<<"输出树的深度:"<<b<<endl;
getch();
break;
case '5':
swap(Tree);
showBinTree(Tree);
getch();
break;
case '6':
BuildBST(&Tree);
showBinTree(Tree);
getch();
break;
case '7':
cout<<"请输入要查找的结点:";
cin>>x;
search(Tree);
getch();
break;
case '8':
cout<<"请输入要删除的结点:";
cin>>x;
delUsing(Tree);
getch();
break;
case 'a':
DisplayBinTree(Tree,j);
getch();
break;
case 'b':
cout<<"("<<flush;
ListBinTree(Tree);
cout<<")"<<flush;
getch();
break;
case '0':
exit(0);
}
}
} //前序遍历二叉树
void Preorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
cout<<p->data<<" ";
Preorder(p->left);
Preorder(p->right);
}
} //中序遍历二叉树
void Inorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
Preorder(p->left);
cout<<p->data<<" ";
Preorder(p->right);
}
} //后序遍历二叉树
void Postorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
Postorder(p->left);
Postorder(p->right);
cout<<p->data<<" ";
}
} //计算总叶子数
int leafs(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p->left==NULL&&p->right==NULL)
{
i++;
}
else if(p->left!=NULL&&p->right==NULL)
{
leafs(p->left);
}
else if(p->right!=NULL&&p->left==NULL)
{
leafs(p->right);
}
else
{
leafs(p->left);
leafs(p->right);
}
return i;
} //二叉树的深度
int depth(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if (p==NULL)
{
return 0;
}
else
{
a=depth(p->left);
b=depth(p->right);
}
if (a>b)
{
return (a+1);
}
else
{
return (b+1);
}
} //交换左右子树
void swap(BiTNode *Tree)
{
BiTNode *p,*q;
p=Tree;
if(p)
{
q=p->left;
p->left=p->right;
p->right=q;
swap(p->left);
swap(p->right);
}
} //用凹入表表示二叉树
void DisplayBinTree(BiTNode *Tree,int j)
{
BiTNode *p;
p=Tree;
if(p!=NULL)
{
int i;
for(i=0;i<j;i++)
{
cout<<" ";
}
cout<<p->data<<"\n";
DisplayBinTree(p->left,j+5);
DisplayBinTree(p->right,j+5);
}
}
//用广义表表示二叉树
void ListBinTree(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p!=NULL)
{
cout<<"(";
cout<<p->data;
ListBinTree(p->left);
ListBinTree(p->right);
cout<<")";
}
}
//建立二叉排序树
//插入函数
void inserttree(BiTNode *Tree,int i)
{
BiTNode *p;
p=Tree;
if(p==NULL)
{
p->data=i;
}
else
{
if(i<p->data)
{
inserttree(p->left,i);
}
else
{
if(i>p->data)
{
inserttree(p->right,i);
}
}
}
} void BuildBST(BiTNode **Tree)
{
*Tree=NULL; //注意置空问题,不然连续运行程序会出问题
int i,n;
while (1)
{
cout << "输入数据个数(0-" << max-1 << "):" << flush;
cin >> n;
if (n >= 0 && n <= max-1)
break;
cout << endl;
}
while (1)
{
cout << "输入随机数种子(0-32767):" << flush;
cin >> i;
if (i >= 0 && i <= 32767)
break;
cout << endl;
}
srand(i); //指定随机数种子,相同的种子将产生相同的数据序列
rand(); for (i = 0; i < n; i++)
{
elem[i] = rand() % 999 +1;
}
elem[n] = 0;
i=0;
while(elem[i]!=0)
{
inserttree(*Tree,elem[i]);
++i;
}
}
源文件名: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>
struct BiTNode //二叉树结点类型
{
int data; //数据
int tem1,tem2; //辅助数据(实习题不用)
BiTNode *left; //左子树指针
BiTNode *right; //右子树指针
}; BiTNode *Tree; //本程序操作的二叉树根指针
const max=100;
int elem[max]; //存放原始数据
int a=1,b=1,c;int i=0,j=0;int x;
BiTNode *stack[max];
//从键盘输入个数和随机数种子,在数组elem中生成指定个数的数据,供其他程序使用,0表示数据结束
void init0(int list[]);
void Preorder(BiTNode *Tree); //先序遍历
void Inorder(BiTNode *Tree); //中序遍历
void Postorder(BiTNode *Tree); //后序遍历
int leafs(BiTNode *Tree); //计算总叶子数
int depth(BiTNode *Tree); //二叉树的深度
void swap(BiTNode *Tree); //交换左右子树
void BuildBST(BiTNode **Tree); //建立二叉排序树
void search(BiTNode *Tree);
void del(BiTNode *Tree);
void delUsing(BiTNode *Tree);
void ListBinTree(BiTNode *Tree);//用广义表表示二叉树
void DisplayBinTree(BiTNode *Tree,int j);//用凹入表表示二叉树
//在本程序所在的位置生成文本文件Map.txt,其中显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree); //从键盘输入个数和随机数种子,以Tree为根指针,生成指定结点个数的二叉树,供其他程序使用
//BiTNode *init1(); #include "BinT.h"
//主函数,显示功能菜单(包括生成二叉树、显示二叉树),键盘选择后执行对应功能
void main()
{
char choice;
while (1)
{
system("cls");
cout << "\n\n\n\n";
cout << "\t\t 二叉树操作 \n";
cout << "\t\t=========================================";
cout << "\n\n";
cout << "\t\t 1:建立二叉树 \n";
cout << "\t\t 2:遍历二叉树 \n";
cout << "\t\t 3:计算总叶子数 \n";
cout << "\t\t 4:计算二叉树的深度 \n";
cout << "\t\t 5:交换左右子树 \n";
cout << "\t\t 6:生成二叉排序树 \n";
cout << "\t\t 7:在二叉排序树中查找结点 \n";
cout << "\t\t 8:在二叉排序树中删除结点 \n";
cout << "\t\t a:用凹入表表示二叉树 \n";
cout << "\t\t b:用广义表表示二叉树 \n";
cout << "\t\t 0:退出 \n"; cout << "\n";
cout << "\t\t请选择:" << flush; choice = getch();
system("cls");
switch(choice)
{
case '1'://init1()和showBinTree(Tree)已在头文件BinT.h中定义好
Tree=init1();
cout<<"二叉树创建成功!"<<endl;
showBinTree(Tree);
getch();
break;
case '2':
cout<<"先序遍历:"<<endl;
Preorder(Tree);
getch();
cout<<"中序遍历:"<<endl;
Inorder(Tree);
getch();
cout<<"后序遍历:"<<endl;
Postorder(Tree);
getch();
break;
case '3':
a=leafs(Tree);
cout<<"输出叶子个数:"<<a<<endl;
getch();
break;
case '4':
b=depth(Tree);
cout<<"输出树的深度:"<<b<<endl;
getch();
break;
case '5':
swap(Tree);
showBinTree(Tree);
getch();
break;
case '6':
BuildBST(&Tree);
showBinTree(Tree);
getch();
break;
case '7':
cout<<"请输入要查找的结点:";
cin>>x;
search(Tree);
getch();
break;
case '8':
cout<<"请输入要删除的结点:";
cin>>x;
delUsing(Tree);
getch();
break;
case 'a':
DisplayBinTree(Tree,j);
getch();
break;
case 'b':
cout<<"("<<flush;
ListBinTree(Tree);
cout<<")"<<flush;
getch();
break;
case '0':
exit(0);
}
}
} //前序遍历二叉树
void Preorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
cout<<p->data<<" ";
Preorder(p->left);
Preorder(p->right);
}
} //中序遍历二叉树
void Inorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
Preorder(p->left);
cout<<p->data<<" ";
Preorder(p->right);
}
} //后序遍历二叉树
void Postorder(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p)
{
Postorder(p->left);
Postorder(p->right);
cout<<p->data<<" ";
}
} //计算总叶子数
int leafs(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p->left==NULL&&p->right==NULL)
{
i++;
}
else if(p->left!=NULL&&p->right==NULL)
{
leafs(p->left);
}
else if(p->right!=NULL&&p->left==NULL)
{
leafs(p->right);
}
else
{
leafs(p->left);
leafs(p->right);
}
return i;
} //二叉树的深度
int depth(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if (p==NULL)
{
return 0;
}
else
{
a=depth(p->left);
b=depth(p->right);
}
if (a>b)
{
return (a+1);
}
else
{
return (b+1);
}
} //交换左右子树
void swap(BiTNode *Tree)
{
BiTNode *p,*q;
p=Tree;
if(p)
{
q=p->left;
p->left=p->right;
p->right=q;
swap(p->left);
swap(p->right);
}
} //用凹入表表示二叉树
void DisplayBinTree(BiTNode *Tree,int j)
{
BiTNode *p;
p=Tree;
if(p!=NULL)
{
int i;
for(i=0;i<j;i++)
{
cout<<" ";
}
cout<<p->data<<"\n";
DisplayBinTree(p->left,j+5);
DisplayBinTree(p->right,j+5);
}
}
//用广义表表示二叉树
void ListBinTree(BiTNode *Tree)
{
BiTNode *p;
p=Tree;
if(p!=NULL)
{
cout<<"(";
cout<<p->data;
ListBinTree(p->left);
ListBinTree(p->right);
cout<<")";
}
}
//建立二叉排序树
//插入函数
void inserttree(BiTNode *Tree,int i)
{
BiTNode *p;
p=Tree;
if(p==NULL)
{
p->data=i;
}
else
{
if(i<p->data)
{
inserttree(p->left,i);
}
else
{
if(i>p->data)
{
inserttree(p->right,i);
}
}
}
} void BuildBST(BiTNode **Tree)
{
*Tree=NULL; //注意置空问题,不然连续运行程序会出问题
int i,n;
while (1)
{
cout << "输入数据个数(0-" << max-1 << "):" << flush;
cin >> n;
if (n >= 0 && n <= max-1)
break;
cout << endl;
}
while (1)
{
cout << "输入随机数种子(0-32767):" << flush;
cin >> i;
if (i >= 0 && i <= 32767)
break;
cout << endl;
}
srand(i); //指定随机数种子,相同的种子将产生相同的数据序列
rand(); for (i = 0; i < n; i++)
{
elem[i] = rand() % 999 +1;
}
elem[n] = 0;
i=0;
while(elem[i]!=0)
{
inserttree(*Tree,elem[i]);
++i;
}
}