码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Java中树的遍历——菜鸟学数据结构(五)

上次分享了二叉树的数据结构,这次楠哥专门拿出一节来分析二叉树的遍历(Traverse)问题。事实上,二叉树的搜索(Search)问题和遍历问题非常相似,不同的是遍历问题会访问树的每一个节点,而搜索问题一旦找到了所需要的结点就停止操作了。搜索问题楠哥会在后续算法相关的文章当中详解,本次主要分析最常用的两种遍历方法。(楠哥计算机学习网www.liubonan.com)

深度优先遍历(Depth First)是指对于一颗树,首先访问其左节点,后访问右节点,再访问其根节点;对于节点本身是子树的情况,则按此规则继续深入,直到叶节点位置。这种方法有两种实现的思路。第一种是使用递归(Recursion)的方式,即如果该节点不是叶节点则访问其左子树、右子树,在访问节点本身;另外一种思路是递推(Iteration)的方式,这里需要定义一个栈(Stack),即LIFO队列,如果栈顶结点不是叶节点,就将其左右子树压入栈;循环的从栈顶取结点,再按此规则进行处理。栈的实现Java已经给出,当然也可以使用自定义的类型,具体方式详见《Java中栈的实现》。

广度优先遍历(Breadth First)是指对一棵树,首先访问第一层的结点,在访问第二层的结点,依次类推。这里我们需要用一个FIFO队列(Queue)来实现:将每一个结点的所有子结点加入到队列中,再从队列中选取队首元素出队,依次规则进行循环直到所有结点全部出队。队列的实现Java同样也有现成的类,如果想自定义该数据结构,可以参考《Java中队列的实现》。(楠哥计算机学习网www.liubonan.com)

下面的代码实现了两种深度优先遍历方式和一种广度优先遍历方式,因为树的具体代码已经在上次文章中给出,本文只列出遍历函数的代码。全部代码详见《Java中的二叉树》。(楠哥计算机学习网www.liubonan.com)

public void dfs_re(Node current)
	{
		if((current.getLeft() == null)&&(current.getRight() == null))
			System.out.print(current.getData() + " ");
		else
		{
			if(current.getLeft() != null)
				dfs_re(current.getLeft());

			if(current.getRight() != null)
				dfs_re(current.getRight());

			System.out.print(current.getData() + " ");
		}
	}

	public void bfs()
	{
		Queue q = new LinkedList();

		q.add(root);

		while(!q.isEmpty())
		{
			Node temp = q.remove();
			if(temp.getLeft()!=null)
				q.add(temp.getLeft());
			if(temp.getRight()!=null)
				q.add(temp.getRight());
			System.out.print(temp.getData() + " ");
		}

	}

	public void dfs_it()
	{
		Stack s = new Stack();

		s.push(root);

		while(!s.isEmpty())
		{
			Node temp = s.pop();

			if(((temp.getLeft() == null)&&(temp.getRight() == null)) || (temp.isVisited()))
				System.out.print(temp.getData() + " ");
			else
			{

				if(temp.getRight() == null)
				{
					Node left = temp.getLeft();
					temp.setVisited(true);

					s.push(temp);
					s.push(left);

				}
				else
				{
					if(temp.getLeft() == null)
					{
						Node right = temp.getRight();
						temp.setVisited(true);

						s.push(temp);
						s.push(right);
					}
					else
					{
						Node left = temp.getLeft();
						Node right = temp.getRight();
						temp.setVisited(true);
						s.push(temp);
						s.push(right);
						s.push(left);
					}
				}
			}
		}

	}
最近的文章

楠哥拟提供免费的Linux练习环境

长久以来,广大国内CS专业的学生都没有一个Unix/Linux编程练习环境,以至于很多学生竟然完全没有机会学习Makefile等技术。现在,楠哥打算抛砖引玉,逐步建立一个免费的Linux平台练习环境。…

Technical继续阅读
更早的文章

Java中的二叉树——菜鸟学数据结构(四)

今天楠哥和大家一起来讨论一下Java当中二叉树的实现。 树是一种高级数据结构,但是却十分常用,稍微复杂的问题就会涉及到树的应用。本文先就树(Tree)的最简单形式——二叉树进行一些简单的分析。顾名思义…

Technical, Career继续阅读
comments powered by Disqus