数据结构——【万字文章+配图+代码】带你深入理解二叉树

2023-12-19 01:53:58

1. 二叉树的概念

二叉树是一种有限集合，由根和左右子树构成，每个结点最多有两棵子树，且这两棵子树具有顺序关系
请添加图片描述

2. 二叉树的特殊情况：

2.1 满二叉树：

一个二叉树，如果每次的结点都达到最大值，那么这个数就是满二叉树。如果一个二叉树有k层，且结点的总个数为2^k^-1，则它就是一个满二叉树

请添加图片描述

2.2 完全二叉树：

如果设二叉树的深度为h，那么除了第h层外，其它各层 (即1~h-1层) 的结点数都达到最大个数；同时，第h层所有的结点都连续集中在最左边。满二叉树是一种特殊的完全二叉树。

请添加图片描述

3. 二叉树的性质：

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1）个结点。（第一层1个，第二层2个，第三层4个，第四层8个……）
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1
对任何一颗二叉树，如果度为0其叶结点个数为n₀，度为2的分支结点个数为n₂，则有n₀=n₂+1
若规定根节点的层数为1，具有n个结点的满二叉树的深度为h=log₂(n+1)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，对于序号为i的结点有：
1. 若i>0,i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左子树
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右子树

4. 二叉树的存储结构

4.1 顺序结构

二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树

请添加图片描述

4.2 链式结构

二叉树的链式存储结构是指，用链接来表示一颗二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给处该结点的左孩子和右孩子所在链结点的存储地址。

请添加图片描述

5. 二叉树的实现

5.1 二叉树的创建

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//如果数组已经遍历完或者当前节点的是空姐发，则返回空指针
	if (*pi >= n || a[*pi] == '#')
	{
		//当前节点为空，返回NULL
		(*pi)++;
		return nullptr;
	}
	//创建新节点并赋初值
	BTNode* root = new BTNode;
	root->_data = a[*pi];
	root->_left = nullptr;
	root->_right = nullptr;
	(*pi)++;
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

5.2 二叉树的销毁

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == nullptr)
	{
		//如果当前节点为空直接返回
		return;
	}
	//递归销毁左子树和右子树
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	//释放当前节点的内容
	free(*root);
	*root = nullptr;
}

5.3 二叉树节点个数

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空返回0
		return 0;
	}
	//返回左子树节点个数+右子树节点个数+1
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

5.4 二叉树叶子节点个数

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回0
		return 0;
	}
	if (root->_left == nullptr && root->_right == nullptr)
	{
		//如果当前节点是叶子节点，返回1
		return 1;
	}
	//返回左子树叶子节点个数+右子树叶子节点个数
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

5.5 二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回0
		return 0;
	}
	if (k == 1)
	{
		//如果当前节点是第k层节点，返回1
		return 1;
	}
	//返回左子树第k-1层节点个数+右子树第k-1层节点个数
	int leftk = BinaryTreeLevelKSize(root->_left, k - 1);
	int	rightk = BinaryTreeLevelKSize(root->_right, k - 1);
	return leftk + rightk;
}

5.6 二叉树查找值为x的节点

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回nullptr
	}
	if (root->_data == x)
	{
		//如果当前节点的值等于x,返回指向当前节点的指针
		return root;
	}
	//在左子树中查找x
	BTNode* lret = BinaryTreeFind(root->_left, x);
	//如果在左子树中找到了x，返回指向左子树中x的节点的指针
	if (lret) 
		return lret;
	//在右子树中查找x
	BTNode* rret = BinaryTreeFind(root->_right, x);
	//如果在右子树中找到了x，返回指向右子树中x的节点的指针
	if (rret)
		return rret;
	//否则返回nullptr
	return nullptr;
}

5.7 二叉树的前序遍历

//二叉树的前序遍历 根节点->左子树->右子树
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//打印当前节点的值，并递归打印左子树和右子树
	cout << root->_data << " ";
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

5.8 二叉树的中序遍历

//二叉树的中序遍历 左子树->根节点->右子树
void BinaryTreeInOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//递归打印左子树，打印当前节点的值，再递归打印右子树
	BinaryTreeInOrder(root->_left);
	cout << root->_data << " ";
	BinaryTreeInOrder(root->_right);
}

5.9 二叉树的后序遍历

//二叉树的后序遍历，左子树->右子树->根节点
void BinaryTreePostOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//递归打印左子树和右子树，再打印当前节点的值
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	cout << root->_data << " ";
}

5.10 二叉树的层序遍历

//二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == nullptr)//如果根节点为空，直接返回
	{
		return;
	}
	queue<BTNode*> q;//创建一个队列，用于存储待访问的节点
	q.push(root);//将根节点入队
	while (!q.empty())//当队列不为空时执行循环
	{
		BTNode* node = q.front();//取出队列前面的节点
		q.pop();//将该节点出队
		cout << node->_data <<" ";//输出节点数据
		if (node->_left != nullptr)//如果左子节点不为空，将其入队
		{
			q.push(node->_left);
		}
		if (node->_right != nullptr)//如果右子节点不为空，将其入队
		{
			q.push(node->_right);
		}
	}
}

5.11 判断二叉树是否是完全二叉树

//判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	if (root == nullptr) //如果根节点为空，则空树是完全二叉树
	{
		return 1;
	}
	BTNode* queue[1000];//定义一个队列用于存储待访问的节点
	int front = 0, rear = 0;//初始化队列的前后指针
	queue[rear++] = root;//将根节点入队
	int flag = 0;//标记是否存在空树
	while (front < rear)//当前队列不为空时，继续循环
	{
		BTNode* node = queue[front++];//取出队列前面的节点
		if (node->_left != nullptr)//如果左子树不为空
		{
			//如果之前出现过空子树，则该树不是完全二叉树
			if (flag)//如果之前出现过空子树，则该数不是完全二叉树
			{
				return 0;
			}
			queue[rear++] = node->_left;//将左子节点入栈
		}
		else//如果左子树为空
		{
			flag = 1;//标记存在空子树
		}
		if (node->_right != nullptr)//如果右子节点不为空
		{
			//如果之前出现过空子树，则该树不是完全二叉树
			if (flag)
			{
				return 0;
			}
			queue[rear++] = node->_right;//将右子节点入队
		}
		else//如果右子节点为空
		{
			flag = 1;//标记存在空子树
		}
	}
	//如果队列中所有节点均无左右孩子，则该树是完全二叉树
	return 1;
}

5.12 二叉树完整代码

#include<stdlib.h>
#include<iostream>
#include<queue>
using namespace std;
typedef int BTDataType;
//创建一个结构体表示节点
typedef struct BinaryTreeNode
{
	BTDataType _data;//数据域
	struct BinaryTreeNode* _left;//左指针域
	struct BinaryTreeNode* _right;//右指针域
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	//如果数组已经遍历完或者当前节点的是空姐发，则返回空指针
	if (*pi >= n || a[*pi] == '#')
	{
		//当前节点为空，返回NULL
		(*pi)++;
		return nullptr;
	}
	//创建新节点并赋初值
	BTNode* root = new BTNode;
	root->_data = a[*pi];
	root->_left = nullptr;
	root->_right = nullptr;
	(*pi)++;
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == nullptr)
	{
		//如果当前节点为空直接返回
		return;
	}
	//递归销毁左子树和右子树
	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	//释放当前节点的内容
	free(*root);
	*root = nullptr;
}

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空返回0
		return 0;
	}
	//返回左子树节点个数+右子树节点个数+1
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回0
		return 0;
	}
	if (root->_left == nullptr && root->_right == nullptr)
	{
		//如果当前节点是叶子节点，返回1
		return 1;
	}
	//返回左子树叶子节点个数+右子树叶子节点个数
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回0
		return 0;
	}
	if (k == 1)
	{
		//如果当前节点是第k层节点，返回1
		return 1;
	}
	//返回左子树第k-1层节点个数+右子树第k-1层节点个数
	int leftk = BinaryTreeLevelKSize(root->_left, k - 1);
	int	rightk = BinaryTreeLevelKSize(root->_right, k - 1);
	return leftk + rightk;
}

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == nullptr)
	{
		//如果当前节点为空，返回nullptr
	}
	if (root->_data == x)
	{
		//如果当前节点的值等于x,返回指向当前节点的指针
		return root;
	}
	//在左子树中查找x
	BTNode* lret = BinaryTreeFind(root->_left, x);
	//如果在左子树中找到了x，返回指向左子树中x的节点的指针
	if (lret) 
		return lret;
	//在右子树中查找x
	BTNode* rret = BinaryTreeFind(root->_right, x);
	//如果在右子树中找到了x，返回指向右子树中x的节点的指针
	if (rret)
		return rret;
	//否则返回nullptr
	return nullptr;
}

//二叉树的前序遍历 根节点->左子树->右子树
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//打印当前节点的值，并递归打印左子树和右子树
	cout << root->_data << " ";
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

//二叉树的中序遍历 左子树->根节点->右子树
void BinaryTreeInOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//递归打印左子树，打印当前节点的值，再递归打印右子树
	BinaryTreeInOrder(root->_left);
	cout << root->_data << " ";
	BinaryTreeInOrder(root->_right);
}

//二叉树的后序遍历，左子树->右子树->根节点
void BinaryTreePostOrder(BTNode* root)
{
	if (root == nullptr)
	{
		//如果当前节点为空，直接返回
		return;
	}
	//递归打印左子树和右子树，再打印当前节点的值
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	cout << root->_data << " ";
}

//二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == nullptr)//如果根节点为空，直接返回
	{
		return;
	}
	queue<BTNode*> q;//创建一个队列，用于存储待访问的节点
	q.push(root);//将根节点入队
	while (!q.empty())//当队列不为空时执行循环
	{
		BTNode* node = q.front();//取出队列前面的节点
		q.pop();//将该节点出队
		cout << node->_data <<" ";//输出节点数据
		if (node->_left != nullptr)//如果左子节点不为空，将其入队
		{
			q.push(node->_left);
		}
		if (node->_right != nullptr)//如果右子节点不为空，将其入队
		{
			q.push(node->_right);
		}
	}
}

//判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	if (root == nullptr) //如果根节点为空，则空树是完全二叉树
	{
		return 1;
	}
	BTNode* queue[1000];//定义一个队列用于存储待访问的节点
	int front = 0, rear = 0;//初始化队列的前后指针
	queue[rear++] = root;//将根节点入队
	int flag = 0;//标记是否存在空树
	while (front < rear)//当前队列不为空时，继续循环
	{
		BTNode* node = queue[front++];//取出队列前面的节点
		if (node->_left != nullptr)//如果左子树不为空
		{
			//如果之前出现过空子树，则该树不是完全二叉树
			if (flag)//如果之前出现过空子树，则该数不是完全二叉树
			{
				return 0;
			}
			queue[rear++] = node->_left;//将左子节点入栈
		}
		else//如果左子树为空
		{
			flag = 1;//标记存在空子树
		}
		if (node->_right != nullptr)//如果右子节点不为空
		{
			//如果之前出现过空子树，则该树不是完全二叉树
			if (flag)
			{
				return 0;
			}
			queue[rear++] = node->_right;//将右子节点入队
		}
		else//如果右子节点为空
		{
			flag = 1;//标记存在空子树
		}
	}
	//如果队列中所有节点均无左右孩子，则该树是完全二叉树
	return 1;
}

int main()
{
	BTDataType a[] = { 'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#' };
	int n = sizeof(a) / sizeof(a[0]);
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, n, &i);
	cout<<"二叉树节点个数：" << BinaryTreeSize(root) << endl;
	cout << "二叉树叶子节点的个数：" << BinaryTreeLeafSize(root) << endl;
	cout << "二叉树第1层节点个数："<<BinaryTreeLevelKSize(root,1)<<endl;
	cout << "二叉树第2层节点个数：" << BinaryTreeLevelKSize(root, 2) << endl;
	cout << "二叉树第3层节点个数：" << BinaryTreeLevelKSize(root, 3) << endl;
	cout << "二叉树查找值为x的节点："<<BinaryTreeFind(root,'A') << endl;
	cout << "二叉树的前序遍历：";
	BinaryTreePrevOrder(root);
	cout << endl;
	cout << "二叉树的中序遍历：";
	BinaryTreeInOrder(root);
	cout << endl;
	cout << "二叉树的后序遍历：";
	BinaryTreePostOrder(root);
	cout << endl;
	cout << "二叉树的层序遍历：";
	BinaryTreeLevelOrder(root);
	cout << endl;
	if (BinaryTreeComplete(root) == 1)
	{
		cout << "完全二叉是树" << endl;
	}
	else
	{
		cout << "不是完全二叉树" << endl;
	}
	return 0;
}

6. 二叉搜索树

6.1 二叉搜索树概念

二叉搜索搜又称二叉排序树，它或者是一颗空树

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

6.2 二叉搜索树的查找

从根开始比较，查找，比根大的往右边走查找，比根小则往左走查找
最多查找高度次，走到空，还没找到，这个值不存在

6.3 二叉搜索树的插入

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点

6.4 二叉搜索树的删除

首先查找元素是否在二叉树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况

要删除的结点无孩子结点
要删除的结点只有左孩子结点
要删除的结点只有右孩子结点
要删除的结点有左、右孩子结点

看起来有待删除结点有4种情况，实际情况1可以与情况2或者3合起来，因此真正的删除过程如下：

情况2：删除该结点且使被删除结点的双亲结点指向被删除节点的左孩子结点——直接删除

情况3：删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点——直接删除

情况4：在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除结点中，再来处理该结点的删除问题——替换法删除

6.5 二叉搜索树的实现

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class BST {
public:
    TreeNode* insert(TreeNode* root, int val) {
        if (root == NULL) {
            return new TreeNode(val);
        }
        if (val < root->val) {
            root->left = insert(root->left, val);
        }
        else if (val > root->val) {
            root->right = insert(root->right, val);
        }
        return root;
    }

    void inorderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
};

int main() {
    BST bst;
    TreeNode* root = NULL;
    root = bst.insert(root, 5);
    root = bst.insert(root, 3);
    root = bst.insert(root, 7);
    root = bst.insert(root, 2);
    root = bst.insert(root, 4);
    root = bst.insert(root, 6);
    root = bst.insert(root, 8);

    cout << "中序遍历二叉搜索树：";
    bst.inorderTraversal(root);
    cout << endl;

    return 0;
}

6.6 二叉搜索树的应用

K模型：K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值
KV模型：每一个关键码key，都有与之对应的值Value，即<Key,Value>的键值对，比如：英汉词典、统计单词次数

文章来源:https://blog.csdn.net/weixin_51799303/article/details/135072243
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！