生成树的算法

一、实验目的及要求

根据老师所给的代码，执行所有生成树的算法。输出要求：生成满二叉树，跟踪每一个节点的生成过程，即输出该节点所在的层及在该层的位置，以最左边的节点为0。

二、实验内容及步骤

class QueueNode <T>
{
	T data;
	QueueNode<T> next;
	QueueNode()
	{
		this.next = null;
	}
	QueueNode(T data)
	{
		this.data = data;
		this.next = null;
	}	
}
public class QueueDemo<T> {
	QueueNode<T> head = new QueueNode<T>();
	public void enQueue(T data)
	{
		QueueNode<T> tail;
		tail = head;
		//move to the last node of queue
		while (tail.next != null)
			tail = tail.next;
		QueueNode<T> node = new QueueNode<T>(data);
		// insert the new node at the tail of queue
		tail.next = node;		
	}	
	public T deQueue()
	{
		QueueNode<T> node;
		node = head.next;
		head.next = node.next;
		return node.data;
	}
	public boolean isEmpty()
	{
		if (head.next ==  null)
			return true;
		else
			return false;
	}
	void Tranverse()  //遍历
	{
		QueueNode<T> node = head.next;
		while (node != null)
		{
			System.out.println(node.data);
			node = node.next;
		}
	}

import circleSqQueue.QueueDemo;
import java.util.Scanner;
class TreeNode 
{
	int data;  //结点的数据域
	TreeNode lchild;  //左孩子域
	TreeNode rchild;  //右孩子域
	TreeNode()
	{
		this.lchild = null;
		this.rchild = null;
	}
	TreeNode(int data)
	{
		this.data = data;
		this.lchild = null;
		this.rchild = null;
	}
	int getData()
	{
		return data;
	}
}
public class TreeDemo {
	static TreeNode BuildTree(TreeNode node)
	{
		int data;
		//输入根结点的数据
		System.out.print("Input an Integer(0--null):");
		Scanner sc = new Scanner(System.in); 
		data = sc.nextInt();		
		if (data == 0)
			node = null;
		else
		{
			node = new TreeNode (); //构造新结点
			node.data = data;
			node.lchild = BuildTree(node.lchild);
			node.rchild = BuildTree(node.rchild);
		}
		return node;
	}	
	static void PreTranverse(TreeNode T) //先根遍历
	{
		if (T != null)
		{
			System.out.print(T.data+" ");
			PreTranverse(T.lchild);
			PreTranverse(T.rchild);
		}			
	}	
	static void InTranverse(TreeNode T)  //中根遍历
	{
		if (T != null)
		{
			InTranverse(T.lchild);
			System.out.print(T.data+" ");
			InTranverse(T.rchild);
		}			
	}	
	static void PostTranverse(TreeNode T)   //后根遍历
	{
		if (T != null)
		{
			PostTranverse(T.lchild);
			PostTranverse(T.rchild);
			System.out.print(T.data+" ");
		}			
	}
	static TreeNode BuildbyLevel(TreeNode rootl) //层次遍历
	{
		int data;
		//输入一个表示根节点的整数
		System.out.print("Input an Integer(0--null):");
		Scanner sc = new Scanner(System.in); 
		data = sc.nextInt();		
		if (data != 0)
		{
			rootl = new TreeNode(data);
			//构建队列
			QueueDemo<TreeNode> thequeue = new QueueDemo<TreeNode>();
			thequeue.enQueue(rootl);
			while(!thequeue.isEmpty())
			{
				TreeNode thenode = thequeue.deQueue();
                //输入左子树的数据
				System.out.print("Input the data of "+thenode.getData()+"'s left child(0--null):");
				data = sc.nextInt();
				if (data != 0)
				{
					TreeNode lnode = new TreeNode(data);
					thenode.lchild = lnode;
					thequeue.enQueue(lnode);
				}
				//输入右子树的数据
				System.out.print("Input the data of "+thenode.getData()+"'s right child(0--null):");
				data = sc.nextInt();
				if (data != 0)
				{
					TreeNode rnode = new TreeNode(data);
					thenode.rchild = rnode;
					thequeue.enQueue(rnode);
				}
			}
		}
		sc.close();
		return rootl;
	}
	public static void main(String[] args) {
		 //Scanner sc = new Scanner(System.in);
	   	 //rootl = BuildTree(rootl);
		 //sc.close();
		 TreeNode rootl = null;
		 rootl = BuildbyLevel(rootl);
         System.out.println("先根遍历为");
		 PreTranverse(rootl);
		 System.out.println();
System.out.println("中根遍历为");
		 InTranverse(rootl);
		 System.out.println();	
        System.out.println("后根遍历为");	
		 PostTranverse(rootl);
	}
}