二叉树的基本运算（涉及递归均有给出模型）

目录

介绍：

二叉树的基本运算及其实现：

BTNode* CreateBTree(char* str) 创建二叉树

void DestroyBTree(BTNode* b) 销毁二叉树

BTNode* FindNode(BTNode* b, ElemType x) 查找结点

BTNode* LchildNode(BTNode* p) 查找左孩子结点

BTNode* RchildNode(BTNode* p) 查找右孩子结点

int BTHeight(BTNode* b) 求二叉树b的高度

最后总代码：

结语：

---

介绍：

二叉树的定义：二叉树由一个根结点和两棵互不相交的称为左子树（left subtree）和右子树（right subtree）的二叉树组成。

二叉树的存储结构：

（1）循序存储：（因其在极端条件下空间浪费极大故大部分二叉树都采用链式存储结构）

（2）链式存储：

typedef struct node
{
?? ?ElemType data;? ? ? ?//数据元素
?? ?struct node* lchild;? ? //指向左孩子结点
?? ?struct node* rchild;? ? //指向右孩子结点
}BTNode;? ? ?//二叉树的结构体

二叉树的基本运算及其实现：

特别说明下面运算均采用二叉链存储结构进行存储。

BTNode* CreateBTree(char* str) 创建二叉树

void DestroyBTree(BTNode* b) 销毁二叉树

BTNode* FindNode(BTNode* b, ElemType x) 查找结点

BTNode* LchildNode(BTNode* p) 查找左孩子结点

BTNode* RchildNode(BTNode* p) 查找右孩子结点

int BTHeight(BTNode* b) 求二叉树b的高度

void DispBTree(BTNode* b) 以括号表示法输出二叉树

既然使用二叉链来进行实现的，那么必然就离不开链表，提到链表就不得不想到结构体。那么我们二叉树的结构体就来啦👀

说明：为了使描述简单故基本类型采用char类型，如果大家想修改的话把上面的char改成其它即可。

#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node* lchild;
	struct node* rchild;
}BTNode;

BTNode* CreateBTree(char* str) 创建二叉树

采用括号表达式法表示二叉树，用ch遍历str，因为使括号表达式所以其中只有四类字符，例如下图：

其处理方式如下。

1：若ch=‘（’，表示前面的结点p存在孩子结点需要将其进栈（括号表达式一般都是要用到栈的）。

2：若ch=‘）’，表示以栈顶结点为根节点的子树创建完毕，将其退栈。

3：若ch=‘，’，表示要处理栈顶结点的有孩子结点，故置k=2

4：其它情况：只能是单个字符，对应二叉树中的某个结点值，需要创建一个结点p来存储该结点值。根据k值建立它与栈顶结点之间的联系。当k=1时，将结点p作为栈顶结点的左孩子；当k=2时，将结点p作为栈顶结点的右孩子。

用一个while把str数组全部遍历采用上面四条处理方法，我们的二叉树就创建好啦👌！！！

代码如下：

BTNode* CreateBTree(char* str)
{
	BTNode* b;
	BTNode* St[MaxSize];
	BTNode* p=NULL;
	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];
	}
	return b;
}

void DestroyBTree(BTNode* b) 销毁二叉树

创建讲完，那么销毁必然少不了，想亲兄弟一样（形象吧(?′?`?)）

---

处理方式如下：二叉树最经常用到的莫过于递归了，没错我们的销毁就是用递归来完成的。

递归那么最重要的一定是思路，建议大家遇到递归的时候一定要在草稿纸上列出递归的模型，尤其是递归的出口一定要设置好！！！（下面我给出我的递归模型大家可以参考参考）

当b为NULL时什么也不做，当b不等于NULL时先释放左孩子子树的空间，再释放右孩子子树的空间，最后再释放b树的空间，为什么要按照这个循序呢？这是因为如果先释放了b那么我们的左右孩子子树就找不到了，那么内存就会泄露。（这个递归其实总的就执行free（b））

代码如下：

void DestroyBTree(BTNode* b)
{
	if (b != NULL)
	{
		DestroyBTree(b->lchild);
		DestroyBTree(b->rchild);
		free(b);
	}
	return;
}

BTNode* FindNode(BTNode* b, ElemType x) 查找结点

其功能是在二叉树b中查找值为x的结点，找到后返回其地址，否则返回NULL。

处理方式如下：没错这里的实现又是递归。对于递归的解释在上面的销毁哪我已经讲的很清楚了，故这里不在过多赘述。递归的模型如下：

对着上面的这张图，那么代码实现就非常简单啦🤳🤳🤳

代码如下：

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) 查找左孩子结点

BTNode* RchildNode(BTNode* p) 查找右孩子结点

由于这两个基本算法的实现和功能基本一致故这里我们两个一起来（因为简单故直接上代码）

代码如下：

BTNode* LchildNode(BTNode* p)
{
	return p->lchild;
}
BTNode* RchildNode(BTNode* p)
{
	return p->rchild;
}

int BTHeight(BTNode* b) 求二叉树b的高度

有树那么就有高度，高的树价值大，高的二叉树占的空间大。

处理方法：递归实现，递归的模型如下：

依图代码实现如下：

特别注意：规定空树的高度为0，只有一个根高度为1

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) 以括号表示法输出二叉树

最后就是输出二叉树了，实现方法：递归，有孩子结点时才输出‘（’，递归输出左子树，有右孩子结点才输出‘，’，递归输出右子树，有孩子结点时才输出‘）’。具体递归模型如下：

因为存储时，我们并没有存储括号和逗号，故在输出时，我们要人为的给它们加上。

具体代码实现如下：

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(")");
		}
	}
}

最后总代码：

有给出括号表达式供大家进行代码调试并理解代码。

#define  _CRT_SECURE_NO_WARNINGS 1
//二叉树的基本运算
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node* lchild;
	struct node* rchild;
}BTNode;
BTNode* CreateBTree(char* str)
{
	BTNode* b;
	BTNode* St[MaxSize];
	BTNode* p=NULL;
	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];
	}
	return b;
}
void DestroyBTree(BTNode* b)
{
	if (b != NULL)
	{
		DestroyBTree(b->lchild);
		DestroyBTree(b->rchild);
		free(b);
	}
	return;
}
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()
{
	char str[] = "A(B(D(,G)),C(E,F))";
	BTNode* b = CreateBTree(str);
	DispBTree(b);
	return 0;
}

以上便是二叉树的基本运算，那么我们的文章就好这里结束啦🎉🎉🎉

结语：

其实写博客不仅仅是为了教大家，同时这也有利于我巩固自己的知识点，和一个学习的总结，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进，如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。