数据结构-二叉树中的递归

目录

前言

简单手撕二叉树

二叉树节点的求解

二叉树叶子节点的求解

二叉树高度

二叉树第K层节点的个数

二叉树查找值为X的节点

结束语

前言

在这里说声抱歉，好久没更新数据结构了，二叉树的相关内容还没有更新完，是小编的失职，接下来，小编将对二叉树的内容进行补充完善。

前期我们讲解了二叉树的顺序结构（堆的实现），二叉树的遍历进行讲解，本节内容将对二叉树的节点，高度等的访问求解进行讲解。而这些问题都要用到递归的思想，一步步拆成小问题进行解答。

简单手撕二叉树

首先我们将简单手撕一个二叉树，一个节点包括值和孩子兄弟的指针，在将一个个节点连接起来就可以构造一个简单的二叉树。

typedef struct BTnode {
	int val;
	struct BTnode* left;
	struct BTnode* right;
}Node;

//节点创建
Node* BuyNode(int x) {
	Node* node = (Node*)malloc(sizeof(Node));
	if (node == NULL) {
		perror("node fail");
		return NULL;
	}
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
//树的创建
Node* CreatTree() {

	Node* node1 = BuyNode(1);
	Node* node2 = BuyNode(2);
	Node* node3 = BuyNode(3);
	Node* node4 = BuyNode(4);
	Node* node5 = BuyNode(5);
	Node* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

二叉树节点的求解

如果树是空树，则返回0，不是空树，可以拆成左子树+右子树+1（递归调用）

int TreeSize(Node* root)
{
	static int size = 0;
	if (root == NULL)
		return 0;
	else
		++size;

	TreeSize(root->left);
	TreeSize(root->right);

	return size;
}

来看这段代码，思路上没有什么问题，第一次运行的结果也将是正确的，担当我们连续求就会出问题，结果是递增的，就会出错。

由于size是静态变量，它在整个程序的生命周期内只会被初始化一次。这意味着，如果在计算不同二叉树的节点数量时调用这个函数，size的值将不会重置为0，而是会从上一次调用结束时的值继续增加。这会导致计算结果不正确。

故正确的做法是在每次计算之前将size重置为0。

衍生出下面得到代码形式，设置成全局变量或者多传一个参数。

int size = 0;
int TreeSize(Node* root)
{
	if (root == NULL)
		return 0;
	else
		++size;

	TreeSize(root->left);
	TreeSize(root->right);

	return size;
}

void TreeSize(Node* root, int* psize)
{
	if (root == NULL)
		return 0;
	else
		++(*psize);

	TreeSize(root->left, psize);
	TreeSize(root->right, psize);
}

两个代码原理其实都是差不多的，只是后面一个将size变成了指针形参。当然也可以直接返回，将++size直接结合到递归中。

int TreeSize(Node* root) {
	if (root == NULL) {
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

二叉树叶子节点的求解

二叉树叶子节点求解是一样的思路，1.空树->0  2.非空 左子树和右子树是否为空

同样递归的思想。

• if (root == NULL)：检查当前节点是否为NULL，如果是，则表示已经到达了树的末尾，没有叶子节点，返回0。

• if (root->left == NULL && root->right == NULL)：检查当前节点是否是叶子节点，即它的左右子节点都为NULL。如果是，返回1，表示找到了一个叶子节点。

• return TreeLeafSize(root->left) + TreeLeafSize(root->right);：如果当前节点不是叶子节点，那么递归调用TreeLeafSize函数，分别计算当前节点的左子树和右子树中的叶子节点数量，并将这两个数量相加返回。

int TreeLeafSize(Node* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
		return 1;
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

二叉树高度

对于二叉树的高度，我们可以一层层加，转化为子问题 ，就是在左右子树中高的子树高度加1即可。

int height(Node* root) {
	if (root == NULL) {
		return 0;
	}
	
	return (height(root->left)>height(root->right)?height(root->left):height(root->right)) + 1;
}

上面这个版本虽然能计算出二叉树的高度，但是我们会发现它会冗余的进行递归，在进行比较后，又会递归求解比较高的子树，然后又会进行递归，所以我们可以每次递归后将树的高度用变量保存起来。 

int Height(Node* root) {
	if (root == NULL) {
		return 0;
	}
	int left = Height(root->left);
	int right = Height(root->right);
	return (left > right ? left : right) + 1;
}

二叉树第K层节点的个数

int TreeKSize(Node* root, int k) {
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return(TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1));
	}

通过递归的方式，一层层地向下遍历树，直到达到深度 k，然后统计该层上的节点数量。最终，函数返回所有深度为 k 的节点总数。

二叉树查找值为X的节点

最先想到的肯定是遍历二叉树，如果值相等，就返回节点。

我们同样可以采用递归的方式

Node* Treefind(Node* root, int x) {
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	Node* ret1 = Treefind(root->left, x);
	if (ret1)
		return ret1;
	Node* ret2 = Treefind(root->right, x);
	if (ret2)
		return ret2;
	
	return NULL;
	
}

递归展开图

上面代码简化一下： 

Node* TreeFind(Node* root, int x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == x) {
		return root;
	}
	Node* leftResult = TreeFind(root->left, x);
	if (leftResult != NULL) {
		return leftResult;
	}
	return TreeFind(root->right, x);
}

• if (root == NULL) { return NULL; }：首先检查当前节点是否为 NULL。如果是，表示已经到达了树的末尾，没有找到值为 x 的节点，因此返回 NULL。

• if (root->val == x) { return root; }：检查当前节点的值是否等于 x。如果等于，表示找到了目标节点，返回当前节点的指针。

• Node* leftResult = TreeFind(root->left, x);：递归地在左子树中查找值为 x 的节点。

• if (leftResult != NULL) { return leftResult; }：如果左子树中找到了值为 x 的节点（即 leftResult 不为 NULL），则直接返回该节点的指针。

• return TreeFind(root->right, x);：如果左子树中没有找到，那么递归地在右子树中查找值为 x 的节点，并返回结果。

这个函数使用了深度优先搜索（DFS）策略，优先在左子树中查找，如果左子树中没有找到，则继续在右子树中查找。一旦找到值为 x 的节点，就立即返回，不再继续搜索。

这个函数是有效的，并且它的效率取决于树的结构。在最坏的情况下，如果树是完全不平衡的，例如退化成一条链表，那么时间复杂度将是 O(n)，其中 n 是树中节点的数量。在平衡二叉树的情况下，时间复杂度将是 O(log n)。（了解）

补充：

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。在这种算法中，沿着一个分支遍历，直到这个分支的末端，然后回溯并沿着另一分支进行遍历，直到所有的节点都被访问过。

以下是深度优先搜索的基本步骤：

1. 选择一个起始节点：从图或树的某个节点开始。

2. 探索：从当前节点出发，选择一个相邻的节点进行深入访问。这个相邻节点必须是未被访问过的。

3. 标记：在访问一个节点时，将其标记为已访问，以避免重复访问。

4. 回溯：如果当前节点没有未访问的相邻节点，或者所有的相邻节点都已被访问过，那么算法回溯到上一个节点，继续寻找下一个未访问的相邻节点。

5. 重复步骤2-4：直到所有的节点都被访问过。

深度优先搜索可以使用递归或栈（迭代方式）来实现。

结束语

本节内容就到此结束了，大家对于递归的理解可以通过画图来理解，递归是一个很重要的思想。

最后感谢各位友友的支持！！！