码农乌托邦

楠哥小站

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


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

今天楠哥和大家一起来讨论一下Java当中二叉树的实现。 树是一种高级数据结构,但是却十分常用,稍微复杂的问题就会涉及到树的应用。本文先就树(Tree)的最简单形式——二叉树进行一些简单的分析。顾名思义,二叉树(Binary Tree)即为每个节点至多只有两个子结点(Child Node)的树,因为子结点的个数具有一个固定的范围,所以就可以用顺序存储的办法进行存储。第i个结点的左右子结点分别储存于2i和2i+1的位置。顺序存储的实现可参见本系列文章之《Java链表——菜鸟学数据结构(一)》(http://www.liubonan.com/articles/349.html)。(楠哥计算机学习网www.liubonan.com)

但是由于并不是每个二叉树结点都一定有子结点,这样就会浪费很大的存储空间。为此,我们可以使用非顺序存储的方式,本文也就这种方式进行详细的介绍。使用非顺序存储所使用的结点可以使用三种设计方式,分别是单指向、双指向和三指向式。单指向式的结点中有一个指向其父节点的属性,但是这样的方式会造成从根到叶节点无法顺利的进行遍历。另外一种方法是双指向式,每个节点指向其左右子结点(没有则为NULL),本文基于这种设计实现。另外一种三指向式包含了前两种的特点,但是只有特定问题才使用这种设计,所以在此不作阐述。(楠哥计算机学习网www.liubonan.com)

下面的代码当中实现了一个二叉排序树,每个节点的左节点或左子树的值都小于其本身,而其右节点或右子树的值都大于其本身,该算法将在后面详解,此例的重点在于描述二叉树的数据结构。下文中,将详细介绍该树的各种遍历方法。(楠哥计算机学习网www.liubonan.com)

package ds;
//楠哥计算机学习网www.liubonan.com
public class Node {

	private int data;
	private int depth;
	private boolean visited;

	private Node left, right;

	public Node(int data)
	{
		this.setData(data);
		this.setLeft(null);
		this.setRight(null);
		this.setVisited(false);
	}

	public Node getLeft() {
		return left;
	}

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

	public Node getRight() {
		return right;
	}

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

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public int getDepth() {
		return depth;
	}

	public void setDepth(int depth) {
		this.depth = depth;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}
}
package ds;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
//楠哥计算机学习网www.liubonan.com
public class BinaryTree {

	private Node root;

	public BinaryTree(int data)
	{
		Node temp = new Node(data);
		setRoot(temp);
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}
	//楠哥计算机学习网www.liubonan.com
	public void add_it(int data)
	{
		Node current = root;
		Node prev=null;
		boolean childflag = false;

		while(current != null)
		{
			prev = current;

			if(data  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() + " ");
		}

	}
	//楠哥计算机学习网www.liubonan.com
	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);
					}
				}
			}
		}

	}

}
package ds;
//楠哥计算机学习网www.liubonan.com
public class Tester {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BinaryTree t = new BinaryTree(5);

		t.add_re(6,t.getRoot());
		t.add_re(7,t.getRoot());
		t.add_re(2,t.getRoot());
		t.add_re(3,t.getRoot());
		t.add_re(1,t.getRoot());

		t.add_it(8);
		t.add_it(10);
		t.add_it(4);
		t.add_it(9);

		t.dfs_re(t.getRoot());

		System.out.println();
		t.dfs_it();

		System.out.println();
		t.bfs();
	}

}
最近的文章

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

上次分享了二叉树的数据结构,这次楠哥专门拿出一节来分析二叉树的遍历(Traverse)问题。事实上,二叉树的搜索(Search)问题和遍历问题非常相似,不同的是遍历问题会访问树的每一个节点,而搜索问题…

Technical, Career继续阅读
更早的文章

Java中队列的实现——菜鸟学数据结构(三)

上次文章说到Java中栈的实现,这次楠哥和大家一起学习Java中队列的实现。事实上,队列(Queue)这种数据结构其实和linklist十分的相似,只是在linklist当中可以直接的获取每一个结点的…

Technical, Career继续阅读
comments powered by Disqus