二叉树的实现

数据结构和算法的重要性毋庸置疑，本文将采用Java语言，来实现基本的二叉树。

实现二叉树对于二叉树本身的理解和递归算法的理解有很大的帮助，话不多说，直接进入主题：

基本数据结构

public class BinaryTree<T>{

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

    private Node<T> root == null; //树的根节点

    public static class Node<T> {
        private final T data;  //节点数据
        private Node<T> leftChild = null;   //左节点
        private Node<T> rightChild = null;  //右节点
        public Node(T t){
            this.data = t;
        }
        //...setter 和getter， 注意data无法改变，没有setter方法
    }
}

首先，创建二叉树基类BinaryTree，并实现内部类Node。
这里使用泛型类，可灵活的应用于不同数据类型的树。节点为内部类，毕竟不是只有二叉树这种树结构，其他的树结构和二叉树是有一定差异的。

求树的高度和节点数

// 求树的高度
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;
    }
}

使用递归算法来求树的高度，树的高度为根节点的左、右子树的高度较大者加1，依次类推。
同理可得，节点数的算法即递归条件改为左、右子数的节点数之和。

public size(){
    size(root)
}

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

计算高度和节点数已经完成，接下来做个小测试

    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
    }

至此，二叉树就基本实现了，是不是对于二叉树的结构和递归算法有了更深入的理解呢？顺便一提，二叉树的三种顺序遍历也是使用递归来实现的。

二叉树的顺序遍历

我们在测试代码中添加遍历的代码

    //定义节点访问方法
    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());
        }
    }
    //后续遍历
    public static void postOrder(BinaryTree.Node<String> node){
        if(node!=null){
            postOrder(node.getLeftChild());
            postOrder(node.getRightChild());
            visitNode(node);
        }
    }

    //测试代码
    System.out.println("先序遍历");
    preOrder(root);
    System.out.println("中序遍历");
    inOrder(root);
    System.out.println("后续遍历");
    postOrder(root);

测试结果如下图所示：

测试结果

另外，如果想让二叉树类的功能更加强大，可以编写相对应的迭代器进行二叉树的遍历，会让客户端代码更为简洁，这里就不再扩展了。