基本術語

1. 結點：樹中的一個獨立的單元。包含一個數(shù)據(jù)元素及若干個分支（二叉樹最多兩個）
2. 結點的度：結點擁有的子樹數(shù)稱為結點的度
3. 樹的度：樹的度是樹內(nèi)各個結點中最大的度
4. 葉子：度為0的結點稱為葉子或終端結點
5. 非終端結點：非葉子的結點
6. 雙親和孩子：結點的子樹的根稱為該結點的孩子，相應的該結點稱為孩子的雙親
7. 兄弟：父結點相同的結點即為兄弟結點
8. 樹的深度：樹中結點的最大層次稱為樹的深度或高度

介紹

與前面所介紹循序表以及鏈表的結構所不同，樹結構是一種描述非線性層次關系的數(shù)據(jù)結構。
其主要有一下幾個特點：

• 在一個樹結構中，有且僅有一個結點沒有直接前驅(qū)，那這個結點就是樹的根結點
• 除了根結點外，其余結點有且僅有一個直接前驅(qū)
• 每個結點可以有n個直接后驅(qū)（二叉樹最多只有兩個）
  而在樹結構中，二叉樹是最簡單的一種形式。在研究樹結構時，二叉樹是樹結構內(nèi)容中的重點。二叉樹的描述、處理相對簡單，而且更重要的是，任意的樹都可以轉(zhuǎn)為二叉樹，因此，二叉樹是所有樹的基礎。

二叉樹 結構圖

二叉樹-循環(huán)存儲.png

二叉樹遍歷算法

主要有以下三種：

• 先序遍歷
• 中序遍歷

• 后序遍歷

  
  
  先序遍歷.png
  
  
  中序遍歷.png
  
  
  后序遍歷.png

Java代碼實現(xiàn)

/**
 * 二叉樹結構
 * Created by Sheldon on 2019/4/3.
 * Project Name: alstudy.
 * Package Name: tree.
 */

// 二叉樹結構
public class ChainTree {

    // 結點數(shù)據(jù)
    String data;
    // 左子樹
    ChainTree leftTree;
    // 右子樹
    ChainTree rightTree;
    // 二叉樹根結點
    ChainTree root;

    /**
     * 初始化二叉樹，向根結點插入數(shù)據(jù)
     * @param data
     */
    ChainTree(String data){
        this.data = data;
        this.root = this;
    }

    public static ChainTree bulieTree(String[] datas, int index){
        ChainTree node = null;
        if (index<datas.length){
            String value = datas[index];
            if (value=="#"){
                return null;
            }
            node = new ChainTree(value);
//            node.leftTree = bulieTree(datas, 2*index+1);
//            node.rightTree = bulieTree(datas,2*index+2);
            node.addLeftTree(bulieTree(datas, 2*index+1));
            node.addRightTree(bulieTree(datas,2*index+2));
            return node;
        }
        return node;
    }

    /**
     * 添加左子樹
     * @return
     */
    public void addLeftTree(ChainTree node){
        leftTree = node;
    }

    /**
     * 添加右子樹
     * @return
     */
    public void addRightTree(ChainTree node){
        rightTree = node;
    }

    /**
     * 先序遍歷
     * @param root
     */
    public void DLR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            System.out.printf(node.data+", ");
            DLR(node.leftTree);
            DLR(node.rightTree);
        }
    }

    /**
     * 中序遍歷
     * @param root
     */
    public void LDR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LDR(node.leftTree);
            System.out.printf(node.data+", ");
            LDR(node.rightTree);
        }
    }

    /**
     * 后序遍歷
     * @param root
     */
    public void LRD(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LRD(node.leftTree);
            LRD(node.rightTree);
            System.out.printf(node.data+", ");
        }
    }

    /**
     * 二叉樹深度
     * @param node
     * @return
     */
    public int depth(ChainTree node){
        int depleft, depright;
        if (node==null){
            return 0;
        }else {
            depleft = depth(node.leftTree);
            depright = depth(node.rightTree);
            if (depleft>depright){
                return depleft+1;
            }else {
                return depright+1;
            }
        }
    }

    public static void main(String[] args) {
        String[] datas = new String[]{"0","1","2","3","4","5","6","7","8","9","10"};
        // 構建雙叉樹
        ChainTree chainTree = bulieTree(datas,0);
        // 先序遍歷（中->左->右）
        chainTree.DLR(chainTree.root);
        System.out.println();
        // 中序遍歷（左->右->中）
        chainTree.LDR(chainTree.root);
        System.out.println();
        // 后序遍歷（左->右->中）
        chainTree.LRD(chainTree.root);
        System.out.println();
        // 二叉樹深度
        System.out.println(chainTree.depth(chainTree.root));;
    }
}

運行結果：

運行結果