树的广度优先遍历和深度优先遍历（递归非递归 Java实现）

布满荆棘的人生 2022-04-10 06:19 223阅读 0赞

## [树的广度优先遍历和深度优先遍历（递归非递归、Java实现）][Java] ##

在编程生活中，我们总会遇见树性结构，这几天刚好需要对树形结构操作，就记录下自己的操作方式以及过程。现在假设有一颗这样树，（是不是二叉树都没关系，原理都是一样的）

![20181228102626232][]

## 1.广度优先遍历 ##

英文缩写为BFS即Breadth FirstSearch。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。

先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。

广度优先遍历树，需要用到队列（Queue）来存储节点对象,队列的特点就是先进先出。例如，上面这颗树的访问如下：

首先将A节点插入队列中，队列中有元素（A）;

将A节点弹出，同时将A节点的左、右节点依次插入队列，B在队首，C在队尾，（B，C），此时得到A节点；

继续弹出队首元素，即弹出B，并将B的左、右节点插入队列，C在队首，E在队尾（C,D，E），此时得到B节点；

继续弹出，即弹出C，并将C节点的左、中、右节点依次插入队列，（D,E,F,G,H），此时得到C节点；

将D弹出，此时D没有子节点，队列中元素为（E,F,G,H），得到D节点；

。。。以此类推。。

代码：这里以二叉树为例，遍历所有节点的值

![复制代码][2018122814112877]

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> lists=new ArrayList<Integer>();
            if(root==null)
                return lists;
            Queue<TreeNode> queue=new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tree=queue.poll();
                if(tree.left!=null)
                    queue.offer(tree.left);
                if(tree.right!=null)
                    queue.offer(tree.right);
                lists.add(tree.val);
            }
            return lists;
        }
    }

![复制代码][2018122814112877]

**2、深度优先**

英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个[节点][Link 1]只能访问一次。对于上面的例子来说深度优先遍历的结果就是：A,B,D,E,I,C,F,G,H.(假设先走子节点的的左侧)。

深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。整个遍历过程如下：

先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。

首先将A节点压入栈中，stack（A）;

将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)；

将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）；

将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）；

将E节点弹出，同时将E的子节点I压入，stack（I,C）；

...依次往下，最终遍历完成。

代码：也是以二叉树为例。非递归

![复制代码][2018122814112877]

/**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> lists=new ArrayList<Integer>();
            if(root==null)
                return lists;
            Stack<TreeNode> stack=new Stack<TreeNode>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode tree=stack.pop();
    　　　　　　//先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
                if(tree.right!=null)
                    stack.push(tree.right);
                if(tree.left!=null)
                    stack.push(tree.left);
                lists.add(tree.val);
            }
            return lists;
        }
    }

![复制代码][2018122814112877]

深度优先的递归实现：

![复制代码][2018122814112877]

public void depthOrderTraversalWithRecursive()  
        {  
            depthTraversal(root);  
        }  
          
        private void depthTraversal(TreeNode tn)  
        {  
            if (tn!=null)   
            {  
                System.out.print(tn.value+"  ");  
                depthTraversal(tn.left);  
                depthTraversal(tn.right);  
            }         
        }

![复制代码][2018122814112877]

本文大量引用自：http://www.cnblogs.com/toSeeMyDream/p/5816682.html

分类: [java][],[数据结构与算法][Link 2]

标签: [算法][Link 3], [java][java 1]

好文要顶 关注我 收藏该文 ![20181228141128422][] ![20181228141128474][]

[![20181228102626279][]][20181228102626279 1]

[夜的第八章][20181228102626279 1]  
[关注 - 6][- 6]  
[粉丝 - 4][- 4]

\+加关注

[« ][Link 4]上一篇：[设计模式之组合模式][Link 4]  
[» ][Link 5]下一篇：[设计模式之策略模式][Link 5]

posted on 2017-10-31 21:36 [夜的第八章][Link 6] 阅读(11592) 评论(1) [编辑][Link 7] [收藏][Link 8]

[https://www.cnblogs.com/xiaolovewei/p/7763867.html][Java]

# [邱勇Aaron][Aaron] #

## Sharing ##

*  [博客园][Link 9]
 *  [首页][Aaron]
 *  [新随笔][Link 10]
 *   
 *  [管理][Link 11]
 *

随笔- 59  文章- 0  评论- 46

# [二叉树遍历-JAVA实现][-JAVA] #

**二叉树遍历分为前序、中序、后序递归和非递归遍历、还有层序遍历。**

![复制代码][2018122814112877]

1 //二叉树节点
     2 public class BinaryTreeNode {
     3     private int data;
     4     private BinaryTreeNode left;
     5     private BinaryTreeNode right;
     6     
     7     public BinaryTreeNode() {}
     8 
     9     public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
    10         super();
    11         this.data = data;
    12         this.left = left;
    13         this.right = right;
    14     }
    15 
    16     public int getData() {
    17         return data;
    18     }
    19 
    20     public void setData(int data) {
    21         this.data = data;
    22     }
    23 
    24     public BinaryTreeNode getLeft() {
    25         return left;
    26     }
    27 
    28     public void setLeft(BinaryTreeNode left) {
    29         this.left = left;
    30     }
    31 
    32     public BinaryTreeNode getRight() {
    33         return right;
    34     }
    35 
    36     public void setRight(BinaryTreeNode right) {
    37         this.right = right;
    38     }
    39 }

![复制代码][2018122814112877]

前序递归遍历算法：访问根结点-->递归遍历根结点的左子树-->递归遍历根结点的右子树

中序递归遍历算法：递归遍历根结点的左子树-->访问根结点-->递归遍历根结点的右子树

后序递归遍历算法：递归遍历根结点的左子树-->递归遍历根结点的右子树-->访问根结点

![复制代码][2018122814112877]

1 import com.ccut.aaron.stack.LinkedStack;
      2 
      3 public class BinaryTree {
      4     //前序遍历递归的方式
      5     public void preOrder(BinaryTreeNode root){
      6         if(null!=root){
      7             System.out.print(root.getData()+"\t");
      8             preOrder(root.getLeft());
      9             preOrder(root.getRight());
     10         }
     11     }
     12     
     13     //前序遍历非递归的方式
     14     public void preOrderNonRecursive(BinaryTreeNode root){
     15         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
     16         while(true){
     17             while(root!=null){
     18                 System.out.print(root.getData()+"\t");
     19                 stack.push(root);
     20                 root=root.getLeft();
     21             }
     22             if(stack.isEmpty()) break;
     23             root=stack.pop();
     24             root=root.getRight();
     25         }
     26     }
     27     
     28     //中序遍历采用递归的方式
     29     public void inOrder(BinaryTreeNode root){
     30         if(null!=root){
     31             inOrder(root.getLeft());
     32             System.out.print(root.getData()+"\t");
     33             inOrder(root.getRight());
     34         }
     35     }
     36     
     37     //中序遍历采用非递归的方式
     38     public void inOrderNonRecursive(BinaryTreeNode root){
     39         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
     40         while(true){
     41             while(root!=null){
     42                 stack.push(root);
     43                 root=root.getLeft();
     44             }
     45             if(stack.isEmpty())break;
     46             root=stack.pop();
     47             System.out.print(root.getData()+"\t");
     48             root=root.getRight();
     49         }
     50     }
     51     
     52     //后序遍历采用递归的方式
     53     public void postOrder(BinaryTreeNode root){
     54         if(root!=null){
     55             postOrder(root.getLeft());
     56             postOrder(root.getRight());
     57             System.out.print(root.getData()+"\t");
     58         }
     59     }
     60     
     61     //后序遍历采用非递归的方式
     62     public void postOrderNonRecursive(BinaryTreeNode root){
     63         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
     64         while(true){
     65             if(root!=null){
     66                 stack.push(root);
     67                 root=root.getLeft();
     68             }else{
     69                 if(stack.isEmpty()) return;
     70                 
     71                 if(null==stack.lastElement().getRight()){
     72                     root=stack.pop();
     73                     System.out.print(root.getData()+"\t");
     74                     while(root==stack.lastElement().getRight()){
     75                         System.out.print(stack.lastElement().getData()+"\t");
     76                         root=stack.pop();
     77                         if(stack.isEmpty()){
     78                             break;
     79                         }
     80                     }
     81                 }
     82                 
     83                 if(!stack.isEmpty())
     84                     root=stack.lastElement().getRight();
     85                 else
     86                     root=null;
     87             }
     88         }
     89     }
     90 
     91     //层序遍历
     92     public void levelOrder(BinaryTreeNode root){
     93         BinaryTreeNode temp;
     94         Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
     95         queue.offer(root);
     96         while(!queue.isEmpty()){
     97             temp=queue.poll();
     98             System.out.print(temp.getData()+"\t");
     99             if(null!=temp.getLeft()) 
    100                 queue.offer(temp.getLeft());
    101             if(null!=temp.getRight()){
    102                 queue.offer(temp.getRight());
    103             }
    104         }
    105     }
    106     
    107     public static void main(String[] args) {
    108         BinaryTreeNode node10=new BinaryTreeNode(10,null,null);
    109         BinaryTreeNode node8=new BinaryTreeNode(8,null,null);
    110         BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);
    111         BinaryTreeNode node4=new BinaryTreeNode(4,null,null);
    112         BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);
    113         BinaryTreeNode node6=new BinaryTreeNode(6,null,null);
    114         BinaryTreeNode node7=new BinaryTreeNode(7,null,null);
    115         BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);
    116         BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);
    117         BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);
    118         
    119         BinaryTree tree=new BinaryTree();
    120         //采用递归的方式进行遍历
    121         System.out.println("-----前序遍历------");
    122         tree.preOrder(node1);
    123         System.out.println();
    124         //采用非递归的方式遍历
    125         tree.preOrderNonRecursive(node1);
    126         System.out.println();
    127 
    128         
    129         //采用递归的方式进行遍历
    130         System.out.println("-----中序遍历------");
    131         tree.inOrder(node1);
    132         System.out.println();
    133         //采用非递归的方式遍历
    134         tree.inOrderNonRecursive(node1);
    135         System.out.println();
    136         
    137         //采用递归的方式进行遍历
    138         System.out.println("-----后序遍历------");
    139         tree.postOrder(node1);
    140         System.out.println();
    141         //采用非递归的方式遍历
    142         tree.postOrderNonRecursive(node1);
    143         System.out.println();
    144         
    145         //采用递归的方式进行遍历
    146         System.out.println("-----层序遍历------");
    147         tree.levelOrder(node1);
    148         System.out.println();
    149     }
    150 }

![复制代码][2018122814112877]

一直特立独行的二本僧，书写属于他的天空

分类: [数据结构][Link 12]

好文要顶 关注我 收藏该文 ![20181228141128422][] ![20181228141128474][]

[![20181228141128779][]][20181228141128779 1]

[邱勇Aries][20181228141128779 1]  
[关注 - 13][- 13]  
[粉丝 - 43][- 43]

\+加关注

[« ][Link 13]上一篇：[Java容器-引入Guava类库][Link 13]  
[» ][Link 14]下一篇：[Java实现-每天三道剑指Offre(2-4)][Link 14]

posted @ 2017-04-06 21:16 [邱勇Aries][Aaron] 阅读(6804) 评论(0) [编辑][Link 15] [收藏][Link 16]

[https://www.cnblogs.com/qiuyong/p/6675492.html][-JAVA]

[Java]: https://www.cnblogs.com/xiaolovewei/p/7763867.html
[20181228102626232]: /images/20220402/aac4babaeb7241df99e1e4ca21c1991a.png
[2018122814112877]: /images/20220402/a28d64397c8c4d268ffdc71563399935.png
[Link 1]: http://baike.baidu.com/view/47398.htm
[java]: https://www.cnblogs.com/xiaolovewei/category/1105844.html
[Link 2]: https://www.cnblogs.com/xiaolovewei/category/1105846.html
[Link 3]: https://www.cnblogs.com/xiaolovewei/tag/%E7%AE%97%E6%B3%95/
[java 1]: https://www.cnblogs.com/xiaolovewei/tag/java/
[20181228141128422]: https://img-blog.csdnimg.cn/20181228141128422
[20181228141128474]: /images/20220402/d66119d0b5e749f7860942a49a61ce04.png
[20181228102626279]: /images/20220402/e74ab513355344199ec3e00fc2a4547b.png
[20181228102626279 1]: http://home.cnblogs.com/u/xiaolovewei/
[- 6]: http://home.cnblogs.com/u/xiaolovewei/followees
[- 4]: http://home.cnblogs.com/u/xiaolovewei/followers
[Link 4]: https://www.cnblogs.com/xiaolovewei/p/7760518.html
[Link 5]: https://www.cnblogs.com/xiaolovewei/p/7768579.html
[Link 6]: https://www.cnblogs.com/xiaolovewei/
[Link 7]: https://i.cnblogs.com/EditPosts.aspx?postid=7763867
[Link 8]: https://www.cnblogs.com/xiaolovewei/p/7763867.html#
[Aaron]: https://www.cnblogs.com/qiuyong/
[Link 9]: https://www.cnblogs.com/
[Link 10]: https://i.cnblogs.com/EditPosts.aspx?opt=1
[Link 11]: https://i.cnblogs.com/
[-JAVA]: https://www.cnblogs.com/qiuyong/p/6675492.html
[Link 12]: https://www.cnblogs.com/qiuyong/category/979708.html
[20181228141128779]: /images/20220402/a28d64397c8c4d268ffdc71563399935.png9
[20181228141128779 1]: http://home.cnblogs.com/u/qiuyong/
[- 13]: http://home.cnblogs.com/u/qiuyong/followees
[- 43]: http://home.cnblogs.com/u/qiuyong/followers
[Link 13]: https://www.cnblogs.com/qiuyong/p/6575770.html
[Link 14]: https://www.cnblogs.com/qiuyong/p/6675531.html
[Link 15]: https://i.cnblogs.com/EditPosts.aspx?postid=6675492
[Link 16]: https://www.cnblogs.com/qiuyong/p/6675492.html#