求一个完整的树的C++程序

Question

关于二叉树的程序,用C++模板实现

Answer 1

我给你一份二叉树代码，你把char型改成模板类就可以了
#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#include"string.h"

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define TElemType char
char a[20],b[20]; // a存放先序序列，b存放中序序列
//- - - - -二叉树的二叉链表存储表示- - - - -
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;

Status (* VisitFunc)(TElemType v); // 函数指针
Status Visit(TElemType v);//访问函数

Status CreatBiTree(BiTree &T);//由先序序列创建二叉树
void CreateBiTree(int start1,int start2,int len,BiTree &T);//由先序序列和中序序列建立二叉树
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//先序遍历二叉树
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//中序遍历二叉树
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//后序遍历二叉树

//图6.8(b) p127
char Vexch[15]={'a','b','c','$','$','d','e','$','g','$','$','f','$','$','$'};

int i=0;
int pre=0 , flag=1;

void main()
{
BiTree T;
int cord;
int n0=0,n1=0,n2=0,n=0;

do{
printf("\n");
printf("1 GreatBiTree 算法6.4 \n\n");
printf("2 由先序和中序序列创建二叉树\n\n");
printf("3 先序遍历输出： 算法6.1 \n\n");
printf("4 中序遍历输出： \n\n");
printf("5 后序遍历输出： \n\n");
printf("6 Exit Program \n\n");
printf("-----------------------\n\n");
printf("Input Select(1,2,3,4,...)");
scanf("%d",&cord);
switch(cord)
{case 1:
i=0;
CreatBiTree(T);
break;
case 2:
int len;
printf("Please input preorder:\n");
getchar();
gets(a); //输入先序序列
printf("Please input inorder:\n");
gets(b); //输入中序序列
len=strlen(a);
CreateBiTree(0,0,len,T);
break;
case 3:{
printf("先序遍历输出：\n");
PreOrderTraverse(T, Visit);
printf("\n");
}break;
case 4:{
printf("中序遍历输出：\n");
InOrderTraverse(T, Visit);
printf("\n");

}break;
case 5:
printf("后序遍历输出：\n");
PostOrderTraverse(T,Visit);
printf("\n");
break;
case 6:

exit(0);
}
}while(cord<=50);
}

////////////////////////////////////////////////////////////////
Status CreatBiTree(BiTree &T)
{ //按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
//printf("Input char");
//scanf("%c",&ch); //构造二叉链表表示的二叉树T
//getchar();
///教材p127 图6.8 (b)
if(Vexch[i] =='$')
T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=Vexch[i];
++i;//生成根结点
CreatBiTree(T->lchild); //构造左子树
++i;
CreatBiTree(T->rchild); //构造右子树
}
return OK;
}//GreatBiTree

///////////////////////////////////////////////////////////////////////
//由先序序列和中序序列建立二叉树
//start1是先序序列的起始位置，start2是中序序列的起始位置，
//len是先序序列长度
void CreateBiTree(int start1,int start2,int len,BiTree &T)
{
int pos,len1;
if (len<=0) T=NULL;
else
{ pos=start2; //记录中序序列串的位置
while(b[pos]!=a[start1]) pos++; //只要在中序序列串中没有找到根，那么就向继续向后寻找
T=(BiTree)malloc(sizeof(BiTNode));//在中序序列中找到根，开辟根结点的空间
T->data=a[start1]; //根的值为先序序列的第一个元素
len1=pos-start2; //中序序列根左子区即左子树的长度
CreateBiTree(start1+1,start2,len1,T->lchild); //建立左子树
CreateBiTree(start1+len1+1,pos+1,len-len1-1,T->rchild); //建立右子树
}
}

///////////////////////////////////////////////////////////////////////
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ //采用二叉链表存储结构，Visit是对数据元素操作的应用函数,
//先序历遍二叉树T的递归算法，对每个数据元素调用函数Visit。
if (T) //二叉树不空
{
if (Visit(T->data) )
{
if (PreOrderTraverse(T->lchild,Visit) ) //遍历左子树
{
if ( PreOrderTraverse(T->rchild,Visit) ) //遍历右子树
return OK;
}
}
else
return ERROR; //遍历左或右子树不成功
} else return OK;
}//PreOrderTraverse

//////////////////////////////////////////////////////////////////////
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ //中序历遍二叉树T的递归算法，对每个数据元素调用函数Visit。
if (T)
{
if (InOrderTraverse(T->lchild,Visit) ) //遍历左子树
{
if (Visit(T->data) )
if ( InOrderTraverse(T->rchild,Visit) ) //遍历右子树
return OK;
}
else
return ERROR;
}
else
return OK;
}//InOrderTraverse

/////////////////////////////////////////////////////////////////
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{ //后序历遍二叉树T的递归算法，对每个数据元素调用函数Visit。
if (T)
{
if(PostOrderTraverse(T->lchild,Visit) )//遍历左子树
{
if ( PostOrderTraverse(T->rchild,Visit) )//遍历右子树
if (Visit(T->data) )return OK;
}
else return ERROR;
}
else return OK;
}//InOrderTraverse

///////////////////////////////////////////////////////////////////////
Status Visit(TElemType v)
{
printf("%c ",v);
return OK;
}

Answer 2

找数据结构的代码吧

Answer 3

这是我的一个二叉树链式实现，不过没有实现三序，仅有深度优先和官渡优先的遍历，是C语言的。