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

目录

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

 二,二叉树的遍历

 三,二叉树的基本运算

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

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