數(shù)據(jù)結(jié)構(gòu)和算法的重要性毋庸置疑，本文將采用Java語言，來實(shí)現(xiàn)基本的二叉樹。

實(shí)現(xiàn)二叉樹對(duì)于二叉樹本身的理解和遞歸算法的理解有很大的幫助，話不多說，直接進(jìn)入主題：

基本數(shù)據(jù)結(jié)構(gòu)

public class BinaryTree<T>{

    public BinaryTree(Node<T> node){
        this.root = node;
    }

    private Node<T> root == null; //樹的根節(jié)點(diǎn)

    public static class Node<T> {
        private final T data;  //節(jié)點(diǎn)數(shù)據(jù)
        private Node<T> leftChild = null;   //左節(jié)點(diǎn)
        private Node<T> rightChild = null;  //右節(jié)點(diǎn)
        public Node(T t){
            this.data = t;
        }
        //...setter 和getter， 注意data無法改變，沒有setter方法
    }
}

首先，創(chuàng)建二叉樹基類BinaryTree，并實(shí)現(xiàn)內(nèi)部類Node。
這里使用泛型類，可靈活的應(yīng)用于不同數(shù)據(jù)類型的樹。節(jié)點(diǎn)為內(nèi)部類，畢竟不是只有二叉樹這種樹結(jié)構(gòu)，其他的樹結(jié)構(gòu)和二叉樹是有一定差異的。

求樹的高度和節(jié)點(diǎn)數(shù)

// 求樹的高度
public getHeight(){
    getHeight(root);
}

private int getHeight(Node<T> node) { 
    if (node == null) {  //基線條件
        return 0;
    } else {  //遞歸條件
        int i = getHeight(node.getLeftChild());
        int j = getHeight(node.getRightChild());
        return i >= j ? i + 1 : j + 1;
    }
}

使用遞歸算法來求樹的高度，樹的高度為根節(jié)點(diǎn)的左、右子樹的高度較大者加1，依次類推。
同理可得，節(jié)點(diǎn)數(shù)的算法即遞歸條件改為左、右子數(shù)的節(jié)點(diǎn)數(shù)之和。

public size(){
    size(root)
}

private size(Node<T> node){
    if(node == null){
        return 0;
    } else {
        return size(node.getLeftChild())
            + size(node.getRightChild())
            + 1;
    }
}

計(jì)算高度和節(jié)點(diǎn)數(shù)已經(jīng)完成，接下來做個(gè)小測(cè)試

    public static void main(String[] args) {
        BinaryTree.Node<String> root = new BinaryTree.Node<String>("root");
        BinaryTree<String> tree = new BinaryTree<String>(root);
        BinaryTree.Node<String> leftNode = new BinaryTree.Node<String>("left");
        leftNode.setLeftChild(new BinaryTree.Node<String>("left-left"));
        root.setLeftChild(leftNode);
        root.setRightChild(new BinaryTree.Node<String>("right"));

        System.out.println(tree.getHeight());   //輸出3
        System.out.println(tree.size());    //輸出4
    }

至此，二叉樹就基本實(shí)現(xiàn)了，是不是對(duì)于二叉樹的結(jié)構(gòu)和遞歸算法有了更深入的理解呢？順便一提，二叉樹的三種順序遍歷也是使用遞歸來實(shí)現(xiàn)的。

二叉樹的順序遍歷

我們?cè)跍y(cè)試代碼中添加遍歷的代碼

    //定義節(jié)點(diǎn)訪問方法
    public static void visitNode(BinaryTree.Node<String> node){
        System.out.println(node.getData());
    }

    //先序遍歷
    public static void preOrder(BinaryTree.Node<String> node){
        if(node!=null){
            visitNode(node);
            preOrder(node.getLeftChild());
            preOrder(node.getRightChild());
        }
    }
    //中序遍歷
    public static void inOrder(BinaryTree.Node<String> node){
        if(node!=null){
            inOrder(node.getLeftChild());
            visitNode(node);
            inOrder(node.getRightChild());
        }
    }
    //后續(xù)遍歷
    public static void postOrder(BinaryTree.Node<String> node){
        if(node!=null){
            postOrder(node.getLeftChild());
            postOrder(node.getRightChild());
            visitNode(node);
        }
    }

    //測(cè)試代碼
    System.out.println("先序遍歷");
    preOrder(root);
    System.out.println("中序遍歷");
    inOrder(root);
    System.out.println("后續(xù)遍歷");
    postOrder(root);

測(cè)試結(jié)果如下圖所示：

測(cè)試結(jié)果

另外，如果想讓二叉樹類的功能更加強(qiáng)大，可以編寫相對(duì)應(yīng)的迭代器進(jìn)行二叉樹的遍歷，會(huì)讓客戶端代碼更為簡(jiǎn)潔，這里就不再擴(kuò)展了。