二叉树的遍历、高度、叶子数量、拷贝以及释放

迈不过友情╰ 2022-04-18 00:19 119阅读 0赞

先给出二叉树的结构体定义：

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    struct BinaryTree
    {
    	char value;
    	struct BinaryTree *LChild;
    	struct BinaryTree *RChild;
    };

再提供一个main方法以便二叉树的创建与函数的调用：

int main(int argc, char *argv[])
    {
    	struct BinaryTree g = { '8', NULL, NULL };
    	struct BinaryTree f = { '6', NULL, NULL };
    	struct BinaryTree e = { '4', NULL, NULL };
    	struct BinaryTree d = { '2', NULL, NULL };
    	struct BinaryTree c = { '7', &f, &g };
    
    	struct BinaryTree b = { '3', &d, &e };
    	struct BinaryTree a = { '5', &b, &c };
    
    	recursion(&a);
    	printf("\n");
    	
    	int height = getTreeHeight_another(&a);
    	printf("树的高度为：%d\n", height);
    	
    	int num = getLeafNum(&a);
    	printf("叶子的数量：%d\n", num);
    	
    	struct BinaryTree *newTree =  TreeCopy(&a);
    	printf("遍历拷贝后的二叉树：");
    	recursion(newTree);
    	printf("\n");
    
    	destroy(&newTree);
    
    	system("pause");
    	return 0;
    }

### 一.树的高度： ###

树的高度从下往上增长，最底层为1。  
求树的高度本身也是一个递归的问题：树的高度等于最高的子树的高度加上1。  
所以也要深入的树的最底层，直到没有左右子树的节点，均返回0，之后返回1，  
回溯到上层函数。此时上层递归的左节点深入的语句已经执行完毕，所以开始右  
节点深入，此处的右节点与左节点情况相同，高度同样为1，从上至下的第2层递  
归所以整体返回2。最终整个函数返回3，递归深入最深为4层。

int getTreeHeight(struct BinaryTree *root)
    {
    	if (root == NULL)return 0;
    	int LHeight = getTreeHeight(root->LChild);
    	int RHeight = getTreeHeight(root->RChild);
    	return LHeight > RHeight ? LHeight + 1 : RHeight + 1;
    }

可以更改递归的推出条件，以减少递归的深入层次，这样递给的深入层次最多三层。

int getTreeHeight_another(struct BinaryTree *root)
    {
    	if (root->LChild == NULL && root->RChild == NULL)return 1;
    	int LHeight = getTreeHeight(root->LChild);
    	int RHeight = getTreeHeight(root->RChild);
    	return LHeight > RHeight ? LHeight + 1 : RHeight + 1;
    }

### 二.递归遍历 ###

//递归遍历
    void recursion(struct BinaryTree *root)
    {
    	if (!root)return;
    	putchar(root->value);
    	putchar(' ');
    	recursion(root->LChild);
    	recursion(root->RChild);
    }

### 三.统计叶子数量 ###

判断叶子方法就是：判断一个节点没有左子树和右子树，那么这个节点就是一个叶子节点。  
那么统计叶子数量可以通过返回值，将左子树与右子树返回的的叶子数量分别相加，这种定义方式  
本身就是递归。  
统计叶子数量同样需要深入到树的最底层，所以如以下代码所示：先从左节点开始渗入，直到找到一个  
左右节点均为NULL的叶子节点，此时会返回一个1；之后回溯到上层函数，继续执行“加号”后面的得到  
右子树叶子数量的代码，此处同样也返回一个1，相加结果为2，总体回溯到它的调用函数即第一层也就是  
用户直接调用的函数，执行后面对根节点右子树叶子数量高的计算。

int getLeafNum(struct BinaryTree *root)
    {
    	if (root->LChild == NULL && root->RChild == NULL)return 1;
    	return getLeafNum(root->LChild) + getLeafNum(root->RChild);
    }

### 四.二叉树的拷贝 ###

树的拷贝直到找到一个节点它的左子树返回NULL，右子树也返回NULL，  
那么就为它自身开辟空间，并为其成员变量赋值：挂上左子树、右子树，并保存value。  
之后再返回这个节点作为上次递归的左或右孩子，直到root就是调用函数时传入的root时，  
给其成员赋值，然后结束递归。  
此递归案例需要注意的是：拷贝动作需要从叶子开始，所以就要先深入到树的最底层，  
然后创建节点，进行拷贝。

struct BinaryTree *TreeCopy(struct BinaryTree *root)
    {
    	if (!root)return NULL;
    
    	struct BinaryTree *LChild = TreeCopy(root->LChild);
    	struct BinaryTree *RChild = TreeCopy(root->RChild);
    	struct BinaryTree *myRoot = malloc(sizeof(struct BinaryTree));
    
    	myRoot->LChild = LChild;
    	myRoot->RChild = RChild;
    	myRoot->value = root->value;
    
    	return myRoot;
    }

### 五.二叉树的释放 ###

此函数用于释放TreeCopy返回的二叉树，使用它去释放用户创建的二叉树是非法的操作。  
要首先深入到叶子结点，之后逐层向上释放，否则先释放根节点，而后面的子树就无法进行操作，  
会造成内存泄漏。

此处选择的是使用传入二级地址，因为我想要将释放后的节点赋值为NULL(当然这个被递归释  
放掉的空间以后也不会使用，完全不必赋值为NULL)，所以需要使用\*root的地址来完成。需要  
注意的点是在深入递归传递参数时，要对子树进行取地址操作，对应参数所要求的二级指针。

这里还是先选择释放左子树，当找到左右均为NULL的叶子节点时，将其释放并赋值为NULL，之后  
回溯到上层递归中，执行未执行的释放右子树的代码，此时为递归的第二层。

void destroy(struct BinaryTree **root)
    {
    	if ((*root)->LChild == NULL && (*root)->RChild == NULL)
    	{
    		putchar((*root)->value), putchar(' '), free(*root), *root = NULL;
    		return;
    	}
    	destroy(&(*root)->LChild);
    	destroy(&(*root)->RChild);
    }