在計(jì)算機(jī)科學(xué)中秩铆，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)嬉愧。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

下面的代碼松申，給大家展示如何創(chuàng)建一個(gè)二叉樹灿里。這里我們采用鏈?zhǔn)酱鎯?chǔ)关炼，不過為了創(chuàng)建方便，例子都是滿二叉樹匣吊，或者完全二叉樹盗扒。

二叉樹的操作，可以采用遞歸和迭代的方式缀去。其遍歷操作有：

• 前序遍歷： 訪問根節(jié)點(diǎn) ->前序遍歷左子樹 ->前序遍歷右子樹
• 中序遍歷： 中序遍歷左子樹 ->訪問根節(jié)點(diǎn) ->中序遍歷右子樹
• 后序遍歷： 后序遍歷左子樹 ->后序遍歷右子樹 ->訪問根節(jié)點(diǎn)

package suanfa;

import java.util.Stack;

import sun.reflect.generics.tree.Tree;

class TreeNode {

    public int data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
        super();
        this.data = data;
    }

    @Override
    public String toString() {
        return data + " ";
    }

}

public class BinaryTree {

    public TreeNode root = null;

    public BinaryTree(int[] array, int index) {
        root = createBinaryTree(array, index);
    }
    // 創(chuàng)建二叉樹

    private TreeNode createBinaryTree(int[] array, int index) {

        TreeNode treeNode = null;
        if (index < array.length) {
            treeNode = new TreeNode(array[index]);
            // 對(duì)于順序存儲(chǔ)的完全二叉樹侣灶，如果某個(gè)節(jié)點(diǎn)的索引為index，其對(duì)應(yīng)的左子樹的索引為2*index+1缕碎，右子樹為2*index+1
            treeNode.left = createBinaryTree(array, 2 * index + 1);
            treeNode.right = createBinaryTree(array, 2 * index + 2);
        }
        return treeNode;

    }

    private void showData(TreeNode node) {
        System.out.print(node);
    }

    // 遞歸遍歷二叉樹

    // 先序遍歷（前序遍歷）
    public void preOrder(TreeNode node) {
        if (node != null) {
            showData(node);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // 中序遍歷
    public void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            showData(node);
            inOrder(node.right);
        }
    }
    // 后序遍歷

    public void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            showData(node);
        }
    }

    // 非遞歸遍歷二叉樹

    // 前序遍歷

    public void noRecursionPreOrder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        if (node != null) {
            stack.push(node);
            while (!stack.empty()) {
                node = stack.pop();
                showData(node);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }

            }
        }
    }

    // 中序遍歷
    public void noRecursionInOrder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = node;
        while (p != null || stack.size() > 0) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            if (stack.size() > 0) {
                p = stack.pop();
                showData(p);
                p = p.right;
            }
        }
    }
    
    //后序遍歷 ,需要記錄遍歷過的節(jié)點(diǎn)
    public void noRecursionPostOrder(TreeNode node)
    {
        TreeNode pre=node;
        Stack<TreeNode> stack=new Stack<>();
        while(node!=null)
        {
            for(;node.left!=null;node=node.left)
            {
                stack.push(node);
            }
            while(node!=null&&(node.right==null||node.right==pre))
            {
                showData(node);
                pre=node;
                if(stack.empty()) return;
                node=stack.pop();
            }
            stack.push(node);
            node=node.right;
        }
    }
    
    public static void main(String[] args)
    {
        //順序存儲(chǔ)的滿二叉樹或者完全二叉樹
        int[] arr={1,2,3,4,5,6,7,8,9};
        BinaryTree bt=new BinaryTree(arr, 0);
        System.out.println("遞歸前序遍歷：");
        bt.preOrder(bt.root);
        System.out.println();
        System.out.println("遞歸中序遍歷：");
        bt.inOrder(bt.root);
        System.out.println();
        System.out.println("遞歸后序遍歷：");
        bt.postOrder(bt.root);
        System.out.println();
        System.out.println("非遞歸前序遍歷：");
        bt.noRecursionPreOrder(bt.root);
        System.out.println();
        System.out.println("非遞歸中序遍歷：");
        bt.noRecursionInOrder(bt.root);
        System.out.println();
        System.out.println("非遞歸后序遍歷：");
        bt.noRecursionPostOrder(bt.root);
        
    }

}

輸出結(jié)果：

Paste_Image.png