将数组用树有序表示及树的三种遍历

一、树的基本结构

树，是可以表示任意含有层次结构的数据结构。每棵树只有一个根结点，根结点下可以有任意的子结点，子结点又可以有任意个子结点，如此反复，若子结点下无子结点的子结点，则此结点称为叶，但每个结点只有一个父结点。

一下主要讨论的是二叉树，二叉树即每个结点最多有两个子结点。除根结点与叶结点外每个结点有父结点、子结点。对于构建一个二叉树的结点类，我们可定义四个属性，分别是：结点的数据、父结点、左子结点、右子结点。

 

 

/**
 * 树的结点类
 * 
 * @author lenovo
 * 
 */
public class TreeNode {

	private Object obj; // 数据
	private TreeNode parent; // 父结点
	private TreeNode leftchild; // 左子结点
	private TreeNode rightchild; // 右子结点
	
	/**
	 * 重写构造方法
	 * @param obj
	 */
	public TreeNode(Object obj){
		this.obj=obj;
	}

	public Object getObj() {
		return obj;
	}

	public void setObj(Object obj) {
		this.obj = obj;
	}

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}

	public TreeNode getLeftchild() {
		return leftchild;
	}

	public void setLeftchild(TreeNode leftchild) {
		this.leftchild = leftchild;
	}

	public TreeNode getRightchild() {
		return rightchild;
	}

	public void setRightchild(TreeNode rightchild) {
		this.rightchild = rightchild;
	}
	
	
	

}

 

 

二、树的三种遍历方式

对于一棵树，一般有三种遍历的方法，即前序遍历、中序遍历、后序遍历。前序遍历即先遍历父结点，再遍历左子结点，再右子结点；中序遍历即先遍历左子结点，再遍历父结点，再遍历右子结点；后序遍历即先遍历左子结点，再遍历右子结点，再遍历父结点

遍历一个棵树是否，采用哪种方式，主要看是先递归，还是先打印。

 

　　 A　　

     /  \　

   B     C

　/     /  \ 

 D     E     F　

　    

     图　

 

（1） 中序序列（inorder traversal）　　

中序遍历二叉树时，对结点的访问次序为中序序列　　

【例】中序遍历上图所示的二叉树时，得到的中序序列为：　　

D B A E C F　　

（2） 先序序列（preorder traversal）　　

先序遍历二叉树时，对结点的访问次序为先序序列　　

【例】先序遍历上图所示的二叉树时，得到的先序序列为：　　

A B D C E F　　

（3） 后序序列（postorder traversal）　　

后序遍历二叉树时，对结点的访问次序为后序序列　　

【例】后序遍历上图所示的二叉树时，得到的后序序列为：　　

D B E F C A

 

 

 

/**
	 * 遍历树的方法（左根右、根左右、左右根）
	 * 
	 * @param root
	 *            ：树的根节点
	 */
	public void printTree(TreeNode root) {

		if (root != null) {
			// 前序（根左右）
			// Object obj = root.getObj();
			// System.out.println(obj);

			// 左子结点递归
			TreeNode leftTree = root.getLeftchild();
			printTree(leftTree);

			// 中序（左根右）
			Object obj = root.getObj();
			System.out.print(obj + "\t");

			// 右子结点
			TreeNode rightTree = root.getRightchild();
			printTree(rightTree);

			// 后序（左右根）
			// Object obj = root.getObj();
			// System.out.println(obj);

		}

	}

 

 

三、将数组用树表示，并实现有序的遍历输出（基于二叉搜索树的实现）

先定义一个根结点，从数组取小标为0的数据作为根结点（优化：将数组中的中值作为根结点）。每一次从数组中去一个数和根结点比较，若值小于根结点且子结点为null，则作为根结点的左子结点，若不为null，则对左子结点递归，若值大于或等于根结点且子结点为null，则作为根结点的右子结点，若不为null，则对右子结点递归。

 

 

/**
	 * 将数组转化为树的方法
	 * 
	 * @param array
	 * @return
	 */
	public TreeNode arraytoTree(int[] array) {

		if (array == null) {
			throw new RuntimeException("传入的数组为空");
		}

		TreeNode ptree = new TreeNode(array[0]);

		for (int i = 1; i < array.length; i++) {

			DatatoTree(array[i],ptree);

		}

		return ptree;
	}


/**
	 * 将数组中每个元素放入到树的方法 比根结点小的元素设为左子结点，比根结点大的元素设为右子结点
	 * 
	 * @param num
	 * @param tree
	 *            ：根结点
	 */
	public void DatatoTree(int num, TreeNode root) {

		// 如果值比根结点小的话，作为左子结点
		if (num < (Integer) root.getObj()) {

			if (root.getLeftchild() == null) { // 如果左子结点为null

				TreeNode ltree = new TreeNode(num);

				root.setLeftchild(ltree);
				ltree.setParent(root);
			} else { // 否则，左子结点递归

				DatatoTree(num, root.getLeftchild());
			}
			// 如果值不比根结点小的话，作为右子结点
		} else {

			if (root.getRightchild() == null) { // 如果右子结点为null

				TreeNode rtree = new TreeNode(num);

				root.setRightchild(rtree);
				rtree.setParent(root);

			} else { // 否则，右子结点递归

				DatatoTree(num, root.getRightchild());
			}

		}

	}