您的位置: 首页  >  文章  >  Java数据结构之二叉树遍历

Java数据结构之二叉树遍历

分类: 文章 • 2024-01-05 20:10:34

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

先序遍历

先遍历根节点，再遍历左子树，最后遍历右子树，如图1。
Java数据结构之二叉树遍历

递归算法

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

	/**
	 * @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。
Java数据结构之二叉树遍历

递归算法

	/**
	 * @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。
Java数据结构之二叉树遍历

递归算法

	/**
	 * @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

相关推荐