二叉树的遍历

冷不防 2022-02-28 06:18 113阅读 0赞

二叉树的遍历分为：

1.  深度优先遍历
2.  广度优先遍历

其中，深度优先遍历又分为：

1.  前序遍历(根–>左子–>右子)
2.  中序遍历(左子–>根–>右子)
3.  后续遍历(左子–>右子–>根)

下面分别介绍这2类，4种遍历方式：

节点类（ListNode 、TreeNode）

class ListNode { 
    	
    	 int val;
         ListNode left;
         ListNode right;
         ListNode(int x) {  val = x; }
     }

**前序遍历**

/** * 前序遍历，递归法 * @param root */
    	public void preOrderTraverse(TreeNode root) { 
    		if(root!=null) { 
    			System.out.println(root.val);
    			preOrderTraverse(root.left);
    			preOrderTraverse(root.right);
    		}
    	}
    	
    	/** * 前序遍历，非递归法 * @param root */
    	public void preOrderTraverse(TreeNode root) { 
    		TreeNode pNode = root;
    		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    		while (pNode != null || !stack.isEmpty()) { 
    			if(pNode != null) { 
    				System.out.print(pNode.val+",");
    				stack.push(pNode);
    				pNode = pNode.left;
    			}else { 
    				TreeNode node = stack.pop();
    				pNode = node.right; 
    			}
    		}
    	}

**中序遍历**

/** * 中序遍历，递归法 * @param root */
    	public void preOrderTraverse(TreeNode root) { 
    		if(root!=null) { 
    			preOrderTraverse(root.left);
    			System.out.print(root.val);
    			preOrderTraverse(root.right);
    		}
    	}
    	
    	/** * 中序遍历，非递归法 * @param root */
    	public void preOrderTraverse(TreeNode root) { 
    		TreeNode pNode = root;
    		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    		while (pNode != null || !stack.isEmpty()) { 
    			if(pNode != null) { 
    				stack.push(pNode);
    				pNode = pNode.left;
    			}else { 
    				TreeNode node = stack.pop();
    				System.out.print(node.val+",");
    				pNode = node.right; 
    			}
    		}
    	}

**后序遍历**  
[https://www.cnblogs.com/llguanli/p/7363657.html][https_www.cnblogs.com_llguanli_p_7363657.html]  
二叉树的后序遍历比较复杂，因为需要先顺序访问完节点的左子树、右子树，才能去访问此节点。流程控制较复杂。  
思路1：  
对于任意节点，先入栈，然后沿左子树一直往下搜索。直到没有左子树，此时节点出栈但不访问，因为右子树还未访问。  
**记录此节点的左子树已访问完毕**，然后用同样的规则对右子树遍历，直到遍历完成。  
此时节点再次出栈，并访问。

/** * 后序遍历，递归法 * @param root */
    	public void preOrderTraverse(TreeNode root) { 
    		if(root!=null) { 
    			preOrderTraverse(root.left);
    			preOrderTraverse(root.right);
    			System.out.print(root.val);
    		}
    	}
    
    
    /** * 后序遍历非递归实现 * @param root */
    	public void postOrderTraverse(ListNode root) { 
    		LinkedList<ListNode> stack1 = new LinkedList<ListNode>();
    		//辅助栈，用来判断子节点返回父节点时处于左节点还是右节点
    		LinkedList<Integer> stack2 = new LinkedList<Integer>();
    		int left = 1; //辅助栈里标识左子节点
    		int right= 2; //辅助栈里标识右子节点
    		ListNode node = root;
    		while (node!=null || !stack1.isEmpty()) { 
    			while(node !=null) { 
    				//将节点压入栈1，并在栈2将节点标记为左节点
    				stack1.push(node);
    				stack2.push(left);
    				node = node.left;
    			}
    			while(!stack1.isEmpty() && stack2.peek() == right) { 
    				//如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
    				ListNode cur = stack1.pop();
    				stack2.pop();
    				System.out.print(cur.val);
    			}
    			if(!stack1.isEmpty() && stack2.peek() == left) { 
    				//如果是从左子节点返回父节点，则将标记改为右子节点
    				stack2.pop();
    				stack2.push(right);
    				node = stack1.peek().right;
    			}
    		}
    	}

**广度优先遍历**

/** * 广度优先遍历 * @param root */
    	public void levelTraverse(ListNode root) { 
    		//使用队列结构
    		LinkedList<ListNode> queue = new LinkedList<ListNode>();
    		queue.offer(root);  //入队列
    		while (!queue.isEmpty()) { 
    			ListNode cur = queue.poll(); //出队列
    			System.out.println(cur.val);
    			if(cur.left != null) { 
    				queue.offer(cur.left);
    			}
    			if(cur.right != null) { 
    				queue.offer(cur.right);
    			}
    		}
    	}

求二叉树的深度

public int height()                                    //返回二叉树的高度
        { 
            return height(root);
        }
        public int height(BinaryNode<T> p) //返回以p结点为根的子树高度，后根次序遍历
        { 
            if (p==null)
                return 0;
            int lh = height(p.left);                           //返回左子树的高度
            int rh = height(p.right);                          //返回右子树的高度
            return (lh>=rh) ? lh+1 : rh+1;                //当前子树高度为较高子树的高度加1
        }

二叉树节点数

public int size()                                      //返回二叉树的结点数
        { 
            return size(root);
        }
        public int size(BinaryNode<T> p)                       //返回以p结点为根的子树的结点数
        { 
            if (p==null)
                return 0;
            return 1+size(p.left)+size(p.right);            //左右树分开求
        }

[https_www.cnblogs.com_llguanli_p_7363657.html]: https://www.cnblogs.com/llguanli/p/7363657.html