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

Question

1.创建树，键盘输入屏幕输出

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

Answer 2

数据结构书里有全的，还有讲解

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct bitnode
{
char data;
struct bitnode *lchild, *rchild;
}bitnode, *bitree;

void createbitree(t,n)
bitnode ** t;
int *n;
{
char x;
bitnode *q;

*n=*n+1;
printf("\n Input %d DATA:",*n);
x=getchar();
if(x!='\n') getchar();

if (x=='\n')
return;

q=(bitnode*)malloc(sizeof(bitnode));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
*t=q;

printf(" This Address is: %o, Data is: %c,\n Left Pointer is: %o, Right Pointer is: %o",q,q->data,q->lchild,q->rchild);

createbitree(&q->lchild,n);
createbitree(&q->rchild,n);
return;
}

void visit(e)
bitnode *e;
{
printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n",e,e->data,e->lchild,e->rchild);
}

void preordertraverse(t)
bitnode *t;
{
if(t)
{
visit(t);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
return ;
}else return ;
}

void countleaf(t,c)
bitnode *t;
int *c;
{
if(t!=NULL)
{
if (t->lchild==NULL && t->rchild==NULL)
{*c=*c+1;
}
countleaf(t->lchild,c);
countleaf(t->rchild,c);
}
return;
}

int treehigh(t)
bitnode *t;
{int lh,rh,h;
if(t==NULL)
h=0;
else{
lh=treehigh(t->lchild);
rh=treehigh(t->rchild);
h=(lh>rh ? lh:rh)+1;
}
return h;
}
main()
{
bitnode *t; int count=0;
int n=0;

printf("\n Please input TREE Data:\n");
createbitree(&t,&n);

printf("\n This is TREE Struct: \n");
preordertraverse(t);

countleaf(t,&count);
printf("\n This TREE has %d leaves ",count);

printf(" , High of The TREE is: %d\n",treehigh(t));
}


这个事二叉树