数据结构建树程序，C语言C++皆可?

Question

数据结构建树程序，C语言C++皆可

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include<iostream.h>
#define maxnode 100
#define NULL 0
typedef char DataType; /*设数据域类型为字符型*/
typedef struct node{
DataType data;
struct node *lchild,*rchild; /*左右链域为指向结点结构的指针类型*/
}bintnode; /*结点类型*/
typedef bintnode *bintree; /*指向二叉树结点的指针类型*/
void createbintree(bintree *T); /*构造二叉链表*/
void Preorder(bintree T); /*先序*/
void inorderout(bintree T); /*中序*/
void Postorder(bintree T); /*后序*/
void LevelOrder(bintree T); /*按层次遍历二叉树T*/

/*以加入结点的先序序列输入，构造二叉链表*/
void createbintree(bintree *T)
{
char ch;
scanf("\n%c",&ch);
if(ch=='0')*T=NULL;
else
{
*T=(bintnode*)malloc(sizeof(bintnode));
(*T)->data=ch;
createbintree(&(*T)->lchild);
createbintree(&(*T)->rchild);
}

}

/*先序遍历二叉树T*/
void Preorder(bintree T)
{
if (T)
{
cout<<T->data; /*访问结点数据*/
Preorder(T->lchild); /*先序遍历二叉树T的左子树*/
Preorder(T->rchild); /*先序遍历二叉树T的右子树*/
}
}

/*中序遍历二叉树T*/
void inorderout(bintree T)
{
if(T)
{
inorderout(T->lchild); /*中序遍历二叉树T的左子树*/
cout<<T->data; /*访问结点数据*/
inorderout(T->rchild); /*中序遍历二叉树T的右子树*/
}
}

/*后序遍历二叉树T*/
void Postorder(bintree T)
{
if (T)
{
Postorder(T->lchild); /*后序遍历二叉树T的左子树*/
Postorder(T->rchild); /*后序遍历二叉树T的右子树*/
cout<<T->data; /*访问结点数据*/
}
}

void LevelOrder(bintree bt)
{
bintree queue[maxnode];
int front,rear;
if (bt==0)return;
front=-1; /*队列初始化*/
rear=0;
queue[rear]=bt; /*根结点入队*/
while(front!=rear)
{
front++;
cout<<queue[front]->data; /*访问队首结点的数据域*/
if(queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/
{
rear++;
queue[rear]=queue[front]->lchild;
}//if
if(queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/
{
rear++;
queue[rear]=queue[front]->rchild;
}//if
}//while
}//LevelOrder

void main()
{
bintree T;
char a,b;
cout<<"欢迎进入二叉树基本操作测试程序，请选择："<<endl;
a='y';
while(a=='y' || a=='Y')
{
cout<<"1-------------------------二叉树建立"<<endl;
cout<<"2-------------------------先序遍历!"<<endl;
cout<<"3-------------------------中序遍历!"<<endl;
cout<<"4-------------------------后序遍历!"<<endl;
cout<<"5-------------------------层次遍历!"<<endl;
cout<<"6-------------------------退出!"<<endl;
cin>>b;
switch(b)
{
case '1': cout<<"请按带空指针的二叉树先序输入建立二叉树存储的结点序列:"<<endl;
createbintree(&T);cout<<endl;break;
case '2': cout<<"该二叉树的先根序遍历序列为:"<<endl;
Preorder(T);cout<<endl;break;
case '3':cout<<"该二叉树的中根遍历序列为:"<<endl;
inorderout(T);cout<<endl;break;
case '4':cout<<"该二叉树的后根遍历序列为:"<<endl;
Postorder(T);cout<<endl;break;
case '5':cout<<"该二叉树的层次遍历序列为:"<<endl;
LevelOrder(T);cout<<endl;break;
case '6':a='n';break;
default:a='n';
}//switch
}//while
}//main