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

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

考慮一種極端情況，一棵深度為k的右斜數(shù)，它只有k個(gè)節(jié)點(diǎn)，卻需要分配2^k-1個(gè)存儲(chǔ)單元，這顯然是對(duì)空間的浪費(fèi)，所以順序的存儲(chǔ)結(jié)構(gòu)只適用于完全二叉樹。

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

二叉樹遍歷原理

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

二叉樹的遍歷方法

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

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

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

二叉樹遍歷的JAVA實(shí)現(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)榫€索二叉樹的過程稱作是線索化。

線索化的實(shí)質(zhì)

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