二叉樹第一部分

二叉樹

樹形結構

樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

它具有以下的特點：有一個特殊的節點，稱為根節點，

根節點沒有前驅節點除根節點外，

其餘節點被分成M(M > 0)個互不相交的集合T1、T2、…、Tm，其中每一個集合 Ti (1 <= i<= m) 又是一棵與樹類似的子樹。

每棵子樹的根節點有且只有一個前驅，可以有0個或多個後繼
樹是遞歸定義的。

概念（重要）

知道了 概念 那麼 如何 錶示 樹呢 ？？？

樹的錶示形式

樹結構相對線性錶就比較複雜了，要存儲錶示起來就比較麻煩了，實際中樹有很多種錶示方式，如：雙親錶示法，
孩子錶示法、孩子兄弟錶示法等等。我們這裏就簡單的了解其中最常用的**孩子兄弟錶示

2、二叉樹

一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉
樹組成。
二叉樹的特點：

1. 每個結點最多有兩棵子樹，即二叉樹不存在度大於 2 的結點。

2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹。

   （有序 不是 大小有序 而是 順序）
   

兩種特殊的二叉樹

概念 ：

1. 滿二叉樹: 一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果
   一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹。
2. 完全二叉樹: 完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對於深度為K的，有n
   個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全
   二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
   
   

二叉樹的 性質

看完了二叉樹的性質那麼接下來我們來了解一下二叉樹的存儲

3、二叉樹的存儲

二叉樹的存儲結構分為：順序存儲和類似於鏈錶的鏈式存儲

這裏我們 主要理解 鏈式存儲 而順序 存儲 則 會在堆中常用

二叉樹的鏈式存儲是通過一個一個的節點引用起來的，常見的錶示方式有二叉和三叉錶示方式，具體如下：

// 孩子錶示法
class Node {
    
int val; // 數據域
Node left; // 左孩子的引用，常常代錶左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代錶右孩子為根的整棵右子樹
}


// 孩子雙親錶示法
class Node {
    
int val; // 數據域
Node left; // 左孩子的引用，常常代錶左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代錶右孩子為根的整棵右子樹
Node parent; // 當前節點的根節點
}

二叉樹的創建

這裏 我們 創建一個二叉樹 會使用 一個非常非常佬的 創建方式

不是 真正的 創建方式 ，我們先這樣 創建 來理解 一下 二叉樹的性質


附上代碼

class BTNode {
    
    public char val;
    // 左孩子引用
    public BTNode left;
    // 右孩子
    public BTNode right;
    public BTNode (char val) {
    
        this.val = val;
    }
}
public class BinaryTree {
    
    public BTNode root; // 二叉樹的根節點

    public BTNode createTree() {
    
        BTNode A = new BTNode('A');
        BTNode B = new BTNode('B');
        BTNode C = new BTNode('C');
        BTNode D = new BTNode('D');
        BTNode E = new BTNode('E');
        BTNode F = new BTNode('F');
        BTNode G = new BTNode('G');
        BTNode H = new BTNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
}

二叉樹的遍曆（重點）

3種遍曆方式 （訪問二叉樹時機不同）

1.前序遍曆（先根遍曆

2.中序遍曆

3.後續遍曆

總結

學習完了 二叉樹 的 三種遍曆 方式 發現 他們 是 沿著一條路線 的，只是打印 的 時機 不同而已

練習

1.代碼實現前序遍曆

1.前序遍曆 根 --》 左子樹 --》 右子樹

 // 通過 遞歸 實現前序遍曆
    void preOrder(BTNode root) {
    
        if(root == null) {
    
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

知道了 前序 遍曆 那麼 我們直接 來做 前序遍曆 的 oj 題

二叉樹的前序遍曆

方法一 ：遍曆 思路

class Solution {
    
    //這裏 保證 了 list 都 只有 一份 
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
    
        
        if(root == null) {
    
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);  
        return list;
    }
}

方法二 ： 子問題思路

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
    
         List<Integer> list = new ArrayList<>();
        if(root == null) {
    
            return list;
        }
        list.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);  
        list.addAll(rightTree);

        return list;
    }
}

·知道前序 遍曆 那麼 中序遍曆 和 後續遍曆 那麼 不就是 調整一下 遞歸 順序嗎

2.中序遍曆 左子樹 --》 根 --》 右子樹

   // 中序遍曆
    // 左子樹 --》 根 --》 右子樹
    void inOrderTraversal(BTNode root) {
    
        if(root == null) {
    
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }

二叉樹的中序遍曆

方法一 ： 遍曆思路

class Solution {
    
    List<Integer> list  = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
    
        if(root == null) {
    
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
}

方法二 ： 子問題思路

class Solution {
    
    public List<Integer> inorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        if(root == null) {
    
            return list;
        }
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);

        list.add(root.val);

        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
}

3.後序遍曆 左子樹 --》右子樹 --》 根

    // 後序遍曆
    // 右子樹 --》 左子樹 --》 根
    void postOrderTraversal(BTNode root) {
    
        if(root == null) {
    
            return;
        }
        inOrderTraversal(root.left);
        inOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

二叉樹的後序遍曆

方法一 ： 遍曆思想

class Solution {
    
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
    
        if(root == null) {
    
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}

方法二 ： 子問題思路

class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
    
        List<Integer> list = new ArrayList();

        if(root == null) {
    
            return list;
        }
        List<Integer> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        list.addAll(rightTree);

        list.add(root.val);
        return list;
    }
}

這裏來 一個 idea 快捷鍵 整體改變 變量命 shift 加 f6

程序遍曆

設二叉樹的根節點所在層數為1，層序遍曆就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然後從
左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是
層序遍曆。

最後在來 4道題 結束 第一部分二叉樹