二叉树的遍历算法Java实现

电玩女神 2022-06-13 13:18 148阅读 0赞

学习并总结了二叉树的递归和非递归的遍历方式~

[http://blog.csdn.net/sheepmu/article/details/28941285][http_blog.csdn.net_sheepmu_article_details_28941285]  
[http://blog.csdn.net/clam\_clam/article/details/6845399][http_blog.csdn.net_clam_clam_article_details_6845399]  
学习并总结了这两位博主的文章，很赞，谢谢~

下面是自己边敲边学的代码。

package tree;
    import java.util.LinkedList;
    public class Binaryorder {
        
    
        private TreeNode root; //根节点
        public Binaryorder()
        {
    
        }
        public Binaryorder(TreeNode root)
        {
            this.root=root;
        }
        public TreeNode getRoot()
        {
            return root;
        }
        public void setRoot(TreeNode root)
        {
            this.root=root;
        }

/*
         * 递归 前序遍历
         */
        public void preOrder(TreeNode node)
        {
            if(node!=null)
            {
                System.out.print(node.getdata()+" ");
                preOrder(node.getleft());
                preOrder(node.getright());
            }
        }
        /*
         * 递归 中序遍历
         */
        public void inOrder(TreeNode node)
        {
            if(node!=null)
            {
                inOrder(node.getleft());
                System.out.println(node.getdata()+" ");
                inOrder(node.getright());
            }
        }
        /*
         * 递归 后序遍历
         */
        public void postOrder(TreeNode node)
        {
            if(node!=null)
            {
                postOrder(node.getleft());
                postOrder(node.getright());
                System.out.println(node.getdata()+" ");
            }
        }

/*
         * 非递归 前序遍历
         */
        public void preOrdernorec(TreeNode root)
        {
            LinkedList<TreeNode> list= new LinkedList<TreeNode>();
            list.push(root);
            TreeNode cur=null;
            while(!list.isEmpty())
            {
                cur=list.poll();  //!!!
                System.out.print(cur.getdata()+" ");
                if(cur.getright()!=null)
                    list.push(cur.getright()); //!!!
                if(cur.getleft()!=null)
                    list.push(cur.getleft()); //这里使用push就是当做栈在使用，如果换成add就不是这样的输出
            }
    
        }

/*
         * 非递归 中序遍历
         */
        public void inordernocur(TreeNode root)
        {
            LinkedList<TreeNode> list= new LinkedList<TreeNode>();
            TreeNode cur=root;
            while(cur!=null||! list.isEmpty())
            {
                while(cur!=null)
                {
                    list.push(cur);
                    cur=cur.getleft();
                }
                if(!list.isEmpty())
                {
                    cur=list.pop();
                    System.out.println(cur.getdata()+" ");
                    cur=cur.getright();
                }
            }
        }

/*
         * 非递归 后序遍历  单栈法
         */
        public void postordernocur(TreeNode root)
        {
            Stack<TreeNode> stack= new Stack<TreeNode>();
            TreeNode cur=root;
            TreeNode node=root;
            while(cur!=null||!stack.isEmpty())
            {
                while(cur!=null)
                {
                    stack.push(cur);
                    cur=cur.getleft();  
                }
                if(stack.size()>0)
                {
                    TreeNode temp=stack.peek().getright();
    
                    if(temp==null||temp==node)//注意第二个条件
                    {
                        cur=stack.pop();
                        System.out.print(cur.getdata()+" ");
                        node=cur;
                        cur=null;
                    }
                    else
                        cur=temp;
    
                }
            }
        }

/*
         * 双栈法
         */
        public void postordernocur2(TreeNode root)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Stack<TreeNode> temp = new Stack<TreeNode>();
            TreeNode node=root;
            while(node!=null||stack.size()>0)
            {
                while(node!=null)
                {
                    temp.push(node);
                    stack.push(node);
                    node=node.getright();
                }
                if(stack.size()>0)
                {
                    node=stack.pop();
                    node=node.getleft();
                }
            }
            while(temp.size()>0)
            {
                node=temp.pop();
                System.out.print(node.getdata()+" ");
            }
        }

//节点类
          class TreeNode
        {
            private String data=null;//数据部分
            private TreeNode left;
            private TreeNode right;
            public TreeNode(String data,TreeNode left,TreeNode right)
            {
                this.data=data;
                this.left=left;
                this.right=right;
            }
            public String getdata()
            {
                return data;
            }
            public void setdata(String data)
            {
                this.data=data;
            }
            public TreeNode getleft()
            {
                return left;
            }
            public void setleft(TreeNode left)
            {
                this.left=left;
            }
            public TreeNode getright()
            {
                return right;
            }
            public void setright(TreeNode right)
            {
                this.right=right;
            }
        }

//主函数
    public static void main(String[] args) {
    
            Binaryorder b =new Binaryorder();
            //构造二叉树
            TreeNode l2=new TreeNode("E",null,null);
            TreeNode r2=new TreeNode("D",null,null);
            TreeNode l1=new TreeNode("B",null,r2);
            TreeNode r1=new TreeNode("C",l2,null);
            TreeNode root=new TreeNode("A",l1,r1);
    
            b.postOrder(root);
            System.out.println("----");
            b.postordernocur(root);
      }
    }

[http_blog.csdn.net_sheepmu_article_details_28941285]: http://blog.csdn.net/sheepmu/article/details/28941285
[http_blog.csdn.net_clam_clam_article_details_6845399]: http://blog.csdn.net/clam_clam/article/details/6845399