实现二叉树各种基本运算的算法

举报
程序员飞鸟 发表于 2022/06/26 19:06:21 2022/06/26
【摘要】 二叉树存储结构和二叉树中各种基本算法设计(1) 创建二叉树;(2) 输出二叉树;(3) 输出‘H’结点的左右孩子结点值;(4) 输出二叉树的高度;(5) 释放二叉树。#include<stdio.h>#include<malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ ElemType data; s...

二叉树存储结构和二叉树中各种基本算法设计

(1) 创建二叉树;
(2) 输出二叉树;
(3) 输出‘H’结点的左右孩子结点值;
(4) 输出二叉树的高度;
(5) 释放二叉树。

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;

}BTNode;
void CreateBTree(BTNode *&b,char *str)
{
	BTNode * St[MaxSize],*p;
	int top=-1,k,j=0;char ch;
	b=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=(BTNode *)malloc(sizeof(BTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if(b==NULL)
				b=p;
			else
			{
				switch(k)
				{
                case 1:St[top]->lchild=p;break;
				case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;ch=str[j];
	}
}
void DestroyBTree(BTNode *&b)
{
	if(b!=NULL)
	{
		DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
		free(b);
	}
}
BTNode *FindNode(BTNode *b,ElemType x)
{
	BTNode *p;
	if(b==NULL)
		return NULL;
	else if(b->data==x)
		return b;
	else
	{
		p=FindNode(b->lchild,x);
		if(p!=NULL)
			return p;
		else
			return FindNode(b->rchild,x);
	}
}
BTNode *LchildNode(BTNode *p)
{
	return p->lchild;

}
BTNode *RchildNode(BTNode *p)
{
	return p->rchild;
}
int BTHeight(BTNode *b)
{
	int lchildh,rchildh;
	if(b==NULL)return(0);
	else
	{
		lchildh=BTHeight(b->lchild);
		rchildh=BTHeight(b->rchild);
		return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
	}
}
void DispBTree(BTNode *b)
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DispBTree(b->lchild);
			if(b->rchild!=NULL)printf(",");
			DispBTree(b->rchild);
			printf(")");
		}
	}
}
int main()
{
	BTNode *b,*p,*lp,*rp;;
	printf("二叉树的基本运算如下:\n");
	printf("  (1)创建二叉树\n");
	CreateBTree(b,"A(B(D,E(H(J,k(L,M(,N))))),C(F,G(,I)))");
	printf("  (2)输出二叉树:");DispBTree(b);printf("\n");
	printf("  (3)H结点:");
	p=FindNode(b,'H');
	if(p!=NULL)
	{  lp= LchildNode(p);
	   if(lp!=NULL)printf("左孩子为%c",lp->data);
	   else printf("无左孩子");
	   rp=RchildNode(p);
	   if(rp!=NULL) printf("右孩子为%c",rp->data);
	   else printf("无右孩子");
       
	}
	printf("\n");
	printf("  (4)二叉树b的高度:%d\n",BTHeight(b));
	printf("  (5)释放二叉树b\n");
	DestroyBTree(b);
	return 1;
}

我是不会飞的飞鸟,肝文不易, 如果文章对你有帮助就点赞关注支持一下,下次再见!

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。