//二叉树
//时间: 05/07/08
//程序: 张建波
//功能：输入二叉树，完成前序、中序、后序、层序遍历
#include <iostream.h>
#include "Menu.h"
#include "key.h"
struct tree
{
int data; // 节点数据
struct tree *left; // 左子树
struct tree *right; // 右子树
};
struct MT{
int data[100]; //保存每层元素
int n; //每层元素的个数
}; //层序遍历保存二叉树的结点
struct MT mt[100]; //假定二叉树最大层数 不超过100层
typedef struct tree treenode; // 树的结构型态
typedef treenode *btree; // 树节点指标型态
void _InputData(int *data); //输入二叉树数据
btree insertnode(btree root,int value); //插入二叉树的节点
btree createbtree(int *data,int len); //建立二叉树
void inorder(btree ptr);// 二叉树中序遍历
void preorder(btree ptr); //二叉树前序遍历
void postorder(btree ptr);//二叉树后序遍历
void CX(btree ptr,int n); //二叉树层序遍历
void _preorder_main(int *data,int n); //前序遍历_测试程序
void _inorder_main(int *data,int n); // 中序遍历_测试程序
void _postorder_main(int *data,int n); //后序遍历列__测试程序
void _CenXu_order_main(int *data,int n);//层序遍历__测试程序
void _ViewTree_main(int *data,int); //浏览树
int _Edit_data(int *data); //修改初始数据
int _f3_main(){ //程序入口
Menu m[10]; //绘制菜单
m[1].Name="输入树";
m[2].Name="浏览树";
m[3].Name="前序遍历 ";
m[4].Name="中序遍历 ";
m[5].Name="后序遍历";
m[6].Name="层序遍历";
m[7].Name="返回";
m[8].Name=" ";
int DATA_Tree[1000] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
int n=9;
int *data=DATA_Tree;
int ID=1;
while(1)
{
ShowMenu("数据结构--二叉树遍历",m,8); //显示菜单
ID=SelectMenuID(); //获取选中的菜单ID
switch(ID){
case 1:{n=_Edit_data(data);InitKey();}break;
case 2:{_ViewTree_main(data,n);InitKey();}break;
case 3:{_preorder_main(data,n);InitKey();}break;
case 4:{_inorder_main(data,n);InitKey();}break;
case 5:{_postorder_main(data,n);InitKey();}break;
case 6:{_CenXu_order_main(data,n);InitKey();}break;
case 7:return 0;
case 8:break;
}
}
return 0;
}
int _Edit_data(int *data){ //修改初始数据
int n;
cout<<"/n请输入结点总数n=";
cin>>n;
cout<<"输入每个结点的数据"<<endl;
cout<<"例如依次输入：5, 6, 4, 8, 2, 3, 7, 1, 9/n"<<endl;
for(int i=0;i<n;i++){ //输入数据
cout<<"["<<i<<"]=";
cin>>data[i];
cout<<"/n";
}
cout<<"/n您输入的数据为：";
for(int j=0;j<n;j++)cout<<data[j]<<" ";
return n;
}
btree insertnode(btree root,int value){ //插入二叉树的节点
btree newnode; //树根
btree current; //目前树节点指标
btree back; //父节点指标
newnode=new treenode; //建立新节点
newnode->data = value; //建立节点内容
newnode->left = NULL; //设定指标初值
newnode->right = NULL; //设定指标初值
if(root==NULL) return newnode; //是根节点传回新节点位置
else
{
current = root; //保留目前树指标
while ( current != NULL )
{
back = current; //保留父节点指标
if ( current->data > value ) //比较节点值
current = current->left; //左子树
else
current = current->right; //右子树
}
if (back->data>value )back->left = newnode; // 左子树
else back->right = newnode; // 右子树
}
return root; // 返回树根
}
btree createbtree(int *data,int len){ //建立二叉树
btree root = NULL; // 树根指标
int i;
for ( i = 0; i < len; i++ ) // 用回路建立树状结构
root = insertnode(root,data[i]);
return root;
}
void preorder(btree ptr){ //二叉树前序遍历
if ( ptr != NULL )
{
cout<<ptr->data<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
void inorder(btree ptr){// 二叉树中序遍历
if ( ptr != NULL ) // 终止条件
{
inorder(ptr->left); // 左子树
cout<<ptr->data<<" ";
inorder(ptr->right); // 右子树
}
}
void postorder(btree ptr){//二叉树后序遍历
if ( ptr != NULL )
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->data<<" ";
}
}
void _preorder_main(int *data,int n){ //先序遍历_测试程序
btree root = NULL;
root = createbtree(data,n); //建立二叉树
cout<<"树的节点内容 n=";
preorder(root); //先序遍历二叉树
}
void _inorder_main(int *data,int n){ // 中序遍历_测试程序
btree root = NULL;
root = createbtree(data,n); //建立二叉树
cout<<"树的节点内容 n=";
inorder(root); //中序遍历二叉树
}
void _postorder_main(int *data,int n){ //后序遍历列__测试程序
btree root = NULL;
root = createbtree(data,n); //建立二叉树
cout<<"树的节点内容 n=";
postorder(root); //后序遍历二叉树
}
//~
//////////////////////////////////////////////
int max_n=0;//保存最大层数
void CX(btree ptr,int n) //层序遍历
{
if ( ptr != NULL )
{
n++; //层计数
if(max_n<n)max_n=n;//保存最大层数
mt[n].data[mt[n].n]=ptr->data; //保存当前层的数据
mt[n].n=mt[n].n+1; //把该层的 元素个数+1
CX(ptr->left,n); //继续浏览 左结点
CX(ptr->right,n); //继续浏览 右结点
}
}
void _CenXu_order_main(int *data,int n){//层序遍历
btree root = NULL;
root = createbtree(data,n); //建立二叉树
cout<<"树的节点内容";
for(int m=0;m<100;m++)mt[m].n=0;
CX(root,0);
cout<<"该二叉树的各层数据如下："<<endl;
for(int mm=0;mm<=max_n;mm++)
{
for(int mn=0;mn<mt[mm].n;mn++)
{
cout<<mt[mm].data[mn]<<" ";
}
cout<<"/n";
}
}
void ViewTree(btree ptr){ //浏览树
if ( ptr != NULL ) // 终止条件
{
cout<<ptr->data;
if(ptr->left!=NULL || ptr->right!=NULL)
{
cout<<"(";
ViewTree(ptr->left);
if(ptr->right!=NULL)cout<<",";
ViewTree(ptr->right);
cout<<")";
}
}
}
void _ViewTree_main(int *data,int n) //浏览树
{
btree root = NULL;
root = createbtree(data,n); //建立二叉树
cout<<"树的节点内容 n=";
ViewTree(root);
}