二叉树的详解与实现「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

简介

• 二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述。

二叉树分类

1、完全二叉树

• 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
• 一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。
  

2、满二叉树

• 国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树
  
• 国内的定义是：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。很显然，按照这个定义，上面的图示二叉树就不是满二叉树。

3、扩充二叉树

• 扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的节点都变为度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶子节点则增加两个分支。
  

4、平衡二叉树

• 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1
  

二叉树的应用场景

• 普通的二叉树，很难构成现实的应用场景，但因其简单，常用于学习研究，平衡二叉树则是实际应用比较多的。常见于快速匹配、搜索等方面。
• 常用的树有：AVL树、红黑树、B+树、Trie（字典）树。
  1、AVL树: 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
  2、红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。
  3、B/B+树: 用在磁盘文件组织 数据索引和数据库索引。
  4、Trie树(字典树): 用在统计和排序大量字符串，如自动机、M数据库索引。

二叉树的构建

0、遍历方式

• 前序遍历：root -> left -> right
• 中序遍历：left -> root -> right
• 后续遍历：left ->right -> root
• 层序遍历：按照层次遍历
  
• 比如中序遍历，过程如下：
  
• 以下实现二叉树的所有实现，包括：三种遍历方法、查询树深度叶子数等。但是要通过遍历结果确定一个树，需要中序遍历配合另外的其中一种遍历方式才行。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

struct BTreeNode{
    int data = 0;
    BTreeNode *left;
    BTreeNode *right;
};
class BTree{
public:
    BTree(){
    }
    //传参需要注意，二叉树是指针类型的，节点本身就是一个指针：*node。所以需要二级指针才能改变二叉树的内容
    void create(BTreeNode* &Node){
        int data;
        cin >> data;
        if(data){
            Node = new BTreeNode;
            Node->data = data;
            //cout<<"data:"<<data<<endl;
            create(Node->left);
            create(Node->right);
        } else{
            Node=NULL;
        }
    }
    //按层创建二叉树
    void levelCreate(BTreeNode* &Node){
        queue <BTreeNode*> que;
        int data;
        cin>>data;
        if(data){
            Node = new BTreeNode;
            Node->data = data;
            que.push(Node);
        } else{
            Node = NULL;
            return;
        }
        while(!que.empty()){
            BTreeNode *node = que.front();
            que.pop();
            //输入左边数据
            cin>>data;
            if(data){
                node->left = new BTreeNode;
                node->left->data = data;
                que.push(node->left);
            } else{
                node->left = NULL;
            }
            //输入右边数据
            cin >>data;
            if(data){
                node->right = new BTreeNode;
                node->right->data = data;
                que.push(node->right);
            } else{
                node->right = NULL;
            }
        }
    }
    //1 2 3 4 5 6 0 0 0 7 8 0 9 0 0 0 0 0 0
    void clear(BTreeNode*& Node){
        BTreeNode *p = Node;
        if(p != NULL){
            clear(Node->left);
            clear(Node->right);
            delete p;
        }
    }
    //前序遍历(根左右)
    void preorderTree(BTreeNode* Node){
        if(Node!=NULL){
            cout<<Node->data<<" ,";
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }
    //前序遍历非递归写法
    void NnredursionPreorder(BTreeNode* Node){
        stack<BTreeNode*> node;
        node.push(Node);
        BTreeNode *pNode = Node;
        while(pNode != NULL || !node.empty()){
            //1、先把节点打印，并且入栈，将节点的左孩子作为当前的节点
            //2、当节点不为空或者栈不为空，就取出栈顶，
            if(pNode != NULL){

                cout<<pNode->data<<" ";
                node.push(pNode);
                pNode = pNode->left;
            } else{
                BTreeNode *treeNode = node.top();
                node.pop();
                pNode = pNode->right;

            }
        }
    }

    //中序遍历(左中右)
    void inorderTree(BTreeNode* Node){
        if(Node != NULL){
            inorderTree(Node->left);
            cout<<Node->data<<" ,";
            inorderTree(Node->right);
        }
    }

    //后序遍历（左右中）
    void postorderTree(BTreeNode* Node){
        if(Node != NULL){
            postorderTree(Node->left);
            postorderTree(Node->right);
            cout<<Node->data<<" ,";
        }
    }
    //层序遍历
    void levelTree(BTreeNode *Node){
        queue<BTreeNode*> que;
        if(Node == NULL) return;
        else{
            que.push(Node);
            while(!que.empty()){
                BTreeNode *node = que.front();
                cout<<node->data<<" ";
                que.pop();
                if(node->left != NULL){
                    que.push(node->left);
                }
                if(node->right!=NULL){
                    que.push(node->right);
                }
            }
        }
    }
    //二叉树深度
    int depthOfTree(BTreeNode* Node){
        if(Node){
            return max(depthOfTree(Node->left),depthOfTree(Node->right))+1;
        } else{
            return 0;
        }
    }
    //返回节点总数目
    int getNodeNum(BTreeNode* Node){
        if(Node){
            return 1+getNodeNum(Node->left)+getNodeNum(Node->right);
        } else{
            return 0;
        }
    }
    //返回叶子节点
    int getLeafNum(BTreeNode* Node){
        if(!Node){
            return 0;
        } else if(Node->left == NULL && Node->right == NULL){
            return 1;
        } else{
            return getLeafNum(Node->left)+getLeafNum(Node->right);
        }
    }
};
int main(){
    BTree tree;
    BTreeNode *root;
    //tree.create(root);
    tree.levelCreate(root);
    cout<<"pre :";
    tree.preorderTree(root);
    cout<<endl;
    cout<<"in  :";
    tree.inorderTree(root);
    cout<<endl;
    cout<<"post:";
    tree.postorderTree(root);
    cout<<endl;
    cout<<"level:";
    tree.levelTree(root);
    cout<<endl;
    cout<<"NodeNum:"<<tree.getNodeNum(root)<<",depth:"<<tree.depthOfTree(root)<<",leaf:"<<tree.getLeafNum(root)<<endl;


    tree.clear(root);
    return 0;
}

二叉树重建

参考链接

• 二叉树的重建，只能在提供前序+中序，或者后序+中序的情况下，才可以正常的重构。
• 前序+中序：
  1、前序遍历数组中的第一个数就是根节点，得到根节点的数字。
  2、然后在中序遍历中找到该根节点的位置，中序数组的左边就是该根节点的左子树，中序遍历的右边序列是其右子树。
  3、前序遍历中根据中序遍历中根节点的位置，将前序遍历分为前序遍历的左子树和右子树。
  4、根节点就确定了，最后将前序和中序划分出来的左右子树，分别带入递归得到左右子树的构建情况。
  
• 后序+中序
  1.后续遍历的最后一个节点是根节点，然后中序遍历中找出根节点位置mid。
  2.再在根据中序遍历中的mid位置将后序遍历数组和中序遍历数据分为左子树和右子树。
  3.最后将划分完成的左右子树递归。
  

public class RebuildBinaryTree {
    //假设输入的前序遍历和中序遍历的结果中都不含重复的数字
    /*
      前序遍历第一位是根节点；
      中序遍历中，根节点左边的是根节点的左子树，右边是根节点的右子树。
      例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
      首先，根节点 是{ 1 }；
      左子树是：前序{ 2,4,7 } ，中序{ 4,7,2 }；
      右子树是：前序{ 3,5,6,8 } ，中序{ 5,3,8,6 }；
      这时，如果我们把左子树和右子树分别作为新的二叉树，则可以求出其根节点，左子树和右子树。
     */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre==null||in==null){
            return null;
        }
        TreeNode treeNode=reConstructBinaryTree(pre, in,0,pre.length-1,0,in.length-1);
        return treeNode;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in,int preStart,int preEnd,int inStart,int inEnd) {
         TreeNode tree=new TreeNode(pre[preStart]);  //前序遍历的第一个是根节点,递归时把左子树和右子树分别作为新的二叉树
         tree.left=null;
         tree.right=null;
         if(preStart==preEnd&&inStart==inEnd){   //说明已经是树叶节点
             return tree;
         }
         int root;
         for(root=inStart;root<inEnd;root++){       //寻找根节点在中序遍历中的下标
             if(pre[preStart]==in[root]){
                 break;
             }
         }
         int leftLength=root-inStart;       //左子树的长度
         int rightLength=inEnd-root;        //右子树的长度
         //把左子树和右子树分别作为新的二叉树，则可以求出其根节点，左子树和右子树。
         if(leftLength>0){
             tree.left=reConstructBinaryTree(pre,in,preStart+1,preStart+leftLength,inStart,root-1);
         }
         if(rightLength>0){
             tree.right=reConstructBinaryTree(pre,in,preStart+1+leftLength,preEnd,root+1,inEnd);
         }
         return  tree;
    }
}

二叉排序树

• 二叉排序树，又称二叉查找树、二叉搜索树。
  性质如下：
• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树。

    //建立二叉搜索树,左小右大
    bool insertBST(BTreeNode* &Node,int element){
        int data;
        data  =element;
        if(Node){
            if(element == Node->data){
                return false;
            } else{
                //与Node的数据比较
                if(element >Node->data){
                    return insertBST(Node->left,element);
                } else{
                    return insertBST(Node->right,element);
                }
            }
        } else{
            Node = new BTreeNode;
            Node->data = data;
            return true;
        }
    }
    //二叉搜索树查找
    BTreeNode* BSTSearch(BTreeNode *Node,int data){
        if(Node == NULL || Node->data == data){
            return Node;
        } else{
            if(data > Node->data){
                BSTSearch(Node->right,data);
            } else{
                BSTSearch(Node->left,data);
            }
        }
    }
    //二叉搜索树删除元素
    bool deleteBST(BTreeNode* &Node,int data){
        if(!Node){
            return false;
        }
        if(data == Node->data){
            //找到元素，删除元素，找到子树替换当前位置
            deleteBSTNode(Node);
            return true;
        } else if(data > Node->data){
            //元素在右子树
            deleteBST(Node->right,data);
        } else{
            //元素在左子树
            deleteBST(Node->left,data);
        }
    }
     void deleteBSTNode(BTreeNode*& Node){
        BTreeNode *node = Node;
        //若有左子树，找左子树中最大的，或者右子树中最小的，替换当前节点
        if(Node->left){
            BTreeNode *left = Node->left;
            //左子树的最右边子树的父节点
            BTreeNode *Preer = Node->left;
            while(left->right){
                Preer = left;
                left = left->right;
            }
            if(Preer != left){
                //删除pererd的右叶子
                left->left =Node->left;
                Preer->right = NULL;
            }
            Node = left;
        } else{
            Node = Node->right;
        }
        delete node;
    }

红黑树

• **红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。**这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。
• 从根节点到叶节点的路径上黑色节点的个数，叫做树的黑色高度。
  每个节点要么是红色，要么是黑色；
  根节点永远是黑色的；
  所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
  每个红色节点的两个子节点一定都是黑色；
  从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
• 各种操作的时间复杂度，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）
• 相对于BST和AVL树，红黑树是牺牲了严格的高度平衡的优越条件为代价，能够以O(log2n)的时间复杂度进行搜索、插入、删除操作。最坏情况下，查找（O(lgn)）比二叉排序树快O(n)。较于AVL树，红黑树在数据较乱时查找要更快。
• 与哈希表对比，哈希的内存需求更大，map查找log(n)级别。当数据是静态的时候使用哈希，数据需要动态维护则使用红黑树比较好。比如Linux内核系统使用红黑树维护内存块。

红黑树的旋转

• 左旋：把右子树里的一个节点移动到了左子树。
• 右旋：把左子树里的一个节点移动到了右子树。

线段树

视频参考

• 线段树的提出是为了以log(n)复杂度快速的求出数组中所有树的和所提出的。

• 1.线段树的每个节点代表着一个区间

• 2.线段树具有唯一的根节点，统计的范围为：[1,N]

• 3.对于每个内部节点[l,r]。左子节点是[l,mid]，右边子节点是[mid+1,r]，mid = (l+r)/2（向下取整）
  

• 建树的代码如下：

#include<bits/stdc++.h>
using namespace std; 

const int N = 1000;

int a[] = {1, 3, 5, 7, 9, 11};
int size = 6;
int tree[N] = {0};

//建立范围为a[start]~a[end] 
void build(int a[], int tree[], int node/*当前节点*/, int start, int end){
    //递归边界(即遇到叶子节点时) 
    if (start == end) {
        //直接存储a数组中的值 
        tree[node] = a[start];
    } 

    else {
        //将建立的区间分成两半 
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;//左子节点的下标 
        int right = 2 * node + 2;//右子节点的下标 

        //求出左子节点的值(即从节点left开始,建立范围为a[start]~a[mid])
        build(a, tree, left,  start, mid);
        //求出右子节点的值(即从节点right开始,建立范围为a[start]~a[mid])
        build(a, tree, right, mid+1, end);

        //当前节点的职位左子节点的值加上右子节点的值 
        tree[node] = tree[left] + tree[right];
    }
}

void update(int a[], int tree[], int node, int start, int end, int x, int val){
    //找到a[x],修改值 
    if (start == end){
        a[x] = val;
        tree[node] = val;
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        if (x >= start && x <= mid) {//如果x在左分支 
            update(a, tree, left, start, mid, x, val);
        }
        else {//如果x在右分支 
            update(a, tree, right, mid+1, end, x, val);
        }

        //向上更新值 
        tree[node] = tree[left] + tree[right]; 
    } 
}

//求a[L]~a[R]的区间和 
int query(int a[], int tree[], int node, int start, int end, int L,int R){
    //若目标区间与当时区间没有重叠,结束递归返回0 
    if (start > R || end < L){
        return 0;
    }

    //若目标区间包含当时区间,直接返回节点值 
    else if (L <=start && end <= R){
        return tree[node];
    }

    else {
        int mid = (start + end) / 2;

        int left  = 2 * node + 1;
        int right = 2 * node + 2;

        //计算左边区间的值 
        int sum_left  = query(a, tree, left,  start, mid, L, R);
        //计算右边区间的值 
        int sum_right = query(a, tree, right, mid+1, end, L, R);

        //相加即为答案 
        return sum_left + sum_right;
    } 
}

int main(){
    //从根节点(即节点0)开始建树,建树范围为a[0]~a[size-1]
    build(a, tree, 0, 0, size-1);

    for(int i = 0; i <= 14; i ++)
        printf("tree[%d] = %d\n", i, tree[i]);
    printf("\n");    

    //把a[x]改成6
    update(a, tree, 0, 0, size-1, 4, 6); 

    for(int i = 0; i <= 14; i ++)
        printf("tree[%d] = %d\n", i, tree[i]);
    printf("\n");

    //求区间[2,5]的和
    int ans = query(a, tree, 0, 0, size-1, 2, 5);
    printf("ans = %d", ans); 

    return 0;
}

树类搜索算法

参考链接

• 一般来说就是深度优先搜索,广度优先搜索,A搜索,IDA搜索等几种，通常用的最多就是DFS和BFS。

DFS简述

• 适用于树型查找。
• 找到当前可以拓展的点，就走此分支。
• 如果当前分支无效或者找到了目标，就退回到上一步，称之为回溯。
• 每个节点最多访问两次，一次入栈，一次出栈。

BFS简述

• 使用于图型结构的搜索，通过队列层层向外拓展。
• 找到可以拓展的点，将其放入队列中。
• 每次选取队列的对头，作为当前状态。