数据结构——树与二叉树

树与二叉树

1. 树的基本概念

1.1 树的定义

树(tree)是 n ( n ≥ 0 ) n(n\geq 0) n(n≥0)个结点的有限集T。当n为0时时空树，任意一棵非空树应该满足：

  • 有且仅有一个特定的结点，称为树的根(root)
  • 当 n > 1 n>1 n>1时，其余结点可分为 m ( m > 0 ) m(m>0) m(m>0)个互不相交的有限集 T 1 , T 2 . . . T m T_1,T_2...T_m T1​,T2​...Tm​，其中每一个集合本身又是一棵树，称为根的子树(subtree)

树的递归定义方式表示了树的一种固有的特性：

  • 树中至少有一个结点——根
  • 树中各子树是互不相交的集合

1.2 树的基本术语

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031645622.png

结点的度*：*一个结点含有的子树的个数称为该结点的度； 如上图：A的为6

叶结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等结点为分支结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点

树的度：一棵树中，最大的结点的度称为树的度； 如上图：树的度为6 。二叉树的度为2

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

有序树(ordered tree)、无序树：树中结点的各子树从左到右是有次序的不能互换，则称树为有序树，否则为无序树，下图为有序树

路径和路径长度：从一个祖先结点到其子孙结点的一系列边称为树中一条路径。显然，从树根到树中任一个结点都有路径，且路径唯一 路径中边的条数称为路径长度，认为每个结点到自身有长0 的路径

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031653980.png

1.3 树的表示方法

结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031657925.png

2. 二叉树

2.1 二叉树的定义

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。
与树相似，二叉树也以递归的形式定义。二叉树是 n ( n > 0 ) n(n>0) n(n>0)个结点的有限集合：
① 或者为空二叉树，即 n = 0 n=0 n=0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。

几种特殊的二叉树：

  • 满二叉树

    一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 h h h，且结点总数是 2 h − 1 2^h-1 2h−1 ，则它就是满二叉树。满二叉树的叶结点在二叉树的最下面一层，除叶结点之外每个结点的度数为2.

  • 完全二叉树

    完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于高度为 h h h的，有 n n n个结点的二叉树，当且仅当其每一个结点都与深度为 h h h的满二叉树中编号从1至 n n n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031813190.png

需要注意的是满二叉树的叶结点位于同一层，且是最后一层，而完全二叉树的位于最下层和次下层。

2.2 二叉树的性质

  • 性质1：非空二叉树上的叶结点数等于度为2的结点数加1，即

    n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1

    https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031820380.png

  • 性质2：非空二叉树的第 k k k层最多有 2 k − 1 2^{k-1} 2k−1个结点 ( k ≥ 1 ) (k\geq 1) (k≥1)

  • 性质3：高度为 h h h的二叉树至多有 2 h − 1 2^h-1 2h−1个结点 ( h ≥ 1 ) (h\geq 1) (h≥1)

  • 性质4：

    https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031836088.png

  • 性质5：具有 n n n个结点的完全二叉树的深度为 l o g 2 ( n + 1 ) log_2(n+1) log2​(n+1)或 l o g 2 n + 1 log_2n+1 log2​n+1

2.3 二叉树的存储结构

2.3.1 顺序存储

二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i i i的结点元素存储在一维数组下标为 i − 1 i-1 i−1的分量中。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031842502.png

2.3.2 链式存储

由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含3个域：数据域 data、左指针域 lchild 和右指针域 rchild。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412031844808.png

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

2.4 二叉树的遍历

二叉树的遍历除了层序遍历有递归与非递归的写法，具体如下。

若想要清晰的理解遍历，不要一味的只去看遍历的结果是多少，而是要看清楚每一步是怎么走的，包括走到空。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412032121336.png

前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 2 5 6 4 1

层序遍历结果：1 2 4 3 5 6

2.4.1 前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041619423.png

递归版本：

void PreOrder(Node *root)
{if (root==nullptr)return ;std::cout<<root->val<<" ";PreOrder(root->left);PreOrder(root->right);
}

// 带返回值的版本
void preOrder(struct TreeNode* root, int* res, int* returnSize) {if (root == NULL)return;res[(*returnSize)++] = root->val;preOrder(root->left, res, returnSize);preOrder(root->right, res, returnSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int* res = (int*)malloc(sizeof(int) * 2000);*returnSize = 0;preOrder(root, res, returnSize);return res;
}

非递归版本：

非递归是使用栈，因为递归的本质就是栈帧，故用栈来模拟。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root == nullptr)return res;stack<TreeNode*> st;TreeNode *cur=root;while(!st.empty()||cur!=nullptr){while(cur!=nullptr){res.push_back(cur->val);st.push(cur);cur=cur->left;}cur=st.top();st.pop();cur=cur->right;}return res;}
};

int* preorderTraversal(struct TreeNode* root, int* returnSize) {int *res=(int*)malloc(sizeof(int)*200);*returnSize=0;if(root==NULL)return res;struct TreeNode *st[200];int top=0;struct TreeNode *cur=root;while(top>0||cur!=NULL){while(cur!=NULL){res[(*returnSize)++]=cur->val;st[top++]=cur;cur=cur->left;}cur=st[--top];cur=cur->right;}return res;
}

2.4.2 中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041620505.png

递归版本：

void InOrder(Node *root)
{if (root==nullptr)return ;InOrder(root->left);std::cout<<root->val<<" ";InOrder(root->right);
}

void inOrder(struct TreeNode* root,int *res,int *resSize)
{if(root==NULL)return;inOrder(root->left,res,resSize);res[(*resSize)++]=root->val;inOrder(root->right,res,resSize);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int *res=(int*)malloc(sizeof(int)*200);*returnSize=0;inOrder(root,res,returnSize);return res;
}

非递归版本：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if (root == nullptr)return res;stack<TreeNode*> st;TreeNode* cur = root;while (!st.empty() || cur != nullptr) {while (cur != nullptr) {st.push(cur);cur = cur->left;}cur = st.top();st.pop();res.push_back(cur->val);cur = cur->right;}return res;}
};

2.4.3 后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041620617.png

递归版本：

void PostOrder(Node *root)
{if(root==nullptr)return ;PostOrder(root->left);PostOrder(root->right);std::cout<<root->val<<" ";
}

非递归版本：

后序遍历的非递归版本相对复杂，需要注意右子树是否为空的问题。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;if (root == nullptr)return res;stack<TreeNode*> st;TreeNode* cur = root,*prev=nullptr;while (!st.empty() || cur != nullptr) {while (cur != nullptr) {st.push(cur);cur = cur->left;}cur = st.top();st.pop();if(cur->right==nullptr||cur->right==prev){res.push_back(cur->val);prev=cur;cur=nullptr;}else{st.push(cur);cur=cur->right;}}return res;}
};

2.4.4 层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041620053.png

void LevelOrder(Node *root)
{    if(root==nullptr)return ;std::queue<Node*> q;q.push(root);while(!q.empty()){std::cout<<q.front()->val<<" ";if(q.front()->left){q.push(q.front()->left);}if(q.front()->right){q.push(q.front()->right);}q.pop();}
}
// 返回值为二维数组形式
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(root==nullptr)return res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();res.push_back(vector<int>());for (int i = 0; i < levelSize; i++) {TreeNode* temp = q.front();q.pop();res.back().push_back(temp->val);if (temp->left)q.push(temp->left);if (temp->right)q.push(temp->right);}}return res;}
};

2.5 遍历构造二叉树

对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是确定的。然而，只给出四种遍历序列中的任意一种，却无法唯一地确定一棵二叉树。若已知中序序列，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。

2.5.1 先序序列和中序序列

在先序序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根的左子树的中序序列，后一个子序列是根的右子树的中序序列。左子树的中序序列和先序序列的长度是相等的，右子树的中序序列和先序序列的长度是相等的。根据这两个子序列，可以在先序序列中找到左子树的先序序列和右子树的先序序列，如下图所示。如此递归地分解下去，便能唯一地确定这棵二叉树。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041725362.png

例如，求先序序列(ABCDEFGHI)和中序序列(BCAEDGHFI)所确定的二叉树。首先，由先序序列可知 A为二叉树的根结点。中序序列中A之前的 BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后，由先序序列可知B是左子树的根结点，D是右子树的根结点。以此类推，就能将剩下的结点继续分解下去。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041742821.png

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

struct TreeNode* createNode(int x) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = x;node->left = node->right = NULL;return node;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder,int inorderSize) {if (preorderSize == 0 || inorderSize == 0)return NULL;int index;struct TreeNode* root = createNode(preorder[0]);// 确定目前子树的左右子树的长度for (index = 0; index < inorderSize; index++) {if (inorder[index] == preorder[0])break;}root->left = buildTree(preorder + 1, index, inorder, index);root->right = buildTree(preorder + index + 1, preorderSize - index - 1,inorder + index + 1, preorderSize - index - 1);return root;
}

2.5.2 中序序列和后序序列

同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，如下图所示，然后采用类似的方法递归地进行分解，进而唯一地确定这棵二叉树。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412041824170.png

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

struct TreeNode* createNode(int x) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = x;node->left = node->right = NULL;return node;
}struct TreeNode* buildTreeFromInorderAndPostorder(int* inorder, int inorderSize, int* postorder, int postorderSize) {if (inorderSize == 0 || postorderSize == 0)return NULL;int index;struct TreeNode* root = createNode(postorder[postorderSize - 1]);// 确定目前子树的左右子树的长度for (index = 0; index < inorderSize; index++) {if (inorder[index] == postorder[postorderSize - 1])break;}root->left = buildTreeFromInorderAndPostorder(inorder, index, postorder, index);root->right = buildTreeFromInorderAndPostorder(inorder + index + 1, inorderSize - index - 1, postorder + index, postorderSize - index - 1);return root;
}

// 从右向左构建
struct TreeNode* createNode(int x) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = x;node->left = node->right = NULL;return node;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder,int postorderSize) {if (inorderSize == 0 || postorderSize == 0)return NULL;int index;struct TreeNode* root = createNode(postorder[postorderSize - 1]);for (index = inorderSize - 1; index >= 0; index--) {if (inorder[index] == postorder[postorderSize - 1])break;}root->right = buildTree(inorder + index + 1, inorderSize - index - 1,postorder + index, inorderSize - index - 1);root->left = buildTree(inorder, index, postorder, index);return root;
}

好的，我们来详细模拟一下从右向左构建二叉树的过程。

输入：

  • inorder = [9, 3, 15, 20, 7]
  • postorder = [9, 15, 7, 20, 3]

步骤1

  • postorder的最后一个元素是3，它是根节点。
  • 在inorder中找到3的位置，索引为1。

构建根节点：

    3

步骤2

  • 右子树的inorder范围是[15, 20, 7]，长度为3。
  • 右子树的postorder范围是[15, 7, 20]。

步骤3

  • postorder的最后一个元素是20，它是右子树的根节点。
  • 在inorder中找到20的位置，索引为3。

构建右子树：

    3\20

步骤4

  • 右子树的右子树的inorder范围是[7]，长度为1。
  • 右子树的右子树的postorder范围是[7]。

步骤5

  • postorder的最后一个元素是7，它是右子树的右子树的根节点。
  • 在inorder中找到7的位置，索引为4。

构建右子树的右子树：

    3\20\7

步骤6

  • 右子树的左子树的inorder范围是[15]，长度为1。
  • 右子树的左子树的postorder范围是[15]。

步骤7

  • postorder的最后一个元素是15，它是右子树的左子树的根节点。
  • 在inorder中找到15的位置，索引为2。

构建右子树的左子树：

    3\20/  \15   7

步骤8

  • 左子树的inorder范围是[9]，长度为1。
  • 左子树的postorder范围是[9]。

步骤9

  • postorder的最后一个元素是9，它是左子树的根节点。
  • 在inorder中找到9的位置，索引为0。

构建左子树：

    3/ \9  20/  \15   7

最终构建的二叉树为：

    3/ \9  20/  \15   7

总结一下，其实不管是那种方法，最主要的一点就是划分左右子树，每一次都在更新数组区间，本质就是在更新当前结点的左右子树，因为任何一个结点都可以看作是一个根结点。

2.6 二叉树的应用

二叉树的许多应用于题目基本上都是使用递归，这一点非常重要。

2.6.1 二叉树结点个数

int TreeSize(Node *root) // 树的大小吧（结点）
{// 左右递归遍历相加return root == nullptr ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.6.2 二叉树的高度

二叉树的高度就是左右子树高度的最大值。

int TreeHeight(Node *root)
{if (root == nullptr)return 0;int left = TreeHeight(root->left);int right = TreeHeight(root->right);return left > right ? left + 1 : right + 1;
}

2.6.3 销毁二叉树

使用后序遍历来销毁二叉树。

bool DestroyTree(Node *root)
{if (root == nullptr)return false;DestroyTree(root->left);DestroyTree(root->right);free(root); root = nullptr;return true;
}

3. 树与二叉树的应用

3.1 二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉搜索树，可以为空；如果不为空，满足以下性质：

  • 非空左子树的所有键值小于其根结点的键值。
  • 非空右子树的所有键值大于其根结点的键值。
  • 左、右子树都是二叉搜索树。

按照这个性质二叉搜索树的中序遍历一定是递增序列。

二叉搜索树的具体实现在这里先不讲解，主要是说明其建立过程和原理，在查找中会详细讲解。

下面是一个二叉搜索树的建立过程：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412051333266.png

3.2 哈夫曼树

3.2.1 哈夫曼树的定义

在介绍哈夫曼树之前，先介绍几个相关的概念：

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

路径上的分支数目称为路径长度。

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。

从树的根到一个结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。

树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为

W P L = ∑ i = 1 n w i l i WPL=\sum_{i=1}^nw_il_i WPL=i=1∑n​wi​li​

在式子中 w i w_i wi​是第 i i i个结点的权值， l i l_i li​是该结点到叶结点（度为0的结点）的路径长度。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412051705554.png

计算上图的WPL：

  1. WPL=72+52+22+42=36
  2. WPL=73+53+42+21=46
  3. WPL=71+52+23+43=35

3.2.2 哈夫曼树的构造过程

对于给定的有各自权值的 n 个结点

  1. 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；

  2. 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；

  3. 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树/最优二叉树。

从上述构造过程中可以看出哈夫曼树具有如下特点:

  1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
  2. 构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1。
  3. 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
    例如，权值{17.5.2.4}的哈夫曼树的构造过程如下图所示。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412051710458.png

3.2.3 哈夫曼编码

在数据通信中,若对每个字符用相等长度的二进制位表示,称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

可以利用二叉树来设计二进制前缀编码。假设为A.B,C,D四个字符设计前缀编码，可以用下图所示的二叉树来表示，4个叶结点分别表示4个字符，且约定左分支表示 0，右分支表示1，从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码，可以证明如此得到的必为前缀编码。由下图得到字符 A,B,C,D的前缀编码分别为 0,10,110.111。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412060107279.png

哈夫曼编码是一种非常有效的数据压缩编码。由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个字符当作一个独立的结点，其权值为它出现的频度(或次数)，构造出对应的哈夫曼树。然后，将从根到叶结点的路径上分支标记的字符串作为该字符的编码。下图所示为一个由哈夫曼树构造哈夫曼编码的示例，矩形方块表示字符及其出现的次数。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412060114209.png

这棵哈夫曼树的 WPL为：WPL=1x45+3x(13+12+16)+4x(5 +9)=224

此处的 WPL 可视为最终编码得到二进制编码的长度，共 224 位。若采用3位固定长度编码，则得到的二进制编码长度为 300 位，因此哈夫曼编码共压缩了 25%的数据。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

左分支和右分支究竟是表示0还是表示1没有明确规定，因此构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且为最优。

注意如果是加权平均WPL还需要除以出现次数的总数。

4. 堆

4.1 堆的定义

如果有一个关键码的集合 K = { k 0 , k 1 , k 2 , . . . , k n − 1 } K=\{k_0, k_1, k_2, ..., k_{n-1}\} K={k0​,k1​,k2​,...,kn−1​} ，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： K i < = K 2 ∗ i + 1 K_i<=K_{2 * i+1} Ki​<=K2∗i+1​ 且 K i < = K 2 ∗ i + 2 ( K i > = K 2 ∗ i + 1 K_i<=K_{2 * i+2}\left(K_i>=K_{2 * i+1}\right. Ki​<=K2∗i+2​(Ki​>=K2∗i+1​ 且 K i > = K 2 ∗ i + 2 ) i = 0 , 1 , 2 \left.K_i>=K_{2 * i+2}\right) \mathrm{i}=0,1,2 Ki​>=K2∗i+2​)i=0,1,2。则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆满足以下性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆一定是一颗完全二叉树

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061513998.png

4.2 堆的实现

4.2.1 堆的向下调整

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。若想将其调整为小堆，那么根结点的左右子树必须都为小堆。若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061524743.png

typedef int HPDataType;
//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 堆的向下调整（小堆）
// 大堆只需要把比较的<改为>
void AdjustDown(HPDataType* a, int n, int parent)
{//child记录左右孩子中值较小的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小{child++;//较小的孩子改为右孩子}if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换Swap(&a[child], &a[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else//已成堆{break;}}
}

其时间复杂度为 O ( l o g N ) O(logN) O(logN)，最坏走完整棵树。

4.2.2 堆的向上调整

向上调整便是子节点往父节点的位置去调整。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061529727.png

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}//堆的向上调整（小堆）
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//调整到根结点的位置截止{if (a[child] < a[parent])//孩子结点的值小于父结点的值{//将父结点与孩子结点交换Swap(&a[child], &a[parent]);//继续向上进行调整child = parent;parent = (child - 1) / 2;}else//已成堆{break;}}
}

4.2.3 堆的建立

建立一个堆需要满足其左右子树都是堆，那么我们可以从下面开始调整，最后便可以建成一个堆。这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。大致过程如下图所示：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061538776.png

for (int i = (heapSize - 1 - 1) / 2; i >= 0; i--) // heapSize-1是最后一个元素的位置，再减1除2是为了计算双亲结点的位置
{AdjustDown(heap,heapSize , i);
}

时间复杂度分析：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061542821.png

结点移动的步数为：

$$

T(n)=2^0 *(h-1)+2^1 *(h-2)+2^2 *(h-3)+2^3 *(h-4)+2^{h-3} * 2+2^{h-2} * 1
$$

上述式子为一个等差乘等比的数列求和，根据高中知识，使用错位相减法。

2 ∗ T ( n ) = 2 1 ∗ ( h − 1 ) + 2 2 ∗ ( h − 2 ) + 2 3 ∗ ( h − 3 ) + 2 4 ∗ ( h − 4 ) + … + 2 h − 2 ∗ 2 + 2 h − 1 ∗ 1 2 * T(n)=2^1 *(h-1)+2^2 *(h-2)+2^3 *(h-3)+2^4 *(h-4)+\ldots+2^{h-2} * 2+2^{h-1} * 1 2∗T(n)=21∗(h−1)+22∗(h−2)+23∗(h−3)+24∗(h−4)+…+2h−2∗2+2h−1∗1

两式相减：

T ( n ) = 1 − h + 2 1 + 2 2 + 2 3 + 2 4 + … + 2 h − 2 + 2 h − 1 T(n)=1-h+2^1+2^2+2^3+2^4+\ldots+2^{h-2}+2^{h-1} T(n)=1−h+21+22+23+24+…+2h−2+2h−1

T ( n ) = 2 0 + 2 1 + 2 2 + 2 3 + 2 4 + … + 2 h − 2 + 2 h − 1 − h T(n)=2^0+2^1+2^2+2^3+2^4+\ldots+2^{h-2}+2^{h-1}-h T(n)=20+21+22+23+24+…+2h−2+2h−1−h

可以使用等比数列求和公式：

T ( n ) = 2 h − 1 − h T(n)=2^h-1-h T(n)=2h−1−h

由于 n = 2 h − 1 、 h = log ⁡ 2 ( n + 1 ) n=2^h-1、h=\log _2(n+1) n=2h−1、h=log2​(n+1)，则：

T ( n ) = n − log ⁡ 2 ( n + 1 ) T(n)=n-\log _2(n+1) T(n)=n−log2​(n+1)

故向下调整建堆时间复杂度为 T = O ( N ) T=O(N) T=O(N)

4.2.4 堆的插入

数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061556870.png

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1); // 向上调整
}

4.2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412061558692.png

//堆的删除
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置php->size--;//删除最后一个结点（也就是删除原来堆顶的元素）AdjustDown(php->a, php->size, 0);//向下调整
}

5. 树与二叉树练习题目

题目一：翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

struct TreeNode* invertTree(struct TreeNode* root) {if(root==NULL)return NULL;struct TreeNode *temp=root->left;root->left=root->right;root->right=temp;invertTree(root->left);invertTree(root->right);return root;
}//先递归再翻转也是可以的，道理是一样的
struct TreeNode* invertTree(struct TreeNode* root) {if(root==NULL)return NULL;struct TreeNode*left= invertTree(root->left);struct TreeNode*right= invertTree(root->right);root->left=right;root->right=left;return root;
}

题目二：判断二叉树是否相等

100. 相同的树 - 力扣（LeetCode）

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if (p == NULL && q == NULL) // 两个都为空则相同return true;else if (p == NULL || q == NULL)  //只有一个为空不相同return false;else if (p->val != q->val)  // 判断值是否相等return false;bool l = isSameTree(p->left, q->left);bool r = isSameTree(p->right, q->right);return l && r;
}

题目三：对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

该题目思路与判断二叉树相等几乎是一模一样，这里只不过变成了左子树的值是否等于右子树的值，两边同时递归下去即可。

bool isSymmetricHelper(struct TreeNode *l, struct TreeNode *r)
{if(l==NULL&&r==NULL)return true;else if(l==NULL||r==NULL)return false;else if(l->val!=r->val)return false;return isSymmetricHelper(l->left,r->right)&&isSymmetricHelper(l->right,r->left);}bool isSymmetric(struct TreeNode* root) {  // 仅仅使用此函数无法完成需要额外的函数来帮助if(root==NULL)return true;return isSymmetricHelper(root->left,root->right);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/35599.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

K8S快速部署

K8S快速部署

前置虚拟机环境正式部署BUG解决 前置虚拟机环境 每个虚拟机配置一次就好 #关闭防火墙 systemctl stop firewalld systemctl disable firewalld #关闭 selinux sed -i s/enforcing/disabled/ /etc/selinux/config # 永久 setenforce 0 # 临时 #关闭 swap swapoff -a # 临时 vi…
阅读更多...
Vue生命周期

Vue生命周期

一、Vue的生命周期及其阶段 Vue生命周期&#xff1a;一个Vue实例从 创建 到 销毁 的整个过程。也就是从开始创建、初始化数据、编译模板、挂载Dom→渲染、更新→渲染、卸载等一系列过程&#xff0c;我们称这是 Vue 的生命周期。 生命周期的四个阶段&#xff1a;① 创建 ② 挂…
阅读更多...
Android中的Wifi框架系列

Android中的Wifi框架系列

Android wifi框架图 Android WIFI系统引入了wpa_supplicant&#xff0c;它的整个WIFI系统以wpa_supplicant为核心来定义上层接口和下层驱动接口。 Android WIFI主要分为六大层&#xff0c;分别是WiFi Settings层&#xff0c;Wifi Framework层&#xff0c;Wifi JNI 层&#xff…
阅读更多...
Vue项目搜索引擎优化（SEO）终极指南：从原理到实战

Vue项目搜索引擎优化（SEO）终极指南：从原理到实战

文章目录 1. SEO基础与Vue项目的挑战1.1 为什么Vue项目需要特殊SEO处理&#xff1f;1.2 搜索引擎爬虫工作原理 2. 服务端渲染&#xff08;SSR&#xff09;解决方案2.1 Nuxt.js框架实战原理代码实现流程图 2.2 自定义SSR实现 3. 静态站点生成&#xff08;SSG&#xff09;技术3.1…
阅读更多...
嵌入式八股RTOS与Linux---前言篇

嵌入式八股RTOS与Linux---前言篇

前言 Linux与RTOS是校招八股的时候很喜欢考察的知识,在这里并没有把两个操作系统完全的独立开去讲,放在一起对比或许可能加深印象。我们讲Linux的内核有五部分组成:进程调度、内存管理、文件系统、网络接口、进程间通信,所以我也将从这五方面出发 中断管理去对比和RTOS的不同。…
阅读更多...
centos 8安装及相关操作

centos 8安装及相关操作

安装centos 8 在VMware workstation中安装 UEFI对比BIOS有更快的启动速度、支持更大容量硬盘及 GPT 分区、图形化操作界面更友好、安全性更高、对新操作系统支持更好、硬件兼容性不断增强以及扩展性更好等。 按回车确定 重置root管理员密码 这样进入到紧急救援模式 mount -o r…
阅读更多...
2025最新版Windows通过GoLand远程连接Linux构建Go项目保姆级教学

2025最新版Windows通过GoLand远程连接Linux构建Go项目保姆级教学

以Ubuntu24.04和GoLand2024.1.6为例子&#xff0c;演示如何在Windows上通过GoLand远程连接Linux进行Go编程。 通过go version指令可以发现当前Ubuntu系统没有安装go。 go version 通过指令安装go&#xff0c;其他系统可以通过wget安装&#xff0c;要指定安装的具体go版本&…
阅读更多...
多元时间序列预测的范式革命：从数据异质性到基准重构

多元时间序列预测的范式革命：从数据异质性到基准重构

本推文介绍了一篇来自中国科学院计算技术研究所等机构的论文《Exploring Progress in Multivariate Time Series Forecasting: Comprehensive Benchmarking and Heterogeneity Analysis》&#xff0c;发表在《IEEE Transactions on Intelligent Transportation Systems》。论文…
阅读更多...
开源PACS（dcm4che-arc-light）部署教程，源码方式

开源PACS（dcm4che-arc-light）部署教程，源码方式

目录 文件清单下载地址安装概述OpenLDAP、Apache Directory StudioWildflydcm4che 安装部署MySQL源码编译dcm4cheedcm4chee-arc-light OpenLDAP安装ApacheDirectoryStudio安装配置WildFly服务器 部署完成 文件清单 下载地址 Apache directory studio - linkOpenLDAP - linkdcm…
阅读更多...
PySide(PyQt)，使用types.MethodType动态定义事件

PySide(PyQt)，使用types.MethodType动态定义事件

以PySide(PyQt)的图片项为例&#xff0c;比如一个视窗的场景底图是一个QGraphicsPixmapItem&#xff0c;需要修改它的鼠标滚轮事件&#xff0c;以实现鼠标滚轮缩放显示的功能。为了达到这个目的&#xff0c;可以重新定义一个QGraphicsPixmapItem类&#xff0c;并重写它的wheelE…
阅读更多...
深度学习 Deep Learning 第1章 深度学习简介

深度学习 Deep Learning 第1章 深度学习简介

第1章 深度学习简介 概述 本章介绍人工智能&#xff08;AI&#xff09;和深度学习领域&#xff0c;讨论其历史发展、关键概念和应用。解释深度学习如何从早期的AI和机器学习方法演变而来&#xff0c;以及如何有效解决之前方法无法应对的挑战。 关键概念 1. 人工智能的演变 …
阅读更多...
简述下npm，cnpm，yarn和pnpm的区别，以及跟在后面的-g，--save, --save-dev代表着什么

简述下npm，cnpm，yarn和pnpm的区别，以及跟在后面的-g，--save, --save-dev代表着什么

文章目录 前言一、npm&#xff0c;cnpm&#xff0c;yarn和pnpm的基本介绍和特点1.npm (Node Package Manager)2. Yarn3. cnpm (China npm)4. pnpm 二、简述npm和pnpm 的存储方式和依赖数1.存储方式2.依赖树 三、两者依赖树的差异导致结果的对比四、简单说说-g&#xff0c;--sav…
阅读更多...
vue3系列：vite+vue3怎么配置通过ip和端口打开浏览器

vue3系列：vite+vue3怎么配置通过ip和端口打开浏览器

目录 1.前言 2.修改前的 3.修改后的 4.效果 5.其他 1.前言 想要使用IP端口号的方式访问页面&#xff0c;结果无法访问 查了些资料&#xff0c;原来是vite.config.js需要加一些配置才能让他通过IP访问&#xff0c;默认的只能localhost:端口号访问 2.修改前的 使用vue3默认…
阅读更多...
使用yolov8+flask实现精美登录界面+图片视频摄像头检测系统

使用yolov8+flask实现精美登录界面+图片视频摄像头检测系统

这个是使用flask实现好看登录界面和友好的检测界面实现yolov8推理和展示&#xff0c;代码仅仅有2个html文件和一个python文件&#xff0c;真正做到了用最简洁的代码实现复杂功能。 测试通过环境&#xff1a; windows x64 anaconda3python3.8 ultralytics8.3.81 flask1.1.2…
阅读更多...
突破连接边界！O9201PM Wi-Fi 6 + 蓝牙 5.4 模块重新定义笔记本无线体验

突破连接边界！O9201PM Wi-Fi 6 + 蓝牙 5.4 模块重新定义笔记本无线体验

在当今数字化时代&#xff0c;笔记本电脑已成为人们工作、学习和娱乐的必备工具。而无线连接技术&#xff0c;作为笔记本电脑与外界交互的关键桥梁&#xff0c;其性能的优劣直接关乎用户体验的好坏。当下&#xff0c;笔记本电脑无线连接领域存在诸多痛点&#xff0c;严重影响着…
阅读更多...
2025 香港 Web3 嘉年华：全球 Web3 生态的年度盛会

2025 香港 Web3 嘉年华：全球 Web3 生态的年度盛会

自 2023 年首届香港 Web3 嘉年华成功举办以来&#xff0c;这一盛会已成为全球 Web3 领域规模最大、影响力最深远的行业活动之一。2025 年 4 月 6 日至 9 日&#xff0c;第三届香港 Web3 嘉年华将在香港盛大举行。本届活动由万向区块链实验室与 HashKey Group 联合主办、W3ME 承…
阅读更多...
Windows11 新机开荒（二）电脑优化设置

Windows11 新机开荒（二）电脑优化设置

目录 前言&#xff1a; 一、注册微软账号绑定权益 二、此电脑 桌面图标 三、系统分盘及默认存储位置更改 3.1 系统分盘 3.2 默认存储位置更改 四、精简任务栏 总结&#xff1a; 前言&#xff1a; 本文承接上一篇 新机开荒&#xff08;一&#xff09; 上一篇文章地址&…
阅读更多...
[C++面试] 标准容器面试点

[C++面试] 标准容器面试点

一、入门 1、vector和list的区别 [C面试] vector 面试点总结 vector 是动态数组&#xff0c;它将元素存储在连续的内存空间中。支持随机访问&#xff0c;即可以通过下标快速访问任意位置的元素&#xff0c;时间复杂度为 O(1)&#xff0c;准确点是均摊O(1)。但在中间或开头插…
阅读更多...
蓝桥杯每日一题

蓝桥杯每日一题

丢失的雨伞 题目思路代码演示 题目 今天晚上本来想练习一下前缀和与差分 结果给我搜出来这题&#xff08;几乎没啥关系&#xff09;&#xff0c;我看半天有点思路但又下不了手哈哈&#xff0c;难受一批 在图书馆直接红温了 题目链接 思路 题目要求找到两个不重叠的区间&…
阅读更多...
校园安全用电怎么保障？防触电装置来帮您

校园安全用电怎么保障？防触电装置来帮您

引言 随着教育设施的不断升级和校园用电需求的日益增长&#xff0c;校园电力系统的安全性和可靠性成为了学校管理的重要课题。三相智能安全配电装置作为一种电力管理设备&#xff0c;其在校园中的应用不仅能够提高电力系统的安全性&#xff0c;还能有效保障师生的用电安全&am…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023