求数据结构C语言的一程序

Question

以递归方式按先序序列建立二叉树的二叉链表结构，再分别输出先序、中序、后序的遍历结果。
输入顺序为ABVDFVVGVVCVEVHVV

Answer 1

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
//定义二叉树链表
struct Bitree
{
char c;
struct Bitree *lchild,*rchild;
};
//定义队列
struct Quene
{
struct Bitree *p;//指向数的节点的指针
struct Quene *next;
};
//定义哈夫曼树的结构
struct Huffman
{
int weight;//权值
int tag;
int parent,lchild,rchild;
char ch;
};

struct Bitree *creatBt()
{
struct Bitree *btree;
char ch;
cin>>ch;
// "访问"操作为生成根结点
if(ch!='#')
{
btree=(struct Bitree * )malloc(sizeof(struct Bitree )) ;
btree->c=ch;
btree->lchild=creatBt(); // 递归建(遍历)左子树
btree->rchild=creatBt(); // 递归建(遍历)右子树
}
if(ch=='#')
{
btree=NULL;
}
return btree;
}
//先序遍历递归
void preOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
cout<<p->c<<" ";
preOrder1(p->lchild);
preOrder1(p->rchild);
}
}
//中序遍历递归
void inOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
inOrder1(p->lchild);
cout<<p->c<<" ";
if(p->rchild!=NULL)
inOrder1(p->rchild);
}
//后序遍历递归
void postOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
postOrder1(p->lchild);
if(p->rchild!=NULL)
postOrder1(p->rchild);
cout<<p->c<<" ";

}
//非递归先序遍历
void preOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do
{
while(p!=NULL)
{
cout<<p->c<<" ";
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
p=p->rchild;
}
}
while(top>0||p!=NULL);
}
//非递归中序遍历
void inOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do// while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
cout<<p->c<<" ";
p=p->rchild;
}
} while(top>0||p!=NULL);
}
//非递归后序遍历
void postOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
if(p->rchild==NULL)
cout<<p->c<<" ";
p=p->rchild;
}
}
p=btree;
cout<<p->c<<" ";
}
//二叉树的高度
int btHeigh(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int hl=0, h2=0, max=0;
if(p!=NULL)
{
hl=btHeigh(p->lchild); //求左子树的深度
h2=btHeigh(p->rchild); //求右子树的深度
max=hl>h2?hl: h2;
return(max+1);// 返回树的深度
}
else
return 0;
}
//求二叉树的叶子个数
int numLeave(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int static n=0;//静态变量计数
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
n++; //若root所指结点为叶子, 则累加
numLeave(p->lchild);
numLeave(p->rchild);
return n;
}
else
return 0;
}

//借助队列实现二叉树的层次遍历。
void btQuene(struct Bitree *btree)
{
struct Quene *head,*rear,*temp;
head=(struct Quene*)malloc(sizeof(struct Quene));//给队列头指针分配器空间
head->p=btree;
head->next=NULL;
rear=head;
while(head!=NULL)
{
if(head->p->lchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));//中间变量暂时保存数的结点
temp->p=head->p->lchild;
temp->next=NULL;
rear->next=temp;//将新结点连接在前一个结点的后面
rear=temp;
}
if(head->p->rchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));
temp->p=head->p->rchild;
temp->next=NULL;
rear->next=temp;
rear=temp;
}
temp=head;
cout<<head->p->c;
head=head->next;
free(temp);
}
}

//建立哈夫曼树
void creatHfm()
{
struct Huffman *HF;
int num;
int i,j,x1,x2,m1,m2;
cout<<"输入字符个数；";
cin>>num;
if(num<=1)
{
cout<<"不能建立哈夫曼树！"<<endl;
return ;
}
HF=new struct Huffman[2*num-1];
char c;
//构造叶子结点数为num,权值为weight的哈夫曼树HF[]
for(i=0;i<num;i++)
{
cout<<"请输入第"<<i+1<<"个字符值:";
cin>>c;
HF[i].ch=c;
cout<<"请输入该字符的权值:";
cin>>HF[i].weight;
HF[i].parent=-1;
HF[i].lchild=-1;
HF[i].rchild=-1;
HF[i].tag=0;
}
//构造非叶子结点
for(i=0;i<num-1;i++)//合并n-1次
{
m1=m2=32767;//m1是最小值单元，m2为次小值
x1=x2=0;//x1，x2为下标号
for(j=0;j<num+1;j++)//找最小权值和次小权值
{
if(HF[i].weight<m1&&HF[j].tag==0)
{
m2=m1;
x2=x1;
m1=HF[j].weight;
x1=j;
}
else if(HF[j].weight<m2&&HF[j].tag==0)
{
m2=HF[j].weight;
x2=j;
}
}
//将两棵子树合并成一棵新树
HF[x1].parent=num+i;//x1,x2对应的子树分别作为n+i的左右子树
HF[x2].parent=num+i;
HF[x1].tag=1;
HF[x2].tag=1;
HF[num+i].weight=HF[x1].weight+HF[x2].weight;//新书跟的权值为左右树根的权值之和
HF[num+i].lchild=x1;//n+i的做孩子是x1
HF[num+i].rchild=x2;
}
cout<<"哈夫曼树创建成功!"<<endl;
}

//删除值为x的结点，并释放相应的空间
void btFree(struct Bitree *btree,char x)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
if(p->c==x)
{
free(p);
cout<<"释放成功！"<<endl;
}
else
{
btFree(p->lchild,x);
btFree(p->rchild,x);
}

}
else
cout<<"空间释放失败！"<<endl;
}
void main()
{
int key;
int depth;
int numLea;
struct Bitree *btree;
cout<<"输入数的节点，'#'表示空节点:"<<endl;
btree=creatBt();
cout<<"二叉树创建成功!"<<endl;
cout<<endl;

cout<<"***********************************"<<endl;
cout<<" 选择菜单 "<<endl;
cout<<"1、递归先序遍历二叉树 "<<endl;
cout<<"2、递归中序遍历二叉树 "<<endl;
cout<<"3、递归后序遍历二叉树 "<<endl;
cout<<"4、非递归先序遍历二叉树 "<<endl;
cout<<"5、非递归中序遍历二叉树 "<<endl;
cout<<"6、非递归后序遍历二叉树 "<<endl;
cout<<"7、求二叉树的高度 "<<endl;
cout<<"8、求二叉树的叶子结点个数 "<<endl;
cout<<"9、队列实现二叉树层次遍历"<<endl;
cout<<"10、建立哈夫曼树 "<<endl;
cout<<"11、释放空间 "<<endl;
cout<<"***********************************"<<endl;
for(;key!=0;)
{
cout<<"输入选项，(0表示结束操作):";
cin>>key;
switch(key)
{

case 1:
cout<<"递归先序遍历结果是:";
preOrder1(btree);
cout<<endl;
break;
case 2:
cout<<"递归中序遍历结果是:";
inOrder1(btree);
cout<<endl;
break;
case 3:
cout<<"递归后序遍历结果是:";
postOrder1(btree);
cout<<endl;
break;
case 4:
cout<<"非递归先序遍历结果是:";
preOrder2(btree);
cout<<endl;
break;
case 5:
cout<<"非递归中序遍历结果是:";
inOrder2(btree);
cout<<endl;
break;
case 6:
cout<<"非递归后序遍历结果是:";
postOrder2(btree);
cout<<endl;
break;
case 7:
depth=btHeigh(btree);
cout<<"二叉树的高度为";
cout<<depth<<endl;
break;
case 8:
numLea=numLeave(btree);
cout<<"二叉树的叶子结点数为";
cout<<numLea<<endl;
break;
case 9:
cout<<"层次遍历的结果为:";
btQuene(btree);
cout<<endl;
break;
case 10:
creatHfm();
break;
case 11:
char c;
cout<<"输入要释放的结点:";
cin>>c;
btFree(btree,c);
break;
default:
printf("\n输入选项错误！\n ");
}
}
}

Answer 2

//递归是最简单的了
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTnode
{
char data;
BiTnode* lchild,*rchild;
}BiTnode,*BiTree;
void visit(char e)
{
printf("%c ",e);
}
void CreateTree(BiTree &T)
{
char number;
scanf("%c",&number);
if (number=='V')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTnode));
T->data=number;
if(!T) exit(1);
CreateTree(T->lchild);
CreateTree(T->rchild);
}
}
void BitreePrint(BiTree T,void(*visit)(char))
{
if (T)
{
visit(T->data);
BitreePrint(T->lchild,visit);
BitreePrint(T->rchild,visit);
}
}
void BitreeinPrint(BiTree T,void(*visit)(char))
{
if (T)
{
BitreeinPrint(T->lchild,visit);
visit(T->data);
BitreeinPrint(T->rchild,visit);
}
}
void BitreepostPrint(BiTree T,void(*visit)(char))
{
if (T)
{
BitreepostPrint(T->lchild,visit);
BitreepostPrint(T->rchild,visit);
visit(T->data);
}
}
void main()
{
BiTree T=NULL;
printf("请输入数据:");
CreateTree(T);
printf("前序遍历:");
BitreePrint(T,visit);
printf("\n");
printf("中序遍历:");
BitreeinPrint(T,visit);
printf("\n");
printf("后序遍历:");
BitreepostPrint(T,visit);
printf("\n");

}本回答被网友采纳

Answer 3

V是结束字符？
以下代码供参考：
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;

//以下是建立二叉树存储结构
Status CreateBiTree(BiTree &T) {
//请将该算法补充完整，参见第6章课件算法或课本
char ch;
scanf("%c",&ch);
if(ch=='V') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;

} // CreateBiTree
void Preorder(BiTree T)
{// 先序遍历二叉树
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}

void Inorder(BiTree T)
{ // 中序遍历二叉树
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}

void main(){
BiTree T;
int s=0,d;
printf("\n creat of the bitree:\n");
CreateBiTree(T);
printf("\n output result of Preorder:\n");
Preorder(T);
Inorder(T);
Postorder(T);

}