二叉樹的存儲結(jié)構(gòu)

順序存儲：就是用一組數(shù)組來存儲二叉樹中節(jié)點，并且節(jié)點的存儲位置绪撵，也就是數(shù)組的下標(biāo)要能體現(xiàn)節(jié)點之間的邏輯關(guān)系姆蘸。

考慮一種極端情況，一棵深度為k的右斜數(shù)翅敌，它只有k個節(jié)點羞福，卻需要分配2^k-1個存儲單元，這顯然是對空間的浪費蚯涮，所以順序的存儲結(jié)構(gòu)只適用于完全二叉樹治专。

二叉鏈表：既然順序存儲結(jié)構(gòu)實用性不強(qiáng)，我們就要考慮練市存儲結(jié)構(gòu)遭顶。二叉樹每個節(jié)點最多有兩個孩子张峰，所以它設(shè)計一個數(shù)據(jù)域和兩個指針域是比較自然的想法。我們稱這樣的鏈表叫做二叉鏈表棒旗。

二叉樹遍歷原理

二叉樹的遍歷是從根節(jié)點出發(fā)喘批，按照某種次序依次訪問二叉樹中所有節(jié)點，使得每個節(jié)點的被訪問一次且僅被訪問一次嗦哆。

二叉樹的遍歷方法

前序遍歷：根-->左-->右

中序遍歷：左-->根-->右

后序遍歷：左-->右-->根

二叉樹遍歷的JAVA實現(xiàn)

public class BinaryTree {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        System.out.print("前序遍歷：");
        binaryTree.preOrderTraverse(binaryTree.init());
        System.out.println();
        System.out.print("中序遍歷：");
        binaryTree.InOrderTraverse(binaryTree.init());
        System.out.println();
        System.out.print("后序遍歷：");
        binaryTree.PostOrderTraverse(binaryTree.init());
    }

    private BinaryTreeNode init() {
        BinaryTreeNode root = new BinaryTreeNode("a");
        BinaryTreeNode nodeB = new BinaryTreeNode("b");
        BinaryTreeNode nodeC = new BinaryTreeNode("c");
        root.setLchild(nodeB);
        root.setRchild(nodeC);
        BinaryTreeNode nodeD = new BinaryTreeNode("d");
        BinaryTreeNode nodeE = new BinaryTreeNode("e");
        nodeB.setLchild(nodeD);
        nodeB.setRchild(nodeE);
        BinaryTreeNode nodeH = new BinaryTreeNode("h");
        nodeD.setLchild(nodeH);
        BinaryTreeNode nodeK = new BinaryTreeNode("k");
        nodeH.setRchild(nodeK);
        BinaryTreeNode nodeF = new BinaryTreeNode("f");
        BinaryTreeNode nodeG = new BinaryTreeNode("g");
        nodeC.setLchild(nodeF);
        nodeC.setRchild(nodeG);
        BinaryTreeNode nodeI = new BinaryTreeNode("i");
        nodeF.setLchild(nodeI);
        BinaryTreeNode nodeJ = new BinaryTreeNode("j");
        nodeG.setRchild(nodeJ);
        return root;
    }

    /**
     * 前序遍歷
     *
     * @param binaryTreeNode
     */
    private void preOrderTraverse(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return;
        }
        System.out.print(binaryTreeNode.getData() + " ");
        preOrderTraverse(binaryTreeNode.getLchild());
        preOrderTraverse(binaryTreeNode.getRchild());
    }

    /**
     * 中序遍歷
     *
     * @param binaryTreeNode
     */
    private void InOrderTraverse(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return;
        }
        InOrderTraverse(binaryTreeNode.getLchild());
        System.out.print(binaryTreeNode.getData() + " ");
        InOrderTraverse(binaryTreeNode.getRchild());
    }

    /**
     * 后序遍歷
     *
     * @param binaryTreeNode
     */
    private void PostOrderTraverse(BinaryTreeNode binaryTreeNode) {
        if (binaryTreeNode == null) {
            return;
        }
        PostOrderTraverse(binaryTreeNode.getLchild());
        PostOrderTraverse(binaryTreeNode.getRchild());
        System.out.print(binaryTreeNode.getData() + " ");
    }

    class BinaryTreeNode {
        private String data;
        private BinaryTreeNode lchild;
        private BinaryTreeNode rchild;

        public BinaryTreeNode() {
        }

        public BinaryTreeNode(String data) {
            this.data = data;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public BinaryTreeNode getLchild() {
            return lchild;
        }

        public void setLchild(BinaryTreeNode lchild) {
            this.lchild = lchild;
        }

        public BinaryTreeNode getRchild() {
            return rchild;
        }

        public void setRchild(BinaryTreeNode rchild) {
            this.rchild = rchild;
        }
    }
}

線索二叉樹

指向前驅(qū)和后繼的指針為線索谤祖，加上線索的二叉鏈表稱為線索鏈表。相應(yīng)的二叉樹就稱為線索二叉樹老速。

二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱作是線索化粥喜。

線索化的實質(zhì)

就是將二叉鏈表中的空指針改為指向前驅(qū)和后繼的線索。由于前驅(qū)和后繼的信息只有在遍歷該二叉樹時才能得到橘券。所以線索化的過程就是在遍歷的過程中修改空指針额湘。