Java教程

二叉树实现非递归遍历(java)

本文主要是介绍二叉树实现非递归遍历(java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二叉树先序,中序,后序遍历都是相对于父节点(有孩子的节点),或者单一节点而言的。左右二孩节点相对位置不变。此节点如果先遍历则为先序,在中间则为中序,在最后则为后续。
在这里插入图片描述
图片来源于百度!

代码展示:

import java.util.Stack;

public class PreMidAfter {
    public static void main(String[] args) {
        TreeNode[] treeNodes = new TreeNode[10];
        for (int i = 0; i < 10; i++) {
            treeNodes[i] = new TreeNode(i);
        }
        for (int i = 0; i <= 16/2-1; i++) {
            if(i*2+1 < 10)
                treeNodes[i].left = treeNodes[i*2+1];
            if(i*2+2 < 10)
                treeNodes[i].right = treeNodes[i*2+2];
        }
        TreeNode header = treeNodes[0];
        //pre(header);
        //mid(header);
        after(header);


    }

    /**
     * 先序遍历
     * 访问当前元素,并压入栈中一次遍历左孩节点,当左孩为空,则找寻其右孩节点
     * 按照上面循环,遍历每个左右分支
     * @param root
     */
    public static void pre(TreeNode root)
    {
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty())
        {
            while (root!=null)
            {
                System.out.print(root.val+"\t");
                stack.push(root);
                root = root.left;
            }
            if(stack!=null)
            {
                root = stack.pop();
                root = root.right;
            }
        }

    }

    /**
     * 与先序遍历类似
     * @param root
     */
    public static void mid(TreeNode root)
    {
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty())
        {
            while (root!=null)
            {

                stack.push(root);
                root = root.left;
            }
            if(stack!=null)
            {
                root = stack.pop();
                System.out.print(root.val+"\t");

                root = root.right;
            }
        }
    }

    /**
     * 当从右孩节点返回到父节点,则可以输出值
     * @param root
     */
    public static void after(TreeNode root)
    {
        int left=1,right = 2;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (root!=null || !stack.isEmpty())
        {
            //压入所有左节点
            while (root!=null)
            {
                stack.push(root);
                stack2.push(left);
                root = root.left;
            }
            while (!stack.isEmpty() && stack2.peek() == right)
            {
                stack2.pop();
                System.out.print(stack.pop().val+" ");
            }
            if(!stack.isEmpty() && stack2.peek() == left)
            {
                stack2.pop();
                stack2.push(right);
                root = stack.peek().right;
            }
        }
    }

}
这篇关于二叉树实现非递归遍历(java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!