数据结构—二叉树

10.二叉树

  说完了树，接下来就该说说一些我们比较常用的树了，二叉树就是其中之一，它的基本结构如下：

struct TreeNode
{
   
    int val;
    TreeNode* left;
    TreeNode* right;
};

  很高兴，这次我们不用再存一个vector或者其他什么了，这样操作起来可要方便不少呢！

(1).二叉树的基本概念

  二叉树是由$n(n\ge 0)$个结点所构成的集合，这个集合或者为空；或者由一个根结点及表示根结点的左、右子树的两个互不相交的结点集合所组成，而根结点的左、右子树也都是二叉树

  二叉树是有序树，把第一个和第二个子结点（或子树）分别称为左子结点和右子结点（或子树），严格区分左右子树

(2).遍历

  因为二叉树的每个结点只有左、中、右三个方向，因此二叉树的遍历方式在树的基础上还包含了中序遍历，所以我们接下来给出三种遍历方式的代码

#1.前序遍历

  前序遍历的打印顺序是中、左、右

void PreOrderTraversal(const TreeNode* root)
{
   
    if (root) {
   
        cout << root->val << " ";
        PreOrderTraversal(root->left);
        PreOrderTraversal(root->right);
    }
}

#2.中序遍历

  前序遍历的打印顺序是左、中、右

void InOrderTraversal(const TreeNode* root)
{
   
    if (root) {
   
        InOrderTraversal(root->left);
        cout << root->val << " "; 
        InOrderTraversal(root->right);
    }
}

#3.后序遍历

  前序遍历的打印顺序是左、右、中

void PostOrderTraversal(const TreeNode* root)
{
   
    if (root) {
   
        PostOrderTraversal(root->left);
        PostOrderTraversal(root->right);
        cout << root->val << " "; 
    }
}

#4.非递归中序遍历

  非递归的中序遍历的流程是这样的：每个结点都往左子结点走，把自己压入栈中，一旦某个左子结点为空，就回溯到上一个根（即栈顶），然后再遍历根的右子树，这么一直重复就好了：

void NoRecursionInOrderTraversal(const TreeNode* root)
{
   
    if (!root) return;
    stack<const TreeNode*> s;
    const TreeNode* ptr{
    root };
    while (ptr || !s.empty()) {
   
        if (ptr) {
   
            s.push(ptr);
            ptr = ptr->left;
        }
        else {
   
            ptr = s.top();
            s.pop();
            cout << ptr->val << " ";
            ptr = ptr->right;
        }
    }
}

(3).中序+前/后序建树

  前序遍历+后序遍历的结果是不能建出一棵二叉树的，比如下面这个例子：

  T1和T2两棵树的前序遍历都是AB，后序遍历都是BA，因此我们靠前序+后序两种序列是没有办法还原一棵树的，但是如果是中序遍历呢？ 比如T1的中序遍历是BA，T2的中序遍历是AB，这样一来两棵树就可以被区别出来了，在这里我不给出证明了，我们需要的一点是，只要我们有中序遍历结果+前序或后序二选一的结果就可以还原出唯一的一棵二叉树了

  还有需要注意的点，根据根结点可以把中序遍历序列拆解成左子树和右子树两个部分，例如左子树有$k$个结点，而右子树有$n$个结点，则在前序遍历序列中，$1\sim k$ 的结点即为左子树的前序遍历结果，$k+1\sim k+n$ 的结点即为右子树的前序遍历结果，这个是比较自然的，比如我们在做前序遍历的时候，我们也是首先打印根结点，在把所有左子树结点打印出来之后，再打印出右子树结点，因此，这一点在之后对我们会非常有用

#1.中序+前序遍历建树

  我们先来思考一下，对于中序：FDHGIBEAC，前序：ABDFGHIEC，这样的结果，我们要怎么还原呢？首先先序遍历的第一个结点一定是根结点，所以取出A，前序变为BDFGHIEC，中序找到A后拆分成左子树FDHGIBE和右子树C
  然后递归地，我们再找到前序序列中的B，作为A左子树的根结点，再在左子树的中序遍历中找到B，拆分成B的左子树FDHGI和右子树E，然后就这么一直做下去，最后我们就可以得到一棵唯一的树：

  所以，我们只要每次根据索引和位置把序列切分成左子树和右子树对应的序列，再利用递归的方法分别完成左右子树的构建过程即可：

void buildTree(TreeNode*& root, const string& preorder, const string& inorder)
{
   
    if (inorder.size() == 0) {
   
        root = nullptr; // 切记当切分到0的时候，要将对应的结点设置为空指针
        return;
    }
    root = new TreeNode;
    int k{
    0 };
    while (preorder[0] != inorder[k]) k++;
    root = new TreeNode{
    inorder[k], nullptr, nullptr };
    buildTree(root->left, preorder.substr(1, k), inorder.substr(0, k));
    buildTree(root->right, preorder.substr(k+1, preorder.size() - 1 - k), inorder.substr(k+1, inorder.size() - 1 - k));
}

  这里采取了字符串来传入前序和中序遍历序列，因为这里可以采取substr方法，可以比较简单地完成整个流程，当然，我们用迭代器的方法就可以用vector来完成的，在中序+后序遍历中我会给出vector的方法

#2.中序+后序遍历建树

  中序+后序遍历的方法其实和前序一样，只是这一次我们每次都从后序遍历的最后一个结点中取出来，作为根结点，所以代码也很容易写出来：

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
   
    if (postorder.size() == 0) return nullptr;
    int val{
    postorder[postorder.size() - 1] };
    TreeNode* root = new TreeNode{
    val, nullptr, nullptr };
    if (postorder.size() == 1) return root;

    int k{
    0 };
    while (inorder[k] != val) k++;
    vector<int> leftInorder{
    inorder.begin(), inorder.begin() + k };
    vector<int> rightInorder{
    inorder.begin() + k + 1, inorder.end() };
    postorder.resize(postorder.size() - 1); // 去掉最后一个元素，比较方便后续直接使用.end()获取最后一个元素

    vector<int> leftPostorder{
    postorder.begin(), postorder.begin() + leftInorder.size() };
    vector<int> rightPostorder{
    postorder.begin() + leftInorder.size(), postorder.end() };
    root->left = buildTree(leftInorder, leftPostorder);
    root->right = buildTree(rightInorder, rightPostorder);
    return root;
}

  其实本质是一样的，我们还是对整个序列进行了一系列的分割，然后再完成后续的建树过程

(4).递归和二叉树基本操作

  和前文中提过的多叉树一样，二叉树的定义同样是递归的，因此我们仍然可以利用递归的方法完成二叉树的各种操作

#1.求树高

  树的高度定义为所有结点的深度的最大值，我们前面认为：树根的高度为0，空树高度为-1，所以求最大值我们可以写出下面的递归式： h e i g h t = m a x { l e f t _ h e i g h t , r i g h t _ h e i g h t } + 1 height = max\{left\_height, right\_height\} + 1 height=max{ left_height,right_height}+1  所以，代码也是很好写的咯，让我们来试试吧：

int max(int a, int b)
{
   
    return (a > b) ? a : b;
}

int tree_height(const TreeNode* root)
{
   
    if (!root) return -1;
    if ((!root->left) && (!root->right)) return 0;
    int hL{
    tree_height(root->left) };
    int rL{
    tree_height(root->right) };
    return max(hL, rL) + 1;
}

#2.求结点数

  求结点数也很简单，我们只需要：$$cnt=left\_cnt+right\_cnt+1$$

int count(const TreeNode* root)
{
   
    if (!root) return 0;
    return count(root->left) + count(root->right) + 1;
}

#3.求叶子结点数

  叶子结点数也是一样，我们需要左子树的叶子结点数+右子树的叶子结点树的值即可:$$leaves=left\_leaves+right\_leaves$$

int leaves(const TreeNode* root)
{
   
    if ((!root->left) && (!root->right)) return 1;
    return leaves(root->left) + leaves(root->right);
}

#4.复制树

  复制树就是把一棵树完整地复制另外一棵出来，那么其实也就是说，遇到某个结点，把左子树复制一次，再把右子树复制一次，就好了

TreeNode* BiTreeCopy(const TreeNode* root)
{
   
    if (!root) return nullptr;
    TreeNode* p{
    new TreeNode{
   root->val, nullptr, nullptr} };
    p->left = BiTreeCopy(root->left);
    p->right = BiTreeCopy(root->right);
    return p;
}

#5.判断两棵树是否相等

  一样的套路，左子树相等 + 本身相等 + 右子树相等

bool equal(const TreeNode* t1, const TreeNode* t2)
{
   
    if (!t1 && !t2) return true;
    if (t1 && t2) {
   
        return (t1->val == t2->val) && equal(t1->left, t2->left) && equal(t1->right, t2->right);
    }
    return false;
}

(5).特殊二叉树

#1.满二叉树

  满二叉树中，每一层结点数目都达到了最大，比如下面这种：

  比如这样，高度为k的满二叉树有$2^{k+1}-1$个结点，在这里我采取根结点编号为1的策略，有些地方可能采取根结点编号为0的策略，但是这种情况下子结点不是很好找，我们把所有结点依据从左到右，从上到下按照层序依次编号的方式给每个结点分配一个编号:

  为啥要考虑这个呢？因为我们会发现，根结点1的两个左右结点分别是2和3，而2的两个结点是4和5，所以说，对于任意一个非叶结点编号为$k$的结点，它的两个子结点必存在，并且编号为$2k和2k+1$，所以满二叉树可以在完全不浪费空间的情况下，使用数组完成存储，并且其编号的关系可以在不开出额外空间的情况下很轻松地存储结点的双亲结点和子结点的位置。

#2.完全二叉树

  完全二叉树则是在满二叉树的基础上去除最后一层从最后一个结点开始的连续若干个结点，比如

  所以满二叉树也算完全二叉树，对于具有$n(n>0)$个结点的完全二叉树，其深度为$\lfloor {\log }_{2}n\rfloor$

(6).堆

#1.基本思想

  堆基于完全二叉树来实现，堆定义为：如果树T中任一结点的值不小于(不大于)其左右结点的值，则树T为一个堆，如果根结点是所有结点中的最大值，则这个堆称为大根堆；否则如果是最小值，则这个堆称为小根堆

  这么做的思想其实很简单，堆排序维护了一个基本有序的序列，再每次插入/删除之后，都能以$O(\log n)$的时间复杂度代价上完成下一次维护，因此，堆排序的时间复杂度是$O(n\log n)$

#2.堆的基本操作

  堆的基本操作主要是上浮和下沉两个流程，上浮就是把结点放在最后的叶结点的位置，然后把它逐渐上浮到合适的位置即可，而下沉则是把新加入的结点放在根结点上，其左右子树都是堆，但是根结点本身不满足堆的性质，所以我们逐渐操作，把根结点下沉，沉到符合条件的位置

i.上浮

void swap(int& a, int& b)
{
   
    int tmp{
   a};
    a = b;
    b = tmp;
}

void siftup(vector<int>& a, int k)
{
   
    bool check{
    false };
    while (k > 1 && !check) {
   
        if (a[k] > a[k/2]) {
   
            swap(a[k/2], a[k]);
            k /= 2;
        }
        else check = true;
    }
}

ii.下沉

  下沉的流程要稍微复杂一点，结点会首先和它的左右两个子结点进行比较（先左后右），直到有序/找到最后一个结点才停下来：

void siftdown(vector<int>& a, int i)
{
   
    int n = a.size() - 1;
    bool check{
    false };
    int t{
    0 };
    while (i*2 <= n && !check) {
   
        if (a[i] < a[i*2]) t = i*2;
        else t = i;

        if (i*2+1 <= n) {
   
            if (a[t] < a[i*2+1]) t = i*2+1;
        }

        if (t != i) {
   
            swap(a[i], a[t]);
            i = t;
        }
        else check = true;
    } 
}

iii.建堆

void buildHeap(vector<int>& a)
{
   
    int n = a.size() - 1;
    for (int i = n / 2; i >= 1; i--) {
   
        siftdown(a, i);
    }
}

iv.插入元素

void addElement(vector<int>& a, int num)
{
   
    a.push_back(num);
    siftup(a, a.size()-1);
}

v.删除元素

int deleteRoot(vector<int>& a)
{
   
    int tmp{
    a[1] };
    a[1] = a[a.size()-1];
    a.pop_back();
    siftdown(a, 1);
    return tmp;
}

#3.堆排序

  所以，我们只需要每一次都从堆的根上拿出一个元素即可，堆排序的流程非常简单：

void heap_sort(vector<int>& a)
{
   
    vector<int> ans;
    while (a.size() > 1) {
   
        int val{
    deleteRoot(a) };
        ans.push_back(val);
    }
    a = ans;
}

  流程比较简单，但是上面的代码并不能保证没有bug，堆的这一部分思路比较简单，因此我只提供一个思路

小结

  这一篇我们比较粗略地介绍了一下二叉树相关的内容，其实应该还有一个二叉搜索树的，但是鉴于它的复杂度，我决定把它放到下一篇：树的应用中再来介绍