数据结构——二叉树

发布时间：2024年01月21日

目录

一、前言

1.1 树

1.2 树的相关概念?

二、二叉树

2.1 定义

2.2 特殊类型

2.3 二叉树的性质

2.4 二叉树的存储结构

（1）顺序存储

（2）链式存储

三、二叉树相关操作

3.1 创建一颗二叉树

3.2 二叉树的遍历

（1）前序遍历/先序遍历

（2）中序遍历

（3）后序遍历

（4）层序遍历

3.3 二叉树的其他操作

（1）求二叉树节点个数

（2）求二叉树的高度

（3）求二叉树第k层节点个数

（4）求二叉树叶子节点个数

（5）在二叉树中查找值为x的节点

（6）销毁二叉树

（7）判断是否为完全二叉树

四、二叉树基础OJ题练习

4.1 单值二叉树

4.2 相同的树

4.3 对称二叉树

4.4 二叉树的前序遍历

4.5 二叉树的中序遍历

4.6 二叉树的后序遍历

4.7 另一棵树的子树

4.8 二叉树的构建及遍历

一、前言

1.1 树

树是一种非线性的数据结构，它是由 n 个有限节点组成的一个具有层次关系的集合。之所以称之为“树”是因为它看起来像一颗倒挂着的树，一颗根朝上叶子朝下的树。

其中，类似A这种没有前驱节点的被称为根节点，与A相连的三个子节点与自身的后继节点构成了三颗子树。每颗子树的根节点只能有一个前驱节点，可以有多个后继节点。因此，树是递归定义的。?

需要注意的是，在树形结构中，子树之间不能有交集，否则就不是树而是图了。

1.2 树的相关概念?

关于树的相关概念，需要简单提一嘴

（1）节点的度：一个节点含有的子树的个数称为该节点的度。例如A的度为6。

（2）叶节点/终端节点：度为0的节点。例如B、H、P、L等节点。

（3）分支节点/非终端节点：度不为0的节点。例如D、E、J、F等节点。

（4）父节点/双亲节点：如果一个节点含有子节点，则该节点是自身子节点的父节点。例如A是B的父节点。

（5）子节点/孩子节点：一个节点含有的子树的根节点。例如B是A的子节点。

（6）兄弟节点：具有相同父节点的节点互称兄弟节点。例如B和C是兄弟节点。

（7）树的度：一个树中最大的节点的度就是树的度。例如A的度最大，为6，则树的度为6。

（8）节点的层次：从根开始定义，根为第一层，根的子节点为第二层，向下类推。

（9）树的高度/深度：树中节点的最大层次。例如上图树的高度为4。

（10）堂兄弟节点：父节点在同一层的节点互为堂兄弟节点。例如H和J互为堂兄弟节点。

（11）节点的祖先：从根到该节点所经的所有节点。例如A是所有节点的祖先。

（12）子孙：以某节点为根的树中任意节点都称为该节点的子孙。例如上图所有节点都是A的子孙

（13）森林：n颗互不相交的树组成的集合称为森林。

二、二叉树

2.1 定义

二叉树（Binary tree）是树形结构的一个重要类型，是指树中节点的度不大于2的有序树。

所以一颗非空二叉树由一个根节点加上两颗同样为二叉树的左右子树组成，左右子树不能颠倒。

2.2 特殊类型

（1）斜树：所有的节点都只有左子树的二叉树叫左斜树，所有节点都只有右子树的二叉树叫右斜树。

（2）满二叉树：每层的节点都是满的二叉树

（3）完全二叉树：前n-1层都是满的，最后一层可以不满，但是一定是连续的

2.3 二叉树的性质

（1）若定义根节点的层数为1，则一颗非空二叉树的第n层上最多有2^{n-1}个节点

（2）若定义根节点的层数为1，则高度为n的二叉树的最大节点数为2^{h}-1

（3）若定义根节点的层数为1，则具有n个节点的满二叉树的高度h=\log _{2}\left ( n+1 \right )

（4）对于具有n个节点的完全二叉树，如果按照从上到下从左到右的数组顺序对所有节点从0开始编号，则对于序号为i的节点：

  • 其父节点序号为\left ( i-1 \right )/2
  • 其左子节点序号为2i+1
  • 其右子节点序号为2i+2

2.4 二叉树的存储结构

二叉树可以使用两种结构来存储：顺序结构和链式结构

（1）顺序存储

顺序存储就是使用数组来存储数据，一般只有完全二叉树适合使用数组存储，因为非完全二叉树不连续，会造成空间的浪费。

在前面的数据结构——堆-CSDN博客中我们提到过，堆也是完全二叉树，而平时生活中也只有堆会用数组存储，存储顺序对应二叉树的性质四。

二叉树的顺序存储在物理上是一个数组，而在逻辑上是一颗二叉树。

（2）链式存储

用链表来表示一颗二叉树，即用链来指示节点间的逻辑关系。

链式结构存储又分为二叉链和三叉链，当前我们主要使用二叉链，即左右指针指向左孩子和右孩子所在的节点地址。后面学到高阶数据结构如红黑树才会用到三叉链。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;  //指向左孩子
	struct BinaryTreeNode* right; //指向右孩子
}BTNode;

三、二叉树相关操作

在学习二叉树的相关操作之前，我们得先有一颗二叉树。

为了降低学习成本，我们先手动创建一颗简单的二叉树，快速进入其他的操作学习。等学到高阶二叉树后我们再来研究二叉树真正的创建方式。

3.1 创建一颗二叉树

要创建二叉树，我们得先写一个创建二叉树新节点的函数

BTNode* CreateNewNode(BTDataType x) //创建新节点
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

然后手动创建一颗和下图一样的二叉树

BTNode* CreateBinaryTree() //创建二叉树
{
	BTNode* node1 = CreateNewNode(1);
	BTNode* node2 = CreateNewNode(2);
	BTNode* node3 = CreateNewNode(3);
	BTNode* node4 = CreateNewNode(4);
	BTNode* node5 = CreateNewNode(5);
	BTNode* node6 = CreateNewNode(6);

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

	return node1;
}

3.2 二叉树的遍历

二叉树遍历即按照一定的顺序依次对二叉树中的节点进行相应的操作，且每个节点只操作一次。

其中又分为前序遍历（先序遍历）、中序遍历、后序遍历和层序遍历。

前序、中序和后序遍历都是使用递归结构来实现，而层序遍历需要用到队列。

（1）前序遍历/先序遍历

先访问根节点，再依次访问左子树和右子树，即为前序遍历。

按照这个顺序，我们来遍历一遍前面创建的二叉树

前序遍历的代码如下：?

void PreOrder(BTNode* root) //二叉树前序遍历
{
	if (root == NULL)
	{
		printf("N "); //遇到空树打印N代表NULL
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

我们测试一下

（2）中序遍历

先访问左子树，再访问根节点，最后访问右子树，即为中序遍历

中序遍历的代码如下：

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

可以发现中序遍历和前序遍历只是将代码交换一下即可，后面的后序遍历也是一样。

我们测试一下

（3）后序遍历

先访问左子树和右子树，最后再访问根节点，即为后序遍历

相信经过前面的前序遍历和中序遍历后大家都能掌握遍历的过程规律了，这里就不再讲解，尝试自己算一下结果吧

后序遍历的代码如下：

void PostOrder(BTNode* root) //二叉树后序遍历
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

我们测试一下

（4）层序遍历

从上到下，从左到右逐层访问树的结点的过程就是层序遍历。

与前中后序遍历不同的是，层序遍历不使用递归，而是使用队列来实现。

队列中不是直接存放节点的值，而是存放节点的地址。

其核心思路是，上一层的节点出队列时带入下一层的节点入队列

在写层序遍历的时候，我们把之前的队列搬过来即可

层序遍历代码如下：

void LevelOrder(BTNode* root) //二叉树层序遍历
{
	Queue que;
	QueueInit(&que);
	if (root)
		QueuePush(&que, root);
	while (!QueueEmpty(&que))
	{
		BTNode* front = QueueFront(&que);
		QueuePop(&que);
		printf("%d ", front->data);
		if (front->left != NULL)
			QueuePush(&que, front->left);
		if (front->right != NULL)
			QueuePush(&que, front->right);
	}
	QueueDestroy(&que);
}

测试一下

3.3 二叉树的其他操作

（1）求二叉树节点个数

有人会想，求二叉树节点个数，遍历一下就好了。但是实际上用分治的思想更优。

分治，即分而治之，就是将一个复杂的问题分解成子问题，子问题再分解成更小子问题，直到最后子问题可以简单求解。

例如要求二叉树的节点个数，我们可以将其拆分成左子树、根和右子树。

把左子树的节点个数加上右子树的节点个数，再加上根，即为二叉树的节点个数。

而左子树和右子树也能以相同的方式进行拆分。这样就将一个大问题拆分成了许多个相同的小问题

代码如下：

int BTreeSize(BTNode* root) //求二叉树节点个数
{
	if (root == NULL)
		return 0;
	return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

测试一下

（2）求二叉树的高度

这里也可以用分治的思想，大家可以自己试一下，后面很多函数都会用到分治思想。

取左右子树的最大值，再加上自身，就是二叉树的高度

代码如下：

int BTreeHeight(BTNode* root) //求二叉树的高度
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);
	return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
}

测试一下?

这里递归的返回值必须要记录下来，不然会重复计算

（3）求二叉树第k层节点个数

代码如下：

int BTreeLevelKSize(BTNode* root, int k) //求二叉树第k层节点个数
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	int count = k - 1;
	if (count == 0) //count为0，说明到达第k层
		return 1;
	return BTreeLevelKSize(root->left, count) + BTreeLevelKSize(root->right, count);
}

测试一下

（4）求二叉树叶子节点个数

代码如下：

int BTreeLeafSize(BTNode* root) //求二叉树叶子节点个数
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL) //左右都为空树，说明是叶子节点
		return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

测试一下

（5）在二叉树中查找值为x的节点

先访问根，根不为x则访问左子树

左子树中没找到则找右子树，找到了则返回节点地址

右子树中找到了返回节点地址，没找到则说明树中没有值为x的节点，返回NULL

代码如下：

BTNode* BTreeFind(BTNode* root, BTDataType x) //在二叉树中查找值为x的节点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* left = BTreeFind(root->left, x);
	if (left)
		return left;
	BTNode* right = BTreeFind(root->right, x);
	if (right)
		return right;
	return NULL;
}

（6）销毁二叉树

销毁一颗二叉树最好使用后序，先销毁其左子树和右子树，最后销毁根节点

代码如下：

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

（7）判断是否为完全二叉树

我们知道，完全二叉树的节点必须是连续的，要判断一颗树是否为完全二叉树，最好使用层序遍历

通过层序遍历将树中的节点地址进入队列，但是与层序遍历不同，这里遇到NULL也要进队列

当我们获取队头元素时，如果是NULL，就结束入队的操作，开始检测队列中是否存在不为空的值

代码如下：

bool BTreeComplete(BTNode* root) //判断是否为完全二叉树
{
	Queue que;
	QueueInit(&que);
	if (root)
		QueuePush(&que, root);
	while (!QueueEmpty(&que))
	{
		BTNode* front = QueueFront(&que);
		if (front == NULL)
			break;
		QueuePop(&que);
		QueuePush(&que, front->left);
		QueuePush(&que, front->right);
	}
	while (!QueueEmpty(&que))
	{
		BTNode* front = QueueFront(&que);
		QueuePop(&que);
		if (front != NULL)
		{
			QueueDestroy(&que);
			return false;
		}
	}
	QueueDestroy(&que);
	return true;
}

测试一下

我们在创建二叉树的函数中手动把树补全一下

再测试一下

关于二叉树相关操作的学习就先到此为止，接下来我们来看看关于二叉树的OJ题

四、二叉树基础OJ题练习

4.1 单值二叉树

OJ题链接：965. 单值二叉树 - 力扣（LeetCode）

代码如下：

bool isUnivalTree(struct TreeNode *root)
{
    if (root == NULL)
        return true;
    bool left, right;
    if (root->left != NULL && root->val != root->left->val)
        return false;
    else
        left = isUnivalTree(root->left);
    if (root->right != NULL && root->val != root->right->val)
        return false;
    else
        right = isUnivalTree(root->right);
    return left && right;
}

4.2 相同的树

OJ题链接：100. 相同的树 - 力扣（LeetCode）

代码如下：

bool isSameTree(struct TreeNode *p, struct TreeNode *q)
{
    if (p == NULL || q == NULL)
    {
        if (p == NULL && q == NULL)
            return true;
        else
            return false;
    }
    if (p->val == q->val)
    {
        if (!isSameTree(p->left, q->left) || !isSameTree(p->right, q->right))
            return false;
        else
            return true;
    }
    else
        return false;
}

4.3 对称二叉树

OJ题链接：101. 对称二叉树 - 力扣（LeetCode）

代码如下：

bool _isSymmetric(struct TreeNode *left, struct TreeNode *right)
{
    if (left == NULL && right == NULL)
        return true;
    else if (left == NULL || right == NULL)
        return false;
    if (left->val != right->val)
        return false;
    return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}

bool isSymmetric(struct TreeNode *root)
{
    return _isSymmetric(root->left, root->right);
}

4.4 二叉树的前序遍历

OJ题链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

这里的前序遍历并不是像我们前面写的只需要把节点值打印出来，而是按照遍历顺序将值存放到一个数组中并返回数组地址

代码如下：

void PreOrder(struct TreeNode *root, int *arr, int *returnSize)
{
    if (root == NULL)
    {
        return;
    }
    arr[(*returnSize)++] = root->val;
    PreOrder(root->left, arr, returnSize);
    PreOrder(root->right, arr, returnSize);
}

int *preorderTraversal(struct TreeNode *root, int *returnSize)
{
    int *arr = (int *)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    PreOrder(root, arr, returnSize);
    return arr;
}

4.5 二叉树的中序遍历

OJ题链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

代码如下：

void InOrder(struct TreeNode *root, int *arr, int *returnSize)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left, arr, returnSize);
    arr[(*returnSize)++] = root->val;
    InOrder(root->right, arr, returnSize);
}

int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    int *arr = (int *)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    InOrder(root, arr, returnSize);
    return arr;
}

4.6 二叉树的后序遍历

OJ题链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

代码如下：

void PastOrder(struct TreeNode *root, int *arr, int *returnSize)
{
    if (root == NULL)
    {
        return;
    }
    PastOrder(root->left, arr, returnSize);
    PastOrder(root->right, arr, returnSize);
    arr[(*returnSize)++] = root->val;
}

int *postorderTraversal(struct TreeNode *root, int *returnSize)
{
    int *arr = (int *)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    PastOrder(root, arr, returnSize);
    return arr;
}

4.7 另一棵树的子树

OJ题链接：572. 另一棵树的子树 - 力扣（LeetCode）

这里我把前面相同的树中的代码cv了过来（懒狗实锤了doge）

🎊这是个小彩蛋！感觉能一点点看到这的人应该很少吧＞﹏＜

如果发现了这个彩蛋让我在评论区看到你好吗( ?? ω ?? )?

代码如下：

bool isSameTree(struct TreeNode *p, struct TreeNode *q)
{
    if (p == NULL || q == NULL)
    {
        if (p == NULL && q == NULL)
            return true;
        else
            return false;
    }
    if (p->val == q->val)
    {
        if (!isSameTree(p->left, q->left) || !isSameTree(p->right, q->right))
            return false;
        else
            return true;
    }
    else
        return false;
}

bool isSubtree(struct TreeNode *root, struct TreeNode *subRoot)
{
    if (root == NULL)
        return false;
    if (isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

4.8 二叉树的构建及遍历

OJ题链接：二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

在牛客网里写OJ题，我们就要把二叉树的一些函数贴上去啦

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* CreateNewNode(BTDataType x) //创建新节点
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

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

BTNode* TreeBuild(char* arr,int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    else 
    {
        BTNode* root = CreateNewNode(arr[*pi]);
        (*pi)++;
        root->left = TreeBuild(arr,pi);
        root->right = TreeBuild(arr,pi);
        return root;
    }
}

void InOrder(BTNode* root)
{
    if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

int main() {
    char arr[100];
    scanf("%s",arr);
    int i = 0;
    BTNode* root = TreeBuild(arr,&i);
    InOrder(root);
    BTreeDestroy(root);
    return 0;
}

完.

文章来源:https://blog.csdn.net/Eristic0618/article/details/135723033
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章