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

发布网友发布时间：2022-05-12 07:53

共1个回答

热心网友时间：2024-01-18 23:54

我有C语言版的，要不???
先建立一个头文件"bitree.h"(以下都要用到):
#include
<stdio.h>
#include
<malloc.h>
#include
<conio.h>
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);
}