二叉树基本运算

时间: 1ms        内存:128M

描述:

编写一个程序,实现二叉树的建立,并完成以下功能!

 

  1. 输出二叉树b
  2. 输出H节点的左右孩子节点值
  3. 输出二叉树b的深度
  4. 输出二叉树b的宽度
  5. 输出二叉树b的节点个数
  6. 输出二叉树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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。