二叉树操作

1、定义二叉树

class TreeNode<T> {
        public int index;
        public T data;
        public TreeNode<T> leftNode;
        public TreeNode<T> rightNode;
        public TreeNode(int index, T data) {
            this.index = index;
            this.data = data;
        }
    }

2、创建二叉树

    private TreeNode<String>  root = null;
    
    public BinaryTree(){
        root = new TreeNode<String>(1, "A");
    }
    
    /**
     * 构建二叉树
     *         A
     *     B       C
     * D      E        F
     */
    private void createBinaryTree() {
        TreeNode<String> nodeB = new TreeNode<String>(2, "B");
        TreeNode<String> nodeC = new TreeNode<String>(3, "C");
        TreeNode<String> nodeD = new TreeNode<String>(4, "D");
        TreeNode<String> nodeE = new TreeNode<String>(5, "E");
        TreeNode<String> nodeF = new TreeNode<String>(6, "F");
        root.leftNode = nodeB;
        root.rightNode = nodeC;
        nodeB.leftNode = nodeD;
        nodeB.rightNode = nodeE;
        nodeC.leftNode = nodeF;
    }

3、计算二叉树的深度

    private int getHeight() {
        return getHeight(root);
    }
    
    private int getHeight(TreeNode<String> node) {
        if(node == null) {
            return 0;
        }else {
            int leftHeight = getHeight(node.leftNode);
            int rightHeight = getHeight(node.rightNode);
            return leftHeight > rightHeight ? (leftHeight + 1):(rightHeight + 1);
        }
    }

4、计算二叉树的节点

    private int getSize() {
        return getSize(root);
    }
    
    private int getSize(TreeNode<String> node) {
        if(node == null) {
            return 0;
        } else {
            int rightSize = getSize(node.rightNode);
            int leftSize = getSize(node.leftNode);
            return rightSize+leftSize+1;
        }
    }

5、前序遍历

   private void preOrder(TreeNode<String> node) {
        if(node == null) {
            return;
        }else {
            System.out.println("preorder node : " + node.data);
            preOrder(node.leftNode);
            preOrder(node.rightNode);
        }
    }

6、中序遍历

    private void midOrder(TreeNode<String> node) {
        if(node == null) {
            return;
        }else {
            midOrder(node.leftNode);
            System.out.println("midOrder node : " + node.data);
            midOrder(node.rightNode);
        }
    }

7、后序遍历

    private void postOrder(TreeNode<String> node) {
        if(node == null) {
            return;
        }else {
            postOrder(node.leftNode);
            postOrder(node.rightNode);
            System.out.println("postOrder node : " + node.data);
        }
    }

8、采用栈实现后序遍历

    private void noOrder(TreeNode<String> node) {
        if(node == null) {
            return;
        }else {
            Stack<TreeNode<String>> stack = new Stack<TreeNode<String>>();
            stack.push(node);
            while(!stack.isEmpty()) {
                TreeNode<String> n = stack.pop();
                System.out.println("postOrder node : " + n.data);
                TreeNode<String> leftNode = n.leftNode;
                if(leftNode != null) {
                    noOrder(leftNode);
                }
                TreeNode<String> rightNode = n.rightNode;
                if(rightNode != null) {
                    noOrder(rightNode);
                }
            }
            
        }
    }

9、测试

   public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.createBinaryTree();
        int height = binaryTree.getHeight();
        System.out.println("height:"+height);
        int size = binaryTree.getSize();
        System.out.println("size:"+size);
        System.out.println("--------preOrder--------");
        binaryTree.preOrder(binaryTree.root);
        System.out.println("--------midOrder--------");
        binaryTree.midOrder(binaryTree.root);
        System.out.println("--------postOrder--------");
        binaryTree.postOrder(binaryTree.root);
        System.out.println("--------noOrder--------");
        binaryTree.noOrder(binaryTree.root);
    }