树的深度优先和广度优先

叁歲伎倆 2021-09-21 00:56 315阅读 0赞

1.深度优先算法----采用栈(非递归)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5MTA1NQ_size_16_color_FFFFFF_t_70]

/** * 深度优先遍历，相当于先根遍历 * 采用非递归实现 * 需要辅助数据结构：栈 */
            public void depthOrderTraversal(){ 
                if(root==null){ 
                    System.out.println("empty tree");
                    return;
                }       
                Stack<TreeNode> stack = new Stack();   //也可以用栈实现
                stack.push(root);       
                while(stack.isEmpty()==false){ 
                    TreeNode node=stack.pop();
                    System.out.print(node.value+" ");
                    if(node.right!=null){ 
                        stack.push(node.right);
                    }
                    if(node.left!=null){ 
                        stack.push(node.left);
                    }           
                }
                System.out.print("\n");
            }

深度优先—递归

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

2.广度优先算法—采用队列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5MTA1NQ_size_16_color_FFFFFF_t_70 1]

/** * 广度优先遍历 * 采用非递归实现 * 需要辅助数据结构：队列 */
            public void levelOrderTraversal(){ 
                if(root==null){ 
                    System.out.println("empty tree");
                    return;
                }
                ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
                queue.add(root);
                while(queue.isEmpty()==false){ 
                    TreeNode node=queue.remove();
                    System.out.print(node.value+" ");
                    if(node.left!=null){ 
                        queue.add(node.left);
                    }
                    if(node.right!=null){ 
                        queue.add(node.right);
                    }
                }
                System.out.print("\n");
            }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5MTA1NQ_size_16_color_FFFFFF_t_70]: /images/20210920/d029337a677e406fa1b99d15dad9241c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5MTA1NQ_size_16_color_FFFFFF_t_70 1]: /images/20210920/95cb00b534c04a5faff87c48390c904d.png