当前位置:文档之家› 数据结构与算法问题分析及源代码之二叉树

数据结构与算法问题分析及源代码之二叉树

二叉树
1 题目
编写一个程序,实现二叉树的各种运算,并在此基础上设计一个主程序完成如下功能(b 为如图示的一棵二叉树):
输出二叉树b;
输出‘H’节点的左、
右孩子结点值;
输出二叉树b的深度;
输出二叉树b的结点个数;
输出二叉树b的叶子结点个数。

2 目标
熟悉二叉树的定义及其基本操作的实现
3 设计思想
二叉树的每个结点都有指向其左右孩子的指针,对二叉树的表示可以有很多方法,这里采用中序的带括号表示法,以字符串形式读入输出。

建立存储结构的时候,从根结点开始,赋值定义其左右指针,由于二叉树的每个结点操作类似,因此可以采用递归的方法。

4 算法描述
(1)输入建立二叉树:读入字符串,根据括号表示法的规则,a(b,c)的括号中左右元素表示结点的左右子树结点,若结点是树(括号中还有括号),则再调用改操作,直至结点全部读入。

(2)输出二叉树:从根结点开始,打印根结点数据,如果结点的左右孩子指针不为空,就打印左括号,并按先左后右的次序调用此操作,最后输出右括号完成括号表示。

(3)输出二叉树的深度:从根结点开始,如果左或右孩子不是树的话返回深度加一,否则继续调用此操作,直到完全返回(返回深度是左、右深度中的最大值)。

(4)输出二叉树叶子结点数:从根结点开始,用ln和r n分别表示结点左右叶子结点数,函数返回叶子结点数之和,递归调用该函数,直到左右指针指空。

(5)输出二叉树结点数:结点数即是叶子数加一。

5 程序结构图
6 源程序
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}*Bitree;
Bitree bt;
void CreateBitree(Bitree &bt,char *str){
Bitree St[100],p=NULL;//100个结点的二叉树
int top=-1,k,j=0;
char ch;
bt=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case'(':top++;St[top]=p;k=1;break;
case')':top--;break;
case',':k=2;break;
default:p = (struct node*)malloc(sizeof(struct node)); p->data=ch;p->lchild=p->rchild=NULL;
if (bt==NULL)//是根结点
bt=p;
else//是叶子结点
{ switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break; }
}
}
j++;
ch=str[j];
}
}
void DispBTNode(Bitree bt)
{
Bitree p;
if(bt==NULL) return ;
else {
printf("%c",bt->data);
if(bt->lchild!=NULL||bt->rchild!=NULL) {
printf("(");
DispBTNode(bt->lchild);
if(bt->rchild!=NULL)
printf(",");
DispBTNode(bt->rchild);
printf(")");
}
}
}
int BtNodeDepth(Bitree bt)
{
int lh,rh;
if(bt==NULL)
return 0;
else
{
lh=BtNodeDepth(bt->lchild);
rh=BtNodeDepth(bt->rchild);
return (lh>rh?lh:rh)+1;
}
}
int NodeNum(Bitree bt)
{
int ln,rn;
if(bt==NULL)
return 0;
else
{
ln=NodeNum(bt->lchild);
rn=NodeNum(bt->rchild);
return ln+rn+1;
}
}
int LeafNodeNum(Bitree bt)
{
int ln,rn;
if(bt==NULL)
return 0;
else if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
else
{
ln=LeafNodeNum(bt->lchild);
rn=LeafNodeNum(bt->rchild);
return ln+rn;
}
}
#include<stdio.h>
#include<stdlib.h>
#include"bintree.h"
void main()
{
int m,length;
Bitree p;
char e;
char choice;
printf("请选择(输入退出)\n1 创建二叉树b\n2 打印二叉树b(中续括号表示法)\n3 二叉树b的长度\n4 二叉树b的结点数\n5 二叉树b的叶子数\n");
while(choice!='0')
{
// system("cls");
scanf("%c",&choice);
switch (choice)
{
case'1':
CreateBitree(bt,"A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))");
break;
case'2':
DispBTNode(bt);
printf("\n");
break;
case'3':
printf("二叉树b的长度为:%d\n",BtNodeDepth(bt));
break;
case'4':
printf("二叉树结点数为:%d\n",NodeNum(bt));
break;
case'5':
printf("二叉树叶子结点数为:%d\n",LeafNodeNum(bt));
break;
case'0':
return;
}
getchar();
}
}。

相关主题