数据结构——树与二叉树-EW帮帮网

树与二叉树

1. 树的基本概念

1.1 树的定义

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

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

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

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

1.2 树的基本术语

结点的度*：*一个结点含有的子树的个数称为该结点的度；如上图：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 的路径

1.3 树的表示方法

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

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

2. 二叉树

2.1 二叉树的定义

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

几种特殊的二叉树：

满二叉树

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

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

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

2.2 二叉树的性质

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

$n_0=n_2+1$
性质2：非空二叉树的第 $k$ 层最多有 $2^{k-1}$ 个结点 $(k\geq 1)$
性质3：高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点 $(h\geq 1)$
性质4：
性质5：具有 $n$ 个结点的完全二叉树的深度为 $log_2(n+1)$ 或 $log_2n+1$

2.3 二叉树的存储结构

2.3.1 顺序存储

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

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

2.3.2 链式存储

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

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

2.4 二叉树的遍历

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

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

前序遍历结果：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/

递归版本：

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/

递归版本：

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/

递归版本：

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/

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 先序序列和中序序列

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

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

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://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。

构建根节点：

步骤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。

构建右子树的右子树：

步骤6

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

步骤7

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

构建右子树的左子树：

步骤8

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

步骤9

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

构建左子树：

最终构建的二叉树为：

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

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），也称二叉排序树或二叉查找树。

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

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

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

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

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

3.2 哈夫曼树

3.2.1 哈夫曼树的定义

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

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

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

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

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

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

$WPL=\sum_{i=1}^nw_il_i$

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

计算上图的WPL：

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

3.2.2 哈夫曼树的构造过程

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

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树/最优二叉树。

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

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

3.2.3 哈夫曼编码

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

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

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

这棵哈夫曼树的 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_i<=K_{2 * i+1}$ 且 $K_i<=K_{2 * i+2}\left(K_i>=K_{2 * i+1}\right.$ 且 $\left.K_i>=K_{2 * i+2}\right) \mathrm{i}=0,1,2$ 。则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆满足以下性质：

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

4.2 堆的实现

4.2.1 堆的向下调整

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

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)$ ，最坏走完整棵树。

4.2.2 堆的向上调整

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

//交换函数
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 堆的建立

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

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

时间复杂度分析：

结点移动的步数为：

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
$$

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

$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$

两式相减：

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

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

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

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

由于 $n=2^h-1、h=\log _2(n+1)$ ，则：

$T(n)=n-\log _2(n+1)$

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

4.2.4 堆的插入

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

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 堆的删除

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

//堆的删除
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);
}

数据结构——树与二叉树

树与二叉树

1. 树的基本概念

1.1 树的定义

1.2 树的基本术语

1.3 树的表示方法

2. 二叉树

2.1 二叉树的定义

2.2 二叉树的性质

2.3 二叉树的存储结构

2.3.1 顺序存储

2.3.2 链式存储

2.4 二叉树的遍历

2.4.1 前序遍历

2.4.2 中序遍历

2.4.3 后序遍历

2.4.4 层序遍历

2.5 遍历构造二叉树

2.5.1 先序序列和中序序列

2.5.2 中序序列和后序序列

2.6 二叉树的应用

2.6.1 二叉树结点个数

2.6.2 二叉树的高度

2.6.3 销毁二叉树

3. 树与二叉树的应用

3.1 二叉搜索树

3.2 哈夫曼树

3.2.1 哈夫曼树的定义

3.2.2 哈夫曼树的构造过程

3.2.3 哈夫曼编码

4. 堆

4.1 堆的定义

4.2 堆的实现

4.2.1 堆的向下调整

4.2.2 堆的向上调整

4.2.3 堆的建立

4.2.4 堆的插入

4.2.5 堆的删除

5. 树与二叉树练习题目

网站公告

今日签到

热门文章

最新发布