基本術(shù)語

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

介紹

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

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

二叉樹 結(jié)構(gòu)圖

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

二叉樹遍歷算法

主要有以下三種：

• 先序遍歷
• 中序遍歷

• 后序遍歷

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

Java代碼實現(xiàn)

/**
 * 二叉樹結(jié)構(gòu)
 * Created by Sheldon on 2019/4/3.
 * Project Name: alstudy.
 * Package Name: tree.
 */

// 二叉樹結(jié)構(gòu)
public class ChainTree {

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

    /**
     * 初始化二叉樹，向根結(jié)點插入數(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"};
        // 構(gòu)建雙叉樹
        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));;
    }
}

運行結(jié)果：

運行結(jié)果