Java数据结构之二叉树遍历

- 日理万妓 2022-01-31 09:13 166阅读 0赞

二叉树遍历指沿着魔调搜索路径访问二叉树的结点，每个结点被访问的次数有且仅有一次。

# 先序遍历 #

先遍历根节点，再遍历左子树，最后遍历右子树，如图1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]

## 递归算法 ##

递归算法结构简单，易于实现，但是在时间上开销较大，运行效率较低。

/**
    	 * @param BiTreeNode root 根结点
    	 */
    	public void preOrder(BiTreeNode root) {
    		if (root == null) {
    			return;
    		}
    		System.out.print(root.data + "...");
    		preOrder(root.lchild);
    		preOrder(root.rchild);
    	}

## 非递归算法 ##

解决了递归算法中运行效率低下的问题  
可以使用临时遍历保存中间结果，用循环结构代替递归过程；或者利用栈保存中间结果。

### 核心思想 ###

从二叉树的根结点出发，沿着该结点的左子树向下搜索，每遇到一个结点先访问该结点，并将其右子树入栈。在左子树遍历完成后，将右子树出栈，在重复上述过程，直到栈为空。步骤如下：

1.  将二叉树的根结点入栈
2.  若栈非空，将结点从栈中弹出并访问
3.  依次访问当前访问结点的左孩子结点，并将当前结点的右孩子结点入栈
4.  重复步骤2和3，知道栈为空

### 代码实现 ###

import ch03.LinkStack;
    	
    	/**
    	 * @param BiTreeNode root 根结点
    	 */
    	public void preOrder2(BiTreeNode root) {
    		BiTreeNode p = root;
    		if (p != null) {
    			LinkStack s = new LinkStack();
    			try {
    				s.push(p);
    			} catch (Exception e) {
    				e.getMessage();
    			}
    			while (!s.isEmpty()) {
    				p = (BiTreeNode) s.pop();
    				System.out.print(p.data + "...");
    				while (p != null) {
    					if (p.lchild != null) {
    						System.out.print(p.lchild.data + "...");
    					}
    					if (p.rchild != null) {
    						try {
    							s.push(p.rchild);
    						} catch (Exception e) {
    							// TODO Auto-generated catch block
    							e.printStackTrace();
    						}
    					}
    					p = p.lchild;
    				}
    			}
    		}
    	}

# 中序遍历 #

先遍历左子树，再遍历根节点，最后遍历右子树，如图2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]

## 递归算法 ##

/**
    	 * @param BiTreeNode root 根结点
    	 */
    	public void inOrder(BiTreeNode root) {
    		if (root == null)
    			return;
    		inOrder(root.lchild);
    		System.out.print(root.data + "...");
    		inOrder(root.rchild);
    	}

## 非递归算法 ##

### 核心思想 ###

从二叉树的根结点出发，沿着该结点的左子树向下搜索，每遇到一个结点就使其入栈，直到结点的左孩子结点为空。再从栈顶弹出结点访问，然后采用相同的方法遍历结点的右子树，直到栈为空。步骤如下：

1.  将二叉树根节点入栈
2.  若栈非空，将栈顶节点的左孩子结点依次入栈，直到栈顶节点的左孩子结点为空
3.  将栈顶结点弹出并访问，并使栈顶结点的右孩子结点入栈
4.  重复（2）和（3）步骤

### 代码实现 ###

public void inOrder2(BiTreeNode root) {
    		BiTreeNode p = root;
    		if (p != null) {
    			LinkStack s = new LinkStack();
    			try {
    				s.push(p);// 根结点入栈
    			} catch (Exception e) {
    				e.getMessage();
    			}
    			while (!s.isEmpty()) {
    				while (p.lchild != null) {// 循环入栈，直到叶节点为止
    					try {
    						s.push(p.lchild);// 栈顶结点的左孩子结点入栈
    					} catch (Exception e) {
    						e.printStackTrace();
    					}
    					p = p.lchild;// 更新p指向
    				}
    				p = (BiTreeNode) s.pop();// 栈顶结点出栈
    				System.out.print(p.data + "...");
    				if (p.rchild != null) {
    					try {
    						s.push(p.rchild);
    					} catch (Exception e) {
    						e.printStackTrace();
    					}
    					p = p.rchild;
    				}
    			}
    		}
    	}

# 后序遍历 #

先遍历左子树，再遍历右子树，最后遍历根节点，如图3。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 2]

## 递归算法 ##

/**
    	 * @param BiTreeNode root 根结点
    	 */
    	public void postOrder(BiTreeNode root) {
    		if (root == null)
    			return;
    		inOrder(root.lchild);
    		inOrder(root.rchild);
    		System.out.print(root.data + "...");
    	}

## 非递归算法 ##

### 核心思想 ###

从二叉树的根结点出发，沿着该结点的左子树向下搜索，每遇到一个结点需要判断其是否为第一次经过，若是则使结点入栈，之后遍历该结点的左子树，完成后再遍历该结点的右子树，最后从栈顶弹出该结点并访问。后序遍历需要引入两个变量，一个为访问标记变量flag，用于标记栈顶结点是否被访问，若flag=true，则表明该结点已被访问，其左子树和右子树已经遍历完成，可继续弹出栈顶结点，否则需先遍历栈顶结点的右子树；一个为结点指针t，指向最后一个被访问的结点，查看栈顶结点的右孩子结点，证明此结点的右子树已已经比那里完成，栈顶结点可出栈并访问  
步骤如下：

1.  将二叉树根节点入栈，t赋值为空
2.  若栈非空，将栈顶节点的左孩子结点依次入栈，直到栈顶节点的左孩子结点为空
3.  若栈非空，查看栈顶结点的右孩子结点，若右孩子结点为空或者与p相等，则弹出栈顶结点并访问，同时使t指向该结点，并置flag为true；否则，将栈顶结点的右孩子结点入栈，并置flag为false
4.  若flag为true，重复步骤3；否则，重复步骤2和3，直到栈为空

### 代码实现 ###

public void postOrder2(BiTreeNode root) {
    		BiTreeNode p = root;
    		boolean flag = false;// 标记是否访问过根节点，若为false，表示没有访问过；若为true，表示已经访问过
    		if (p != null) {
    			LinkStack s = new LinkStack();
    			try {
    				s.push(p);// 根结点入栈
    			} catch (Exception e) {
    				e.getMessage();
    			}
    			while (!s.isEmpty()) {
    				while (p.lchild != null) {// 循环入栈，直到叶节点为止
    					try {
    						s.push(p.lchild);// 栈顶结点的左孩子结点入栈
    					} catch (Exception e) {
    						e.printStackTrace();
    					}
    					p = p.lchild;// 更新p指向
    				}
    				p = (BiTreeNode) s.pop();// 栈顶结点出栈
    				if (!flag) {
    					if (p == root) {
    						try {
    							s.push(p);
    						} catch (Exception e) {
    							e.printStackTrace();
    						}
    						flag = true;
    					} else
    						System.out.print(p.data + "...");
    				} else {
    					System.out.print(p.data + "...");
    					if (p == root)
    						return;
    				}
    				if (p.rchild != null) {
    					try {
    						s.push(p.rchild);
    					} catch (Exception e) {
    						// TODO Auto-generated catch block
    						e.printStackTrace();
    					}
    					p = p.rchild;
    				}
    			}
    		}
    	}

# 层次遍历 #

层次遍历为非递归算法，是从根结点出发，自上而下、从左到右依次遍历每层结点，可以利用队列的FIFO特点实现。先将根结点入队列，然后将队首结点出队并访问，都将其孩子结点依次入队。主要步骤：

1.  将根结点入队
2.  若队非空，取出队首结点并访问，将队首结点的孩子结点入队
3.  重复步骤2，知道队为空

## 代码实现 ##

import ch03.LinkQueue;
    
    	public void order() throws Exception {
    		BiTreeNode p = root;
    		while(p!=null) {
    			LinkQueue q = new LinkQueue();
    			q.offer(p);
    			while(!q.isEmpty()) {
    				p = (BiTreeNode) q.poll();
    				System.out.print(p.data+"...");
    				if(p.lchild!=null)
    					q.offer(p.lchild);
    				if(p.rchild!=null)
    					q.offer(p.rchild);
    			}
    			p = null;
    		}
    	}

# 应用 #

## 查找算法 ##

在先序遍历的过程中进行查找，步骤如下：

1.  若二叉树为空，则返回空值；否则将根结点与x进行比较，相等则返回
2.  若根结点与x不相等，则在左子树中搜寻，找到返回
3.  若在左子树中没找到，则在右子树中搜寻，找到返回，否则返回空值

### 代码实现 ###

/**二叉树查找算法——利用先序遍历进行查找
    	 * @param BiTreeNode root 根结点
    	 * @param Object x 待查询的结点*/
    	public  BiTreeNode searchNode(BiTreeNode t,Object x) {
    		if(t == null) {//树为空
    			return null;
    		}else {
    			if(x.equals(t.data)) {//与根节点比较
    				return t;
    			}else {
    				BiTreeNode lresult = searchNode(t.lchild,x);//在左子树比较
    				if(lresult == null) {
    					return searchNode(t.rchild,x);//在右子树比较
    				}else {
    					return lresult;
    				}
    			}
    		}
    	}

## 二叉树结点个数算法 ##

利用先序遍历，引入计数变量count=0，每访问一次根结点将其加1，步骤如下：

1.  count值初始化为0；
2.  若二叉树为空，返回count值；
3.  若二叉树非空，则count+1，分别统计左右子树的结点个数并加到count中

### 代码实现 ###

public int nodeCount(BiTreeNode t) {
    		int count = 0;
    		if (t != null) {
    			count += 1;
    			count += nodeCount(t.lchild);
    			count += nodeCount(t.rchild);
    		}
    		return count;
    	}

## 求二叉树深度 ##

二叉树的深度为左右子树深度的最大值加1，故可使用后序遍历算法解决。步骤如下：

1.  若二叉树为空，返回0；
2.  若二叉树非空，求左右子树深度；
3.  比较左右子树的深度，求最大值并+1

### 代码实现 ###

public int getDepth(BiTreeNode t) {
    		if(t == null) {
    			return 0;
    		}else {
    			int ldepth = getDepth(t.lchild);
    			int rdepth = getDepth(t.rchild);
    			return ldepth > rdepth ? ldepth+1:rdepth+1;
    		}
    	}

# 参考类 #

> [LinkStack][]  
> [BiTreeNode][]  
> [LinkQueue][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220131/bc2b784dbe2e42a5871d63d6d4904a2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220131/41e6e2dcf60c4097a654c6e39ff140bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220131/408c3f45bf314d308d729f999dab06a1.png
[LinkStack]: https://blog.csdn.net/weixin_44270248/article/details/89482106
[BiTreeNode]: https://blog.csdn.net/weixin_44270248/article/details/90257635
[LinkQueue]: https://blog.csdn.net/weixin_44270248/article/details/90229970