自己動手作圖深入理解二叉樹、滿二叉樹及完全二叉樹

• 2020 年 7 月 24 日
• 筆記
• JAVA, 數據結構

一、背景

二叉樹是數據結構中的重點，也是難點。二叉樹是一種非線性結構，比數組、棧、隊列等線性結構相比複雜度更高，想要做到心中有「樹」，需要自己動手畫圖、觀察、思考，才能領會其真諦。該文將會結合圖形，深入理解二叉樹、滿二叉樹及完全二叉樹的概念。

二、基本概念

2.1 結點

• 結點是組成二叉樹的最小單元。
  — 用圖形表示
  
  — 用代碼表示

	// 結點
	class Node<E> {
        E e;
        Node left, right;

        Node(E e) {
            this.e= e;
            this.left = null;
            this.right = null;
        }
    }

2.2 二叉樹

• 每個結點的度（結點擁有的子樹數目）不超過2的樹叫做二叉樹
  

2.2.1 二叉樹的深度

• 結點的最大層次數稱為樹的深度或高度
  

2.3 滿二叉樹

• 指深度為k且有2^k-1個結點的二叉樹，即所有分支結點都存在左子樹和右子樹，並且所有葉子都在同一層上。
• 下圖中深度為4，2⁴-1=15個結點，且所有葉子都在第四層上。
  

2.4 完全二叉樹

• 一顆深度為k的二叉樹，k層的結點都是連續靠左並不可隔開的，並且1～k-1層的結點也組成了一棵滿二叉樹，這樣的二叉樹，我們稱為完全二叉樹。
  

2.4.1 完全二叉樹的線性存儲

• 出於簡便起見,完全二叉樹通常採用數組進行線性存儲
  

/**
 * 完全二叉樹的線性存儲
 *
 * @author zhuhuix
 * @date 2020-06-24
 */
public class FullBinaryTree {
    private Object[] arr;
    private int size;

    FullBinaryTree(int capacity) {
        this.arr = new Object[capacity + 1];
        this.size = 0;
    }

    public int getSize() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void add(Object e, int index) {
        assert index <= this.arr.length;
        this.arr[index] = e;
        this.size++;
    }

    @Override
    public String toString() {
        return "FullBinaryTree{" +
                "arr=" + Arrays.toString(arr) +
                ", size=" + size +
                '}';
    }
    
    public static void main(String[] args) {
        FullBinaryTree fullBinaryTree = new FullBinaryTree(26);
        // 從下標1開始存入26個字母
        for (Character c = 'A'; c <= 'Z'; c++) {
            fullBinaryTree.add(c, c - 'A' + 1);
        }

        System.out.println( fullBinaryTree.toString());
    }
}

2.4.2 完全二叉樹的創建與遍歷

/**
 * 完全二叉樹的創建與遍歷
 *
 * @author zhuhuix
 * @date 2020-06-24
 */
public class BinaryTree {

    // 結點
    private Node root;
    // 結點數
    private int size;
    // 存放結點
    private ArrayList<Node> list;

    public BinaryTree() {
        this.root = null;
        this.size = 0;
        this.list = new ArrayList<>();
    }

    public void createTree(Object[] array){
        for(int i=0;i<array.length;i++){
            Node node =new Node(array[i]);
            list.add(node);
            if (this.root==null){
                this.root = node;
            }
        }
        if(list.size()>0){
            for(int i=0;i<array.length/2;i++){
                if(2*i+1<list.size()) {
                    list.get(i).left=list.get(2 * i + 1);
                }
                if(2*i+2<list.size()) {
                    list.get(i).right=list.get(2 * i + 2);
                }
            }
        }
    }

    // 前序遍歷
    public void preOrder(Node root){
        if(root == null){
            return ;
        }
        else{
            System.out.println(root.getData());
        }
        preOrder(root.left);
        preOrder(root.right);
    }

    public Node getRoot() {
        return root;
    }

    // 私有內部類-樹結點
    private class Node {
        Object data;
        Node left, right;

        Node(Object data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        Object getData() {
            return data;
        }
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Character[] array ={'A','B','C','D','E','F','G','H','I','J','K','L',
                'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
        binaryTree.createTree(array);
        binaryTree.preOrder(binaryTree.getRoot());
    }
}