当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

数据结构与算法——二叉树遍历

发表于: 2012-11-02   作者:ciaos   来源:转载   浏览次数:
摘要: 首先定义一个二叉树结构如下   class BNode{ private String name; private BNode left,right; public String getName() { return name; } public void setName(String name) { this.name = name;

首先定义一个二叉树结构如下

 

class BNode{
	private String name;
	private BNode left,right;
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
	
	public BNode getLeft() {
		return left;
	}

	public void setLeft(BNode left) {
		this.left = left;
	}

	public BNode getRight() {
		return right;
	}

	public void setRight(BNode right) {
		this.right = right;
	}

	public BNode(String name)
	{
		this(name,null,null);
	}
	
	public BNode(String name,BNode left,BNode right){
		this.name = name;
		this.left = left;
		this.right = right;
	}
}

 插入一堆节点

 

BNode root;
		
root = new BNode("贾母");
root.setLeft(new BNode("贾政"));
root.setRight(new BNode("贾赦"));
root.getLeft().setLeft(new BNode("贾元春"));
root.getLeft().setRight(new BNode("贾宝玉"));
root.getRight().setLeft(new BNode("贾琏"));
root.getRight().setRight(new BNode("王熙凤"));

 下面是简单的前序遍历,中序遍历,后序遍历

 

	protected static void preOrder(BNode n)
	{
		if(n!=null){
			System.out.println(n.getName());
			preOrder(n.getLeft());
			preOrder(n.getRight());
		}
	}
	protected static void inOrder(BNode n)
	{
		if(n!=null){
			inOrder(n.getLeft());
			System.out.println(n.getName());
			inOrder(n.getRight());
		}
	}
	protected static void postOrder(BNode n)
	{
		if(n!=null){
			postOrder(n.getLeft());
			postOrder(n.getRight());
			System.out.println(n.getName());
		}
	}

 下面是广度优先遍历

 

	protected static void wideOrder(BNode n)
	{
		LinkedList l = new LinkedList();
		if(n!= null){
			l.push(n);
		}
		
		while(!l.isEmpty()){
			BNode t = (BNode)l.removeLast();
			System.out.println(t.getName());
			
			if(t.getLeft()!=null){
				l.push(t.getLeft());
			}
			if(t.getRight()!=null){
				l.push(t.getRight());
			}
		}
	}

1,首先将根节点放到队列中;

2,不断循环取队列尾,如果能取到节点,进行步骤3,否则退出循环;

3,依次将该节点的左右子节点插入队列头

下面是非递归先序遍历二叉树的一种实现,用到Stack这种数据结构,注意压栈时先右子节点后左子节点

 

	protected static void preOrder(BNode n)
	{
		Stack s = new Stack();
		
		if(n!=null){
			s.push(n);
		}		
		
		while(!s.isEmpty())
		{
			n = (BNode)s.pop();
			System.out.println(n.getName());
			if(n.getRight() != null){
				s.push(n.getRight());
			}
			if(n.getLeft()!=null){
				s.push(n.getLeft());
			}
		}
	}

数据结构与算法——二叉树遍历

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、二叉树的构造 二叉树的构造采用递归方式 //二叉链表方式存储的二叉树结构 typedef struct _tagBi
前一篇写了二叉树的先序遍历,本篇记录一下二叉树的中序遍历,主要是非递归形式的中序遍历。 由于距
非递归后序遍历二叉树相对于先序和中序稍微麻烦一点,网上看到好几种解法, 有一种解法很好,见(ht
据说这个笔试面试的时候非常easy考到,所以写到这里。 图示 代码实现 /** * 源代码名称:TreeIterat
非递归后序遍历二叉树相对于先序和中序稍微麻烦一点,网上看到好几种解法, 有一种解法很好,见(ht
1、二叉树的构造 二叉树的构造采用递归方式 //二叉链表方式存储的二叉树结构 typedef struct _tagBi
前一篇写了二叉树的先序遍历,本篇记录一下二叉树的中序遍历,主要是非递归形式的中序遍历。 由于距
本次的算法主要描述二叉树的遍历: using System; using System.Collections.Generic; namespace NE
1.二叉树,一种递归的数据结构,一棵非空的二叉树由根节点以及左右子树组成。 且看图: 在任一给定
javascript数据结构与算法-- 二叉树 树是计算机科学中经常用到的一种数据结构。树是一种非线性的数
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号