数据结构中关于用c++语言建立二叉树的问题,求代码,急!!!

2024-12-21 13:25:42
推荐回答(1个)
回答1:

我有C语言版的,要不???
先建立一个头文件"bitree.h"(以下都要用到):

#include
#include
#include

typedef char DataType;

typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
}BiTNode, *BiTree;

void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
程序如下:
(1)
#include "bitree.h"

void preOrder(BiTree root)
/*先序遍历二叉树, root为指向二叉树根结点的指针*/
{
if (root!=NULL)
{
printf("%c",root->data); /*输出结点*/
preOrder(root ->LChild);/*先序遍历左子树*/
preOrder(root ->RChild); /*先序遍历右子树*/
}
}
void inOrder(BiTree root)
{
if(root!=NULL)
{
inOrder(root->LChild);/*中序遍历左子树*/
printf("%c",root->data); /*输出结点*/
inOrder(root->RChild);/*中序序遍历右子树*/
}
}
void postOrder(BiTree root)
{
if(root!=NULL)
{
postOrder(root->LChild);/*后序遍历左子树*/
postOrder(root->RChild);/*后序遍历右子树*/
printf("%c",root->data);/*输出结点*/
}
}

void main()
{
BiTree T;
printf("建立二叉树,请输入序列:\n");
CreateBiTree(&T);
printf("\n输出前序序列为:");
preOrder(T);
printf("\n输出中序序列为:");
inOrder(T);
printf("\n输出后序序列为:");
postOrder(T);
getch();
}
(2)
#include "bitree.h"
int leaf(BiTree root)//求二叉树中叶子结点的数目
{
int LeafCount;
if(root==NULL)
LeafCount=0;
else if((root->LChild==NULL)&&(root->RChild==NULL))
LeafCount=1;
else
LeafCount=leaf(root->LChild)+leaf(root->RChild);
return LeafCount;
}
void main()
{
BiTree T;
int LeafCount;
printf("按扩展先序遍历序列建立二叉树,请输入序列:\n");
CreateBiTree(&T);
LeafCount=leaf(T);
printf("\n输出叶子结点的个数:");
leaf(T);
printf("%d",LeafCount);
}
(3)
#include "bitree.h"
int PostTreeDepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max=hl>hr? hl:hr;
return(max+1);
}
else return(0);
}
void main()
{
BiTree T;
int max;
printf("建立二叉树,请输入序列:\n");
CreateBiTree(&T);
max=PostTreeDepth(T);
printf("\n输出二叉树的高度为:");
PostTreeDepth(T);
printf("%d",max);
}