【C语言 || 数据结构】二叉树

前言

二叉树是一种基本且高效的数据结构，每个节点最多有两个子节点：左子节点和右子节点。由于其结构简洁和操作的便捷性，二叉树在计算机科学领域有着广泛的应用。

二叉树

这是棵二叉树，”very标准"的一颗二叉树

1.树

树是一种非线性的数据结构，是由n（n>=0）个有限节点组成一个具有层次关系的集合。把他叫做树，是因为他是一个倒挂的树，也就是根是朝上的，而叶子是朝下的。
根节点：这棵树的根。

1.1树的定义

• 结点的度：一个结点含有的子树的个数称为该结点的度；
• 叶子结点或终端结点：度为0的结点称为叶子结点；
• 非终端结点或分支结点：度不为0的结点；
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
• 兄弟结点：具有相同父结点的结点互称为兄弟结点；
• 树的度：一棵树中，最大的结点的度称为树的度；
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
• 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
• 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林；

1.2 树的结构

我们应该如何来定义这棵树，

struct Tree
{
	TDataType a;
	struct SeqList Sq; //这里需要定义一个顺序表来记载节点地址
};

是这样定义一个顺序表嘛，这样不会觉得很麻烦嘛。
于是就有一个人提出了“左孩子，右兄弟”的结构。

struct Tree
{
	TDataType a;
	struct Tree* leftchild;
	struct Tree* rightborther;
};

2.特殊的树（二叉树）

2.1 二叉树的概念

二叉树（Binary Tree）是一种特殊的树形数据结构，它的每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树具有递归的性质，即一个二叉树由根节点、左子树和右子树组成，而左子树和右子树又分别可以是二叉树。

2.2 特殊的二叉树

• 满二叉树：每一层都是满的，节点个数等于2的层数-1次方。
• 完美二叉树：前n-1层都是满的，最后一层从左到右是不间断的，最少的完美二叉树，最下面一层只有一个节点。

2.3 二叉树的储存

二叉树的储存是有两种，一个是数组储存，一个是链表储存。

2.3.1 顺序储存二叉树

就是由数组来储存，物理是数组，逻辑上是二叉树，顺序二叉树，最好是完美二叉树，那样就可以符合孩子找得到“爹”，“爹”找的到孩子的情况：

• parent = (child-1) / 2;
• child = parent * 2 + 1;

这个主要是运用在堆中，可以使用数组来储存二叉树。

2.3.2 链表储存二叉树

在这里用链表来储存二叉树，是可以直接用“左孩子，右孩子”的思想

typedef int BTDataType;
typedef struct BinaryTree 
{
	BTDataType val;
	struct Tree* leftchild;
	struct Tree* rightborther;
}BTNode;

2.4 二叉树的遍历

二叉树的遍历是按照递归来进行的，主要是分为前序遍历，中序遍历和后序遍历来遍历二叉树的，前序是按照“根-左子树-右子树”的顺序遍历的，中序是按照“左子树-根-右子树”的顺序遍历的，后序是按照“左子树-右子树-根”的顺序遍历的。

2.4.1 二叉树的中序遍历

二叉树的中序遍历是按照“左孩子-根-右孩子” 的方式进行的。直到遇到空才开始返回。

// 二叉树中序遍历 
void BinaryTreeOrder(BTNode* root)
{
	if(root == NULL)
		return;
		
	BinaryTreePrevOrder(root->left);
	printf("%d ",root->val);
	BinaryTreePrevOrder(root->right);
}

2.4.2 二叉树的前序遍历

二叉树的前序遍历是按照“根-左孩子-右孩子” 的方式进行的，只有当左孩子遇到空才开始返回，并输出值。

// 二叉树中序遍历 
void BinaryTreeprevOrder(BTNode* root)
{
	if(root == NULL)
		return;
		
	printf("%d ",root->val);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

2.4.3 二叉树的后序遍历

二叉树的前序遍历是按照“左孩子-右孩子-根” 的方式进行的，只有当左孩子遇到空才开始返回，并输出值。

// 二叉树中序遍历 
void BinaryTreePostOrder(BTNode* root)
{
	if(root == NULL)
		return;
		
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%d ",root->val);
}

2.5 二叉树的接口函数

2.5.1 二叉树的节点的创建

创建一个节点，进行malloc()，然后给他的成员赋值，最后返回。

BTNode* BinaryTreeNode(BTDataType x)
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if(tmp == NULL)
	{
		perror("malloc fail!");
		return;
	}
	tmp->left = NULL;
	tmp->right = NULL;
	tmp->val = x;

	return tmp;
	
}

2.5.2 二叉树的节点的个数

判断当前root是否为NULL，为空则返回0，非空则进入左右子树，最后加上个一，是树的根节点。

int BinaryTreeleafSize(BTNode* root)
{
	return root == 0 ? 0 : BinaryTreeleafSize(root->left) + BinaryTreeleafSize(root->right) + 1;
}

2.5.3 二叉树的深度

如果不记载下来，这个是个形参，修改形参，对实参无影响，所以使用两个变量来记载深度。

int BinaryTreeHight(BTNode* root)
{
	if(root == NULL)
		return 0;

	leftheigth = BinaryTreeHight(root->left);
	rightheigth = BinaryTreeHight(root->right);

	return leftheigth > rightheigth ? leftheigth + 1 : rightheigth + 1;
}

2.5.4 二叉树的叶子节点的个数

叶子节点就是无左子树，无右子树的节点，所以只需要判断他不是NULL，且这个节点无左子树，无右子树即可。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if(root == NULL)
		return 0;

	if(root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.5.5 二叉树第k层的节点个数

第k层是第一层的第k层，是第二层的k-1层，是第三层的k-2层。。。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int* k)
{
	if(root == NULL)
		return 0;

	if(k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left) + BinaryTreeLevelKSize(root->right);
}

2.5.6 二叉树的销毁

这里有没有必要将root制空呢，没必要，因为修改完之后的形参改变，影响不了实参的改变

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if(root == NULL)
		return ;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}