【数据结构与算法】二叉树的知识讲解

目录

 一，二叉树的结构深入认识

 二，二叉树的遍历

 三，二叉树的基本运算

3-1，计算二叉树的大小

3-2，统计二叉树叶子结点个数

3-3，计算第k层的节点个数

3-4，查找指定值的结点

---

一，二叉树的结构深入认识

        二叉树是不可随机访问的，二叉树的结构是通过双亲结点与孩子结点之间的连接进行遍历访问，因此，二叉树的结构是用链式结构来存储的。如下：

二叉树的结构

#include <stdio.h>
#include <stdlib.h>
typedef struct Tree {
    int val;//数据
    struct Tree* leftchild;//左孩子结点
    struct Tree* rightchild;//右孩子结点
}Tree;

        要说明的是，学习二叉树的结构不跟栈和队列之类的一样用于增删查改，二叉树没有这些操作，二叉树的运用比较复杂，下面会依次讲解。

---

 二，二叉树的遍历

        二叉树的遍历有：前序遍历，中序遍历，后序遍历，层序。通常，在这些遍历算法中除了层序遍历外，其它的遍历都要运用递归结构。

        1，前序遍历(也称先序遍历)——访问根结点的操作发生在遍历其左右子树之前，即遍历的

顺序为：根，左子树，右子树。

        2，中序遍历——访问根结点的操作发生在遍历其左右子树之间。即遍历的顺序为：左子树，根，右子树。

        3，后序遍历——访问根结点的操作发生在遍历其左右子树之后。即遍历的顺序为：左子树，右子树，根。

        4，层序遍历——从左到右一层一层的遍历，此遍历非常简单，就如从开始到结尾的遍历顺序表一样。

        注意：这里要说明的是，以上的遍历除了层序遍历外，其它的遍历都是递归式的遍历，可不是单纯普通式按照以上顺序循环式的遍历，正确的遍历如下图：

        说明一下，在二叉树的遍历中，前，中，后遍历的思路基本相同，而层序遍历一般要借助队的结构来实现，本篇文章先不做介绍，后文深入运用时会详细说明。前中后的三种遍历代码如下：

//前序遍历
void FrontOrder(struct Tree* root) {
	//当递归到空结点时退出
	if (root == NULL) {
		return;
	}
	//输出
	fprintf(stdout, "%d ", root->val);
	//递归左子树
	FrontOrder(root->leftchild);
	//递归右子树
	FrontOrder(root->rightchild);
}
//中序遍历
void MiddleOrder(struct Tree* root) {
	//当递归到空结点时退出
	if (root == NULL) {
		return;
	}
	//递归左子树
	MiddleOrder(root->leftchild);
	//输出
	fprintf(stdout, "%d ", root->val);
	//递归右子树
	MiddleOrder(root->rightchild);
}
//后序遍历
void RearOrder(struct Tree* root) {
	//当递归到空结点时退出
	if (root == NULL) {
		return;
	}
	//递归左子树
	RearOrder(root->val);
	//递归右子树
	RearOrder(root->val);
	//输出
	fprintf(stdout, "%d ", root->val);
}

解析：

        递归本身有点不好理解，而上面的递归遍历中，当进行递归遍历时，可看做从此函数的根结点开始不断往下面的左右孩子结点遍历，当递归到根结点为空时结束下一次递归，并返回到此结点的双亲结点，可以说二叉树的递归遍历是不断往下层进行的，只有当遍历到最下层或下层的空结点时才返回，也就是递归遍历是从最后开始，然后不断往回返，直到返回到二叉结构的根节点才结束整个递归程序。

补充：

        函数的递归其实跟我们学习的栈结构一样，递归入函数(即进入函数栈帧)相当于入栈，出函数(即函数栈帧的销毁)相当于出栈。

学习建议：

        遍历思想是学习二叉树的基本，很多二叉树的算法思想都要在此递归遍历的思想上进行开阔的，因此，如果这中递归思路不明白，一定要先理清思路，不建议先往后面看。

---

三，二叉树的基本运算

        在讲解这一部分内容前，我们要先明白递归中设置局部变量的用法。

二叉树递归设置局部变量的注意：

        在二叉树计数中，我们难免要设定局部变量，而在进行递归返回中可能有些人说函数的返回值会覆盖之前的值，不明白为什么覆盖后的值就是我们想要统计的数值。其实这原理很简单，在讲解二叉树遍历的解析说过，二叉树的递归遍历是不断往下层进行的，只有当遍历到最下层时才返回，也就是递归程序是从最后开始，不断往前返回，当我们递归遍历二叉树时，满足计数的条件会不断往上层返，这时计数的值相当于以此函数中root为根结点的子树的以下计数值，也就是我们要统计的数值。

3-1，计算二叉树的大小

        计算二叉树的大小说白了就是确定有几个不为空的结点，此算法比较简单，我们可直接遍历整个二叉结构不断加一来实现。代码如下：

//统计二叉树中叶子结点的个数
int TreeSize(Tree* root) {
	//当为空结点时说明此时为0
	if (root == NULL) {
		return 0;
	}
	//不断递归遍历，遍历一个结点加1。
	return TreeSize(root->leftchild) + TreeSize(root->rightchild) + 1;
}

        以上代码虽然省力，但可能对于部分人来说比较难理解，展开后的代码如下：

int TreeSize(Tree* root) {
	if (root == NULL) {
		return 0;
	}
	//遍历左子树的结点个数
	int leftsize = TreeSize(root->leftchild);
	//遍历右子树的结点个数
	int rightsize = TreeSize(root->rightchild);
	//返回以此结点为根结点的二叉树结点个数，此二叉树是子二叉树
	return leftsize + rightsize + 1;
}

        对于当初学者笔者建议用展开后的代码，对递归了解比较深入后再用合成版代码。

3-2，统计二叉树叶子结点个数

        此算法与计算二叉树的结点个数方法相似，不同的是，当进行递归遍历时，我们可利用叶子结点的左右孩子都为空的特点来计数，当递归遍历时满足这一特点进行计数，不满足进行递归遍历，代码如下：

int LeavesNodeSize(Tree* root) {
	if (root == NULL) {
		return 0;
	}
    //当此结点是叶子结点时，计数1
	if (root->leftchild == NULL && root->rightchild == NULL) {
		return 1;
	}
	//左孩子结点的叶子结点数
	int count1 = LeavesNodeSize(root->leftchild);
	//右孩子结点的叶子结点数
	int count2 = LeavesNodeSize(root->rightchild);
    //返回当前以root为根结点的子二叉树的叶子结点总个数
	return count1 + count2;
}

        当我们明白以上原理后可进行简化算法，跟之前一样，先理清以上思路再进行简化。如下：

int LeavesNodeSize(Tree* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->leftchild == NULL && root->rightchild == NULL) {
		return 1;
	}
	return LeavesNodeSize(root->leftchild) + LeavesNodeSize(root->rightchild);
}

3-3，计算第k层的节点个数

        记录第k层的二叉树结点也是同理，在递归遍历过程中，往下层递归一次将k减1，当k==1时就递归到了第k层，也就是在此时开始计数，而函数返回值将返回以此函数中的root为根结点的子二叉树的第k层结点数。

int NodeCount(Tree* root, int k) {
	if (root == NULL) {
		return 0;
	}
	//当k == 1 时此时遍历到了第k层，此时计数
	if (k == 1) {
		return 1;
	}
	//以此函数的root为根结点以下的子二叉树第k层的左孩子结点数
	int leftchild = NodeCount(root->leftchild, k - 1);
	//以此函数的root为根结点以下的子二叉树第k层的右孩子结点数
	int rightchild = NodeCount(root->rightchild, k - 1);
	//返回以此函数的root为根结点以下的子二叉树第k层的结点数
	return leftchild + rightchild;
}

        算法合并简化后如下：

int NodeCount(Tree* root, int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return NodeCount(root->leftchild, k - 1) + NodeCount(root->rightchild, k - 1);
}

3-4，查找指定值的结点

        此算法的坑比较多，首先我们要考虑的是当遍历到要查找的结点时如何停止遍历，并最终返回该结点。要知道一点，当我们要查找的结点在中间时，直接返回是上一次的递归函数，因此，我们要做的是让查找的指定结点不断返回，直到递归结束。

        算法详细步骤如下：

Tree* FoundNode(Tree* root, int x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == x) {
		return root;
	}
	Tree* leftchild = FoundNode(root->leftchild, x);
	//当左孩子是我们要找的结点时就不往下继续遍历了，直接返回此结点
	if (leftchild != NULL && leftchild->val == x) {
		return leftchild;
	}
	Tree* rightchild = FoundNode(root->rightchild, x);
	//当左孩子是我们要找的结点时就不往下继续遍历了，直接返回此结点
	if (rightchild != NULL && rightchild->val == x) {
		return rightchild;
	}
	//当查找不到返回NULL
	return NULL;
}

        算法的化简代码如下：

Tree* FoundNode(Tree* root, int x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == x) {
		return root;
	}
	Tree* leftchild = FoundNode(root->leftchild, x);
	//当左孩子是我们要找的结点时就不往下继续遍历了，直接返回此结点
	if (leftchild != NULL && leftchild->val == x) {
		return leftchild;
	}
	//遍历右结点，当右孩子是我们要找的结点时返回此结点
	return FoundNode(root->rightchild, x);
}

---

总结：学习到这里学者们明显感到难度增大了，不过也不用担心，只要我们多多思考并加之练习，其实逻辑也不是那么难，上面的算法程序笔者之所以将步骤展开和步骤合并一并写入，就是为了让大家多多练习以上的思路，其实逻辑也都是一样的，只是为了强化思维罢了。