i3geek.com
闫庚哲的个人博客

二叉树实现广度遍历和递归与非递归的深度(前中后序)遍历

二叉树的遍历:

(1)深度优先遍历:前序、中序、后序

(2)广度优先遍历

即,前中后序是深度优先遍历的一种而已,广度优先只有非递归方法。

二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。

一、广度优先遍历

  1. 初始化一个队列,并把根结点入列队;
  2. 当队列为非空时,循环执行步骤3到步骤5,否则执行6;
  3. 出队列取得一个结点,访问该结点;
  4. 若该结点的左子树为非空,则将该结点的左子树入队列;
  5. 若该结点的右子树为非空,则将该结点的右子树入队列;
  6. 结束
	/**
	 * 利用队列的广度遍历
	 * @param root
	 */
	public static void preListIterator(tree root)
	{
		ArrayList<tree> list = new ArrayList<tree>();
		if(root==null)
			return ;
		list.add(root);
		while(!list.isEmpty())
		{
			tree temp = list.get(0);
			list.remove(0);
			System.out.print(temp.value +" ");
			if(temp.lchild!=null)
				list.add(temp.lchild);
			if(temp.rchild!=null)
				list.add(temp.rchild);
		}
	}

 二、深度优先遍历

(1)递归实现:

前序:访问根节点=>左子树=>右子树

	/**
	 * 递归的前序遍历
	 * @param root
	 */
	public static void preIterator(tree root)
	{
		if(root!=null)
		{
			System.out.print(root.value +" ");
			preIterator(root.lchild);
			preIterator(root.rchild);
		}
	}

中序:左子树=>访问根节点=>右子树

	/**
	 * 递归的中序遍历
	 * @param root
	 */
	public static void inIterator(tree root)
	{
		if(root!=null)
		{
			inIterator(root.lchild);
			System.out.print(root.value +" ");
			inIterator(root.rchild);
		}
	}

后序:左子树=>右子树=>访问根节点

	/**
	 * 递归的后序遍历
	 * @param root
	 */
	public static void postIterator(tree root)
	{
		if(root!=null)
		{
			postIterator(root.lchild);
			postIterator(root.rchild);
			System.out.print(root.value +" ");
		}
	}

(2)非递归实现

前序:

	/**
	 * 非递归的深度前序遍历
	 * @param root
	 */
	public static void preStackIterator(tree root)
	{
		Stack<tree> stack = new Stack<tree>();
		if(root==null)
			return ;
		stack.push(root);
		while(!stack.isEmpty())
		{
			tree temp = stack.pop();
			System.out.print(temp.value +" ");
			if(temp.rchild!=null)
				stack.push(temp.rchild);
			if(temp.lchild!=null)
				stack.push(temp.lchild);
		}
	}

中序:

	/**
	 * 非递归的深度中序遍历
	 * @param root
	 */
	public static void inStackIterator(tree root)
	{
		Stack<tree> stack = new Stack<tree>();
		if(root==null)
			return ;
		tree temp = root;
		while(!stack.isEmpty() || temp!=null)
		{
			while(temp!=null)
			{
				stack.push(temp);
				temp = temp.lchild;
			}
			temp = stack.pop();
			System.out.print(temp.value +" ");
			if(temp.rchild!=null)
				temp = temp.rchild;
			else
				temp = null;
		}
	}

后序:

	/**
	 * 非递归的深度后序遍历
	 * 
	 * @param root
	 */
	public static void postStackIterator(tree root) {
		Stack<tree> stack = new Stack<tree>();
		if (root == null)
			return;
		tree temp = root;
		stack.push(temp);
		tree ptr = root, pre = null;
		while (!stack.isEmpty()) {
			ptr = stack.peek();
			if (pre != ptr.rchild && pre != ptr.lchild) {
				if (ptr.rchild != null)
					stack.push(ptr.rchild);
				if (ptr.lchild != null)
					stack.push(ptr.lchild);
			}
			if (ptr.lchild == null && ptr.rchild == null || pre == ptr.lchild
					|| pre == ptr.rchild) {
				System.out.print(ptr.value + " ");
				stack.pop();
			}
			pre = ptr;
		}
	}
赞(0)
未经允许不得转载:爱上极客 » 二叉树实现广度遍历和递归与非递归的深度(前中后序)遍历
分享到: 更多 (0)

评论 7

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    博主的博客很不错,看得出来很用心呀,期待继续更新!!!

    威客圈子4年前 (2015-04-23)回复
    • 谢谢!

      yan4年前 (2015-04-23)回复
  2. #2

    博主的程序不错啊

    驻马店婚纱摄影4年前 (2015-05-07)回复
  3. #3

    不错

    一零网赚4年前 (2015-05-15)回复
  4. #4

    不错支持

    免费广告论坛4年前 (2015-06-04)回复
  5. #5

    罗衣著破前香在,旧意谁教攻。
    一春离恨懒调弦,犹有两行闲泪、宝筝前。

    互传电商网4年前 (2015-07-18)回复
  6. #6

    红叶黄花秋意晚,千里念行客。
    飞云过尽,归鸿无信,何处寄书得?

    互传电商网4年前 (2015-07-18)回复