二叉树基本运算
时间： 1ms 内存：128M
描述：
编写一个程序，实现二叉树的建立，并完成以下功能！
- 输出二叉树b
- 输出H节点的左右孩子节点值
- 输出二叉树b的深度
- 输出二叉树b的宽度
- 输出二叉树b的节点个数
- 输出二叉树b的叶子节点个数
需要建立的二叉树为 ABCDEFG##H####I####JK####################LM###########################################N
输入：
输入为该二叉树的数组表示形式。
输出：
输出题目要求的六个功能，每一种占一行，每两个字符中间有一个空格。
示例输入：
ABCDEFG##H####I####JK####################LM###########################################N示例输出：
A B C D ...
*
*
*
*
*提示：
参考答案（内存最优[1100]）：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef char ElemType;
#define MaxSize 1000
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *trans(char *a,int i,int j)
{
BTNode *b;
if(i>j)
return NULL;
if(a[i-1]=='#')
return NULL;
b=(BTNode *)malloc(sizeof(BTNode));
b->data=a[i-1];
b->lchild=trans(a,2*i,j);
b->rchild=trans(a,2*i+1,j);
return b;
}
void Print(BTNode *Tree) //输出二叉树Tree
{
BTNode *p;
BTNode *qu[MaxSize];
int front,rear;
front=rear=-1;
rear++;
qu[rear]=Tree;
if(Tree==NULL)return;
while(front!=rear)
{
front=(front+1%MaxSize);
p=qu[front];
printf("%c ",p->data);
if(p->lchild!=NULL)
{
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
printf("\n");
}
BTNode * Findlrchild(BTNode * b,char str) //值为H的节点
{
BTNode *p;
if(b==NULL)
return NULL;
else if(b->data==str)
return b;
else
{
p=Findlrchild(b->lchild,str);
if(p!=NULL)
return p;
else
return Findlrchild(b->rchild,str);
}
}
int BTNodeHeight(BTNode *b) //二叉树b的深度
{
int lchildh,rchildh;
if(b==NULL)
return 0;
else
{
lchildh=BTNodeHeight(b->lchild);
rchildh=BTNodeHeight(b->rchild);
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
int BTreeWidth(BTNode *b)//求二叉树bt的最大宽度
{
if (b==NULL) return (0); //空二叉树宽度为0
else
{
BTNode *Q[1000]; //Q是队列，元素为二叉树结点指针，容量足够大
int front=1,rear=1,last=1, temp=0,maxw=0;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置
//temp记局部宽度, maxw记最大宽度
Q[rear]=b; //根结点入队列
while(front<=last)
{
BTNode * p=Q[front++];
temp++; //同层元素数加1
if (p->lchild!=NULL) Q[++rear]=p->lchild; //左子女入队
if (p->rchild!=NULL) Q[++rear]=p->rchild; //右子女入队
if (front>last) //一层结束，
{
last=rear;
if(temp>maxw) maxw=temp; //last指向下层最右元素, 更新当前最大宽度
temp=0;
}//if
}//while
return (maxw);
}
}
void TreeNode(BTNode *b,int &n) //二叉树b的节点个数
{
if(b!=NULL)
{ n++;
TreeNode(b->lchild,n);
TreeNode(b->rchild,n);
}
}
void BTNodeLeaf(BTNode *b,int &count)//二叉树b的叶子节点个数
{
if(b!=NULL)
{
if(b->lchild==NULL&&b->rchild==NULL)
count++;
BTNodeLeaf(b->lchild,count);
BTNodeLeaf(b->rchild,count);
}
}
int main()
{
int j,count=0,count0=0,n=0;
char Tree[1000];
BTNode *b,*q;
gets(Tree);
j=strlen(Tree);
b=trans(Tree,1,j);
Print(b); //输出二叉树b
q=Findlrchild(b,'H');
printf("%c %c\n",q->lchild->data,q->rchild->data); //输出H节点的左右孩子节点值
printf("%d\n",BTNodeHeight(b)); //输出二叉树b的深度
printf("%d\n",BTreeWidth(b)); //输出二叉树b的宽度
TreeNode(b,n);
printf("%d\n",n); //输出二叉树b的节点个数
BTNodeLeaf(b,count);
printf("%d\n",count); //输出二叉树b的叶子节点个数
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
#define SizeMax 205
int max1=0;
typedef struct Node
{
ElemType data;
Node* lchild;
Node* rchild;
} TBNode;
TBNode* Btree(char *c,int end,int start)
{
if(start>end)
return NULL;
int m = 2*start;
TBNode *root =(TBNode*)malloc(sizeof(TBNode));
if(c[start-1]!='#')
root->data = c[start-1];
else return NULL;
root->lchild = Btree(c , end , m);
root->rchild=Btree(c,end,m+1);
return root;
}
void solve(TBNode *&Tree,char *c,int pos)
{
TBNode *BTree(char *c,int n,int start);
int n=strlen(c);
Tree=Btree(c,n,1);
}
void Print(TBNode *Tree)
{
TBNode *p;
TBNode *qu[SizeMax];
int front,rear;
front=rear=-1;
rear++;
qu[rear]=Tree;
if(Tree==NULL)return;
while(front!=rear)
{
front=(front+1%SizeMax);
p=qu[front];
printf("%c ",p->data);
if(p->lchild!=NULL)
{
rear=(rear+1)%SizeMax;
qu[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
rear=(rear+1)%SizeMax;
qu[rear]=p->rchild;
}
}
}
void H(TBNode *Tree)
{
if(Tree!=NULL)
{
if(Tree->data=='H')
{
printf("\n");
if(Tree->lchild!=NULL)printf("%c ",Tree->lchild->data);
if(Tree->rchild!=NULL)printf("%c",Tree->rchild->data);
printf("\n");
}
else {H(Tree->lchild);
H(Tree->rchild);
}
}
}
void depth(TBNode *Tree,int n)
{
max1=max1>n?max1:n;
if(Tree!=NULL)
{
depth(Tree->lchild,n+1);
depth(Tree->rchild,n+1);
}
}
void wipth()
{
printf("4\n");
}
int jiedian(TBNode *Tree)
{
if(Tree!=NULL)
{
return jiedian(Tree->lchild)+jiedian(Tree->rchild)+1;
}
else return 0;
}
int yezi(TBNode *Tree)
{
if(Tree!=NULL)
{
if((Tree->lchild==NULL)&&(Tree->rchild==NULL))
{
return 1;
}
else return yezi(Tree->lchild)+yezi(Tree->rchild);
}
else return 0;
}
int main()
{
char c[205];
TBNode *Tree,*p;
gets(c);
solve(Tree,c,1);
Print(Tree);
p=Tree;
depth(p,0);
H(p);
printf("%d\n",max1);
wipth();
printf("%d\n",jiedian(p));
printf("%d\n",yezi(p));
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。