二叉树（C/C++）

二叉树的种类

 二叉树的种类网上介绍的很多，这里简单用几张图描述一下。
注意：二叉树每个结点最多只有两棵子树，这意味着任意结点的度小于等于2。子树有左右之分；某个结点只有一个孩子时，它位于左边和右边组成的是不同的树。

满二叉树

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

完全二叉树

1.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

2. 某结点的度如果为1，则它只有左孩子
   3.叶子结点只能出现在最后两层（考虑树2）
   4.相同结点的树中，完全二叉树的深度最小
   

斜数（特殊的链表）

如果一棵二叉树只有左孩子，则称该树为左斜树，类似的如果只有右孩子，就称为右斜树，他们统称为斜树。这时候树就演化成了链表。树的深度就是树的结点个数。

二叉搜索树

二叉搜索树是一个有序树。
·若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
·若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
·它的左、右子树也分别为二叉排序树

平衡二叉搜索树

左右两个子树的高度差不超过1的二叉搜索树。
之前的map的底层实现就是平衡二叉搜索树，但是unordered_map的底层实现是用哈希表，所以map的时间复杂度是logn，而unordred_map不是，unordered_map时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)

存储方式

链式存储

数组存储

父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。（一般使用链表，这个看看就好了）

怎么建立一个二叉树

先看一下怎么定义一个二叉树

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

递归

struct TreeNode* CreateTree(vector<int>num, int n, int start)  
{  
    if (num[start] == 0)  
    {  
        return NULL;  
    }  
    // 根  
    TreeNode *root = new TreeNode;    
    root->val = num[start];  
    root->left = NULL;  
    root->right = NULL;  
    // 左子树  
    int lnode = 2 * start + 1;  
    int rnode = 2 * start + 2;  
    if (lnode > n - 1)  
    {  
        root->left = NULL;  
    }  
    else  
    { 
        root->left = CreateTree(num, n, lnode);  
    }   
    if (rnode > n - 1)  
    {  
        root->right = NULL;  
    }  
    else  
    {  
        root->right = CreateTree(num, n, rnode);  
    }  
    return root;  
}  

二叉树的遍历方式

1.深度优先遍历：先往深走，遇到叶子节点再往回走。
2.广度优先遍历：一层一层的去遍历。
·深度优先遍历
先序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
·广度优先遍历
层次遍历（迭代法）
这里前中后序遍历，其实指的就是中间节点的遍历顺序。
先序遍历：中左右
中序遍历：左中右
后序遍历：左右中

递归求解先中后序遍历

1.先序

void tree(TreeNode* root, vector<int>& vec)   
{  
    if (root== NULL) return;
    vec.push_back(cur->val);    // 中  
    tree(root->left, vec);  // 左  
    tree(root->right, vec); // 右 
}   

2. 中序

void tree(TreeNode* root, vector<int>& vec)     
{    
    if (root== NULL) return;  
    tree(root->left, vec);  // 左  
    vec.push_back(root->val);    // 中  
    tree(root->right, vec); // 右  
}     

3.后序

void tree(TreeNode* root, vector<int>& vec)   
{  
    if (root== NULL) return;
    tree(root->left, vec);  // 左
    tree(root->right, vec); // 右
    vec.push_back(root->val);    // 中
}   

迭代法求二叉树

这里需要用到栈，还不清楚的可以看一下我的另一篇浅谈栈与队列。

vector<int> pre(TreeNode* root)  
 {  
    stack<TreeNode*> qwe;  
    vector<int> result;  
    qwe.push(root);   
    while (!qwe.empty())   
{      
        TreeNode* node = qwe.top();                        // 中     
        qwe.pop();    
        if (node != NULL) result.push_back(node->val);  
        else 
            continue;  
        qwe.push(node->right);                           // 右  
        qwe.push(node->left);                            // 左   
    }  
    return result; 
}  

层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {  
        queue<TreeNode*> que;  
        if (root != NULL) que.push(root);  
        vector<vector<int>> result;  
        while (!que.empty()) {  
            int size = que.size();  
            vector<int> vec;  
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的  
            for (int i = 0; i < size; i++) {  
                TreeNode* node = que.front();  
                que.pop();  
                vec.push_back(node->val);   
                if (node->left) que.push(node->left);  
                if (node->right) que.push(node->right);   
            }  
            result.push_back(vec);  
        }  
        return result;  
    }  

文章参考：https://mp.weixin.qq.com/s/c_zCrGHIVlBjUH_hJtghCg