数据结构之二叉树

递归构造二叉树

二叉树节点:

public 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 + " ";
    }


}

递归构造:

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

        TreeNode treeNode = null;
        if (index < array.length) {
            treeNode = new TreeNode(array[index]);
            // 对于顺序存储的完全二叉树，如果某个节点的索引为index，其对应的左子树的索引为2*index+1，右子树为2*index+1
            treeNode.left = createBinaryTree(array, 2 * index + 1);
            treeNode.right = createBinaryTree(array, 2 * index + 2);
        }
        if (treeNode != null) {
            System.out.println(treeNode.data);
        }
        return treeNode;

    }

图示:

图1.png

递归遍历

递归实现先序遍历

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

图示:

图2.png

递归实现中序遍历

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

图示:

图3.png

递归实现后序遍历

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

图示:

图4.png

非递归实现前序遍历

    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);
                }
            }
        }
     
    }

图示:

图5.png

非递归实现中序遍历

    // 中序遍历
    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;
            }
        }
    }

图示:

图6.png

非递归实现后序遍历

    //后序遍历 ,需要记录遍历过的节点
    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);
            }
            System.out.println(stack.size());
            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;
        }
    }