打败 二叉树！

树的概念与结构

树是一种非线性的数据结构，它是由n（n≥0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
● 有一个特殊的结点，称为根结点，根节点没有前驱结点，但有0个或多个后继
● 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。

节点的度：一个节点含有的子树的个数称为该节点的度；
叶节点或终端节点：度为0的节点称为叶节点；
非终端节点或分支节点：度不为0的节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；
树的度：一棵树中，最大的节点的度称为树的度；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：双亲在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>0）棵互不相交的树的集合称为森林；

实际应用如：Linux树状目录结构
 
 
 

二叉树

 

概念与结构

二叉树(Binary Tree)是n(n≥0)个结点所构成的集合，它或为空树(n= 0); 或为非空树，
对于非空树T: (1) 有且仅有一个称之为根的结点； (2) 除根结点以外的其余结点分为两个互不相交的子集T1和T2, 分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

1. 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大与2 的结点）；
2. 二叉树的子树有左右之分，其次序不能任意颠倒。（有序树）

二叉树5种基本形态

 

特殊二叉树

1. 满二叉树：
   深度为 K 且节点总共 2^K-1 个的二叉树，即每一个层的结点数都是满的（都达到最大值），则这个二叉树就是满二叉树。
   每层节点个数为 2^K-1

2. 完全二叉树：
   深度为 K 且节点数为 n的二叉树, 当且仅当其每一个结点都与深度为 K 的满二叉树中编号从1~n的结点位置序号一一对应时为完全二叉树。
   满二叉树是一种特殊的完全二叉树。
   (树高为 h ，前 h-1 层都存满，第 h 层从左->右一次存储)

节点总数是奇数：没有度为 1 的节点 为偶数： 度为 1 的节点有且只有一个

 
 

性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2^(i-1)个结点.

2. 若规定根节点的层数为1，则深度为 h 的二叉树的最大结点数是 2^h-1（满二叉树）

3. 对任何一棵二叉树, 如果度为 0 叶结点个数为 N0, 度为2的分支结点个数为 N2,则有 N0 ＝ N2＋1
   

4. 若规定根节点的层数为1，具有n个结点的完全二叉树的深度，h = log2(n+1)(ps： 是log以2为底，n+1为对数)
   

5. 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：

1.若 i > 0，i 位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2.若2i+1<n，左孩子序号：2i+1，2i+1 ≥ n否则无左孩子
3.若2i+2<n，右孩子序号：2i+2，2i+2 ≥ n否则无右孩子
 

 
 

存储结构

1. 顺序结构：二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

顺序结构存储就是使用数组来存储，内存是连续分布的，（一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。）而现实中使用中只有堆才会使用数组来存储，关于堆详见下篇

2. 链式结构：二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

链式存储则是通过指针把分布在散落在各个地址的节点串联一起 通常的方法是链表中每个结点由三个域组成，数据域 和 左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链，大部分是二叉链，如红黑树等会用到三叉链。

 
 

二叉树的遍历

（这两种遍历是图论中最基本的两种遍历方式）

深度优先遍历：先往深走，遇到叶子节点再往回走。
● 前序遍历（递归法，迭代法）根左右
● 中序遍历（递归法，迭代法）左根右
● 后序遍历（递归法，迭代法）左右根

广度优先遍历：一层一层的去遍历。
● 层次遍历（迭代法）

二叉树的定义

// C （二叉链）
struct TreeNode {
    
     int val;
     struct TreeNode *left;   // 结构体指针
     struct TreeNode *right;
};
—————————————————————————————————————————————————————————————————————————
// cpp
struct TreeNode {
    
      int val;
      TreeNode *left;
      TreeNode *right;
      // 三种重载的构造
      TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
 };

 

前序遍历

144. 二叉树的前序遍历
也叫先序遍历，访问顺序为 根节点 -> 先序遍历左子树 -> 先序遍历右子树

    // 前序遍历递归实现
	void preOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root) return ;   //递归出口
        res.push_back(root->val);   // 保存根值
        preOrder(root->left, res);   // 遍历左子树
        preOrder(root->right, res);  // 遍历右子树
    }  
      
    vector<int> Traversal(TreeNode* root) {
    
        vector<int> res;
        preOrder(root, res);
        // inOrder(root, res);
        // postOrder(root, res);
        return res;
    }

前序遍历是根左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。这样出栈的时候才是根左右的顺序。

  // 迭代
    //那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子
    vector<int> preorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> s;
        vector<int> res;
        if(nullptr == root) return res;
        s.push(root);
        while(!s.empty()){
    
            TreeNode* node = s.top();    // 根节点
            s.pop();  
            res.push_back(node->val);  
            if(node->right != nullptr)
                s.push(node->right);   // 右孩子入栈
            if(node->left != nullptr)
                s.push(node->left);    // 左孩子入栈
        }
        return res;
    }

 

中序遍历

94. 二叉树的中序遍历
访问顺序为 中序遍历左子树 -> 根节点 -> 中序遍历右子树

// 中序遍历递归实现
    void inOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root) 
            return ;   //递归出口 
        inOrder(root->left, res);   // 遍历左子树
        res.push_back(root->val);   // 保存根值
        inOrder(root->right, res);  // 遍历右子树
    }

先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进res数组中）

使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

   // 迭代
   vector<int> inorderTraversal(TreeNode* root) {
    
        stack<TreeNode*> s;
        vector<int> res;
        TreeNode* cur = root;
        while(cur != nullptr || !s.empty()){
    
            if(cur != nullptr){
       // 访问到最底层
                s.push(cur);
                cur = cur->left;
            }else{
    
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }

        return res;
    }

 

后序遍历

145. 二叉树的后序遍历
访问顺序为 后序遍历左子树 -> 后序遍历右子树 -> 根节点

// 后序遍历递归实现
    void postOrder(TreeNode* root, vector<int>& res){
    
        if(nullptr == root)
            return ;
        postOrder(root->left, res);
        postOrder(root->right, res);
        res.push_back(root->val);
    }

后序遍历只需要前序遍历的代码稍作修改就可以了

  // 迭代
   vector<int> postorderTraversal(TreeNode* root) {
    
        vector<int> res;
        stack<TreeNode*> s;
        if(nullptr == root) return res;
        s.push(root);
        while(!s.empty()){
    
            TreeNode* node = s.top();
            s.pop();
            res.push_back(node->val);
            // 相对于前序遍历，这更改一下入栈顺序
            if(node->left != nullptr) s.push(node->left);
            if(node->right != nullptr) s.push(node->right);
            
        }
        reverse(res.begin(), res.end()); // 将结果反转之后就是后序的顺序了
        return res;
    }

---

C语言递归实现三种遍历代码
 

层序遍历

层序遍历需要借助队列
先将根节点入队列然后:如果队列不为空，循环进行以下操作:
1.从队列中取 1 个节点
2.将该节点从队列中删除（指针保存）
3.遍历该节点
4.如果该节点有左孩子，将其左孩子入队列; 如果有右孩子，将右孩子入队列

    vector<vector<int>> levelOrder(TreeNode* root) {
    
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(nullptr == root) return res;
        q.push(root);
        // 当第i层所有节点遍历完成后，如果队列不空，则队列中刚好放i+1层的节点
        while(!q.empty()){
    
            size_t size = q.size();
            vector<int> level;
            level.reserve(size);
            for(int i = 0; i < size; ++i){
    
                TreeNode* node = q.front();
                q.pop();   //将该节点从队列中删除（指针保存）
                level.push_back(node->val);
                //如果该节点有左孩子，将其左孩子入队列; 如果有右孩子，将右孩子入队列
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
            res.push_back(level);
        }
        return res;
    }

学会层序遍历Leetcode直接打十个！

 
 

二叉搜索树

又称二叉排序树，二叉搜索树是一个有序树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树
● 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
● 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
● 它的左、右子树也分别为二叉排序树

AVL树

平衡二叉树(Balance d Binary Tree或Height-Balanced·Tree), 因由前苏联数学家Adelson-Velskii和Landis提出，所以又称AVL树
平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：
( 1 ) 左子树和右子树的深度之差(平衡因子)的绝对值不超过 1;
( 2 ) 左子树和右子树也是平衡二叉树。

若将二叉树上结点的平衡因子(Balance Factor, BF)定义为该结点左子树和右子树的深度之
差，则平衡二叉树上所有结点的平衡因子只可能觅-1、0和1。

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log2n) ，搜索时间复杂度 O(log2n) 。

 

红黑树

AVL-tree之外,另一个颇具历史并被广泛运用的平衡二叉搜索树是RB- tree
(红黑树)。所谓RB-tree,不仅是-一个二叉搜索树，而且必须满足以下规则:

1. 每个节点不是红色就是 黑色
2. 根节点为黑色。
3. 如果节点为红， 其子节点必须为黑。
4. 任一节点至NULL (树尾端)的任何路径，所含黑色节点数必须相同。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树（红黑树）

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2N)，
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；
红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。