二叉树

二叉树每个节点最多有两个子树，并且子树有左右之分，其次序不能任意颠倒

java 实现二叉树

public class BinaryTree {

    private BiNode root;

    public BinaryTree(BiNode root) {
        this.root = root;
    }
    static class BiNode {

        char data;
        BiNode left;
        BiNode right;

        public BiNode(char data) {
            this.data = data;
        }
    }

遍历二叉树

• 前序遍历 访问根结点，先序遍历左子树，先序遍历右子树
• 中序遍历 中序遍历左子树，访问根结点，中序遍历右子树
• 后序遍历 后序遍历左子树，后序遍历右子树，访问根结点

二叉树的遍历可以使用递归的算法实习，也可以使用非递归的算法实现

递归遍历

递归遍历算法比较简单直接按照定义递归即可，代码如下：

/**
     * Recursive implementation of preOrder traversal
     */

    public void perOrderTraverseRecursive() {
        System.out.println("perOrderTraverseRecursive:");
        perOrderTraverseRecursive(root);
        System.out.println();
    }

    private void perOrderTraverseRecursive(BiNode node) {
        if (node != null) {
            visit(node);
            perOrderTraverseRecursive(node.left);
            perOrderTraverseRecursive(node.right);
        }
    }

    /**
     * Recursive implementation of inOrder traversal
     */

    public void inOrderTraverseRecursive() {
        System.out.println("inOrderTraverseRecursive:");
        inOrderTraverseRecursive(root);
        System.out.println();
    }

    private void inOrderTraverseRecursive(BiNode node) {

        if (node != null) {
            inOrderTraverseRecursive(node.left);
            visit(node);
            inOrderTraverseRecursive(node.right);
        }
    }


    /**
     * Recursive implementation of postOrder traversal
     */
    public void postOrderTraverseRecursive() {
        System.out.println("postOrderTraverseRecursive:");
        postOrderTraverseRecursive(root);
        System.out.println();
    }

    private void postOrderTraverseRecursive(BiNode node) {
        if (node != null) {
            postOrderTraverseRecursive(node.left);
            postOrderTraverseRecursive(node.right);
            visit(node);
        }

    }

非递归的遍历算法

非递归的遍历算法使用Stack实现，其中前序遍历和中序遍历相对来说比较简单，结构也类似
代码如下：

/**
     * Stack implementation of preOrder traversal
     */

    public void preOrderTraverse() {
        System.out.println("preOrder Traverse use Stack:");
        Stack<BiNode> nodeStack = new Stack<>();
        BiNode node = root;
        while (!nodeStack.isEmpty() || node != null) {
            while (node != null) {
                visit(node);
                nodeStack.push(node);
                node = node.left;

            }
            if (!nodeStack.isEmpty()) {
                node = nodeStack.pop();
                node = node.right;
            }
        }
        System.out.println();
    }

    /**
     * Stack implementation of inOrder traversal
     */

    public void inOrderTraverse() {

        System.out.println("inOrder Traverse use Stack:");
        Stack<BiNode> nodeStack = new Stack<>();
        BiNode node = root;
        while (!nodeStack.isEmpty() || node != null) {
            while (node != null) {
                nodeStack.push(node);
                node = node.left;

            }
            if (!nodeStack.isEmpty()) {
                node = nodeStack.pop();
                visit(node); //访问根结点
                node = node.right;
            }
        }
        System.out.println();
    }

后序遍历的非递归算法麻烦一点，如下给出了后序遍历的两个实现，其中第一个使用一个栈完成，但是逻辑看起来复杂一些，后一个使用两个栈完成，逻辑看起来比较简洁

/**
     * Stack implementation of postOrder traversal
     */
    public void postOrderTraverse() {
        System.out.println("postOrder Traverse use Stack:");
        BiNode node = root;
        if (node != null) {
            Stack<BiNode> stack = new Stack<>();
            stack.push(node);
            BiNode c;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && node != c.left && node != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && node != c.right) {
                    stack.push(c.right);
                } else {
                    visit(stack.pop());
                    node = c;
                }
            }
        }
        System.out.println();
    }

    /**
     * Double Stack implementation of postOrder traversal
     */
    public void postOrderTraverseWithDoubleStack() {
        System.out.println("postOrderTraverse use Double Stack:");
        BiNode node = root;
        if (node != null) {
            Stack<BiNode> s1 = new Stack<>();
            Stack<BiNode> s2 = new Stack<>();
            s1.push(root);
            while (!s1.isEmpty()) {
                node = s1.pop();
                s2.push(node);
                if (node.left != null) {
                    s1.push(node.left);
                }
                if (node.right != null) {
                    s1.push(node.right);
                }
            }
            while (!s2.isEmpty()) {
                visit(s2.pop());
            }
        }

        System.out.println();
    }

创建二叉树

我们根据先序遍历的字符串创建二叉树，使用#表示空指针

比如AB##DE##C#F## 会创建如下一个二叉树:

二叉树创建的代码如下：

 /**
     * @param s preOrder string represent of Binary Tree， # mean nil
     * @return Binary Tree construct by the preOrder string
     */
    public static BinaryTree createBiTree(String s) {
        System.out.println("createBiTree with preOrder String : " + s);
        i = 0;
        return new BinaryTree(BinaryTree.createBiTreeNode(s));
    }


    private static BiNode createBiTreeNode(String s) {
        BiNode node = null;
        if (s.charAt(i) != '#') {// char is not #， do recursion
            node = new BiNode(s.charAt(i));
            i++; // when successful create a BiNode ,increase string index
            node.left = createBiTreeNode(s);
            node.right = createBiTreeNode(s);


        } else {// Character # encountered, increase  string index
            i++;
        }
        return node;

    }

创建二叉树并测试

 public static void main(String[] args) {
        BinaryTree binaryTree = createBiTree("AB##DE##C#F##");
        binaryTree.perOrderTraverseRecursive();
        binaryTree.inOrderTraverseRecursive();
        binaryTree.postOrderTraverseRecursive();
        binaryTree.preOrderTraverse();
        binaryTree.inOrderTraverse();
        binaryTree.postOrderTraverse();
        binaryTree.postOrderTraverseWithDoubleStack();
    }

测试结果

createBiTree with preOrder String : AB##DE##C#F##
perOrderTraverseRecursive:
A B D E C F 
inOrderTraverseRecursive:
B A E D C F 
postOrderTraverseRecursive:
B E F C D A 
preOrder Traverse use Stack:
A B D E C F 
inOrder Traverse use Stack:
B A E D C F 
postOrder Traverse use Stack:
B E F C D A 
postOrderTraverse use Double Stack:
B E F C D A 

完整代码地址

https://github.com/spraysss/data-structure/blob/master/src/main/java/com/ds/tree/BinaryTree.java