手撕链式二叉树（二）—【C语言】

链式二叉树（一）         http://t.csdn.cn/HWu6E

目录

1. 二叉树找值为x的节点

代码实现分析

 代码实现

递归展开图

2. 求二叉树层数

代码思路分析

代码实现 

 3. 二叉树的销毁

代码思路分析

代码实现

运行结果

4. 二叉树的一些OJ题目

1. 单值二叉树                      OJ链接跳转 

2. 检查两颗树是否相同       OJ链接跳转

3. 对称二叉树                      OJ链接跳转

4. 二叉树的前序遍历           OJ链接跳转

5. 二叉树中序遍历              OJ链接跳转

6. 二叉树的后序遍历           OJ链接跳转

7. 另一颗树的子树              OJ链接跳转

---

1. 二叉树找值为x的节点

代码实现分析

代码步骤分析：

1. 判断根节点是不是空，是空就返回NULL

2. 不是NULL，就判断该节点的数据是不是要找的数据，是 —>（找到了，一层一层返回上去）

3. 不是要找的数据，就开始调用左子树（如果左子树一直没找到），从最后递归到的NULL开始返回，返回到调用的地方，然后开始调用最后一层的右子树,如果左子树和右子树都递归完了，还没找到就返回NULL

4. 如果一颗二叉树左子树和右子树都有要找的值，只要先找到其中一个，该值就会被一层一层的返回上去，剩下相同的值就不会找找了

 代码实现

// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
 
	if (root->data == x)
		return root;
 
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
 
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
 
	return NULL;
}

递归展开图

举例：假设我们这里找5这个节点

注意：我这里把5的位置换了下，让他在左子树就可以被找到（还是画出的左子树的递归图）

---

过程讲解：1. 一直递归调用左边，递归到3的左儿子是NULL，返回到调用NULL的地方，开                          始调用3的右儿子，发现也是NULL

                  2. 这时返回到调用3的地方，3是被2的左边调用的，返回后，开始递归2的右儿子

                  3. 这时要找的数据x和data相同，if条件符合，执行return，然后就开始返回上去

                  4. 首先返回到2调用右儿子的地方，if语句为真，继续返回，返回到2被1调用的地                        方

                  5. 还是if条件为真，返回出去了，这时整个递归就结束了

---

---

2. 求二叉树层数

---

---

代码思路分析

代码实现分析：

1. 先判断根节点是不是为空，为空就返回NULL，就结束了

2. 走到这里那根节点就不是空，不是空就开始一直递归树的左边，递归到3的左儿子，左儿子是空，这时if条件判断成立，就返回0，开始递归3的右儿子，右儿子也为NULL，这时左返回的层数和右返回的层数比较，由于左边和右边一样都为0，那就随便返回一个+1

3. 节点3的左右儿子都返回完了，这时开始递归调用2的右子树，右子树为空，和3返回的作比较，3返回的值大，那就返回层数2

4. 后面和3的逻辑差不多，最后就是比较节点2返回的层数和4返回的层数谁大，然会就返回给1，节点1再+1，然会就返回出去，结束整个递归

---

通过上面的分析可以看出，这个是二叉树遍历顺序中的后序遍历

代码实现 

int TreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = TreeDepth(root->left);
	int rightDepth = TreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
 
}

---

---

 3. 二叉树的销毁

---

代码思路分析

前中后序遍历，哪个更适合这里的二叉树销毁呢？

---

如果采用前序遍历去销毁，一进来就销毁根节点，节点中存着的左孩子和右孩子的指针，如果我们一进来就销毁根节点，这时的左右孩子指针就也被销毁了，不能遍历下去了

中序遍历也一样

---

后序遍历访问根的顺序——左子树—>右子树—>根，所以我们使用后序遍历可以轻松的避免上面的问题发生

代码实现

通过上面可以知道是后续遍历，代码步骤分析如下

1. 还是一开始就递归调用左边，递归到NULL就返回，开始递归调用右边，右边到NULL，然      后就释放节点，这时就回到2，先不销毁2，先递归2的右边，是NULL，然后就销毁节点2

2. 节点2销毁后，就返回1的右边，开始递归调用1的右孩子》》》（原理和左边相同）

void TreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

运行结果

注意点：一般递归不好调试，我们可以借助打印，来理解

由于我们使用的是后序遍历，所以我们这里打印的销毁节点的顺序，就是后序遍历的顺序

---

---

4. 二叉树的一些OJ题目

下面是一些Leetcode上的一些二叉树练习题，价值还是蛮高的，可以点击OJ链接跳转去做题

后面小余也会出这些题目的题解和做题心得，大家可以关注下哦！

1. 单值二叉树                      OJ链接跳转 

2. 检查两颗树是否相同       OJ链接跳转

3. 对称二叉树                      OJ链接跳转

4. 二叉树的前序遍历           OJ链接跳转

5. 二叉树中序遍历              OJ链接跳转

6. 二叉树的后序遍历           OJ链接跳转

7. 另一颗树的子树              OJ链接跳转

---

---

如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！