二叉树的练习

一、实验目的及要求

以下练习都需要用广度优先和深度优先算法实现一遍。
1：给定一棵二叉树，求二叉树的层数
2：给定一棵二叉树，求整棵树节点个数以及叶结点的个数
3：将树结点的数据域声明为int型，然后求出一棵树的最大值，最小值
（以上每一个题目的子题目都要用广度优先和深度优先实现）

二、实验内容及步骤

1、求二叉树的层数

（1）
import circleSqQueue.QueueDemo;
import java.util.Scanner;
class TreeNode 
{
	int data;  //结点的数据域
	TreeNode lchild;  //左孩子域
	TreeNode rchild;  //右孩子域
	private TreeNode rootl;
	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 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 void LevelTranverse(TreeNode rootl)//层次遍历，需引入变量
	{
		TreeNode T=rootl; //外部输入
		if(T!=null) {
			LinkQueue L=new LinkQueue();
			L.offer(T);
			while(!L.isEmpty()) {
				T=(TreeNode)L.poll();
				System.out.print(T.data+" ");
				if(T.lchild!=null)
					L.offer(T.lchild);
				if(T.rchild!=null)
					L.offer(T.rchild);
			  }
		  }
	    }
	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 int getDepth(TreeNode T) {
		if(T!=null) {
			int lDepth=getDepth(T.lchild);
			int rDepth=getDepth(T.rchild);
			return 1+(lDepth>rDepth?lDepth:rDepth);
		}
		return 0;
	}
	public static void main(String[] args) {
		 TreeNode rootl = null;
		 rootl = BuildbyLevel(rootl);
		 //即TreeNode rootl = BuildbyLevel(null);
		 System.out.println("先根遍历为");
		 PreTranverse(rootl);
		 System.out.println();
		 System.out.println("中根遍历为");
		 InTranverse(rootl);
		 System.out.println();	
		 System.out.println("后根遍历为");
		 PostTranverse(rootl);
		 System.out.println();	
		 System.out.println("层次遍历为");
		 LevelTranverse(rootl);
		 System.out.println("树的深度为");
		 System.out.println(getDepth(rootl));
	}
}

（2）
import circleSqQueue.TreeDemo;
public class NodeCount extends TreeDemo{
	public int getDepth1(TreeNode T) {
	    Object rootl = null;
		if (rootl == null) 
		{
		        return 0;
	     }
		    int currentLevelCount = 1; // 当前层的节点数量
		    int nextLevelCount = 0; // 下一层节点数量
		    int depth = 0; // 树的深度
		    LinkQueue T1 = new LinkQueue(); //队列保存树节点
		    T1.offer(rootl);
		    while (!T1.isEmpty()) {
		    	TreeNode temp = (TreeNode)T1.poll(); //移除节点
		        currentLevelCount--; //当前层节点数减1
		     // 添加左节点并更新下一层节点个数
		        if (temp.lchild != null) { 
		            T1.offer(temp.lchild);
		            nextLevelCount++;
		        }
		     // 添加右节点并更新下一层节点个数
		        if (temp.rchild != null) {
		            T1.offer(temp.rchild);
		            nextLevelCount++;
		        }
		     // 如果是该层的最后一个节点,树的深度加1
		        if (currentLevelCount == 0) { 
		            depth++;
		      // 更新当前层节点数量并且重置下一层节点数量
		            currentLevelCount = nextLevelCount;
		            nextLevelCount = 0;
		        }
		    }
		    return depth;
	}
public static void main(String[] args) {
		 TreeNode rootl = null;
		 rootl = BuildbyLevel(rootl); //继承自上一个类的方法哦
		 System.out.println("采用层次遍历后，树的深度为");
		 System.out.println(getDepth(rootl));
	}

2、求整棵树节点个数以及叶结点的个数

（1）
import circleSqQueue.TreeDemo;
public class NodeCount extends TreeDemo{
	public static int countNode(TreeNode T) {
		int count=0;
		if(T!=null) {
			++count;
			count+=countNode(T.lchild);
			count+=countNode(T.rchild);
		}
		return count;
	}
	public static int countNode1(TreeNode T) {
		int count=0;
		if(T!=null) {
			LinkQueue L=new LinkQueue();
			L.offer(T);
			while(!L.isEmpty()) {
				T=(TreeNode)L.poll();
				++count;
				if(T.lchild!=null)
					L.offer(T.lchild);
				if(T.rchild!=null)
					L.offer(T.rchild);
			}
		}
		return count;
	}
	public static void main(String[] args) {
		 TreeNode rootl = null;
		 rootl = BuildbyLevel(rootl); //继承自上一个类的方法哦
		 System.out.println("采用深度优先后，树的结点个数为");
		 System.out.println(countNode(rootl));
		 System.out.println("采用广度优先后，树的结点个数为");
		 System.out.println(countNode1(rootl));
	}
}

（2）
public class LeafNode extends TreeDemo {
	static int total(TreeNode T) {
		if(T==null)
			return 0;
		if(T.lchild==T.rchild&&T.lchild==null&&T.rchild==null)
			return 1;
		else
			return (total(T.lchild)+total(T.rchild))+1;
	}
	public static void main(String[] args) {
		 TreeNode rootl = null;
		 rootl = BuildbyLevel(rootl); //继承自上一个类的方法哦
		 System.out.println("树的叶结点数为");
		 System.out.println(total(rootl));
	}

}

3、求出一棵树的最大值，最小值

(1) 
static int maxval(TreeNode T) {
		if(T==null)
			return 0;
		else
			return T.data>Math.max(maxval(T.lchild), maxval(T.rchild))?T.data:Math.max(maxval(T.lchild), maxval(T.rchild));
	}
	static int minval(TreeNode T) {
		if(T==null)
			return 0;
		else
			return T.data<Math.max(maxval(T.lchild), maxval(T.rchild))?T.data:Math.max(maxval(T.lchild), maxval(T.rchild));
	}

（2）
static int maxval(TreeNode T) {
		int count=0;
		if(T!=null) {
			LinkQueue L=new LinkQueue();
			L.offer(T);
			count=T.data;
			while(!L.isEmpty()) {
				T=(TreeNode)L.poll();
				count=count>T.data?count:T.data;
				if(T.lchild!=null)
					L.offer(T.lchild);
				if(T.rchild!=null)
					L.offer(T.rchild);
			}
		}
		return count;
	}
static int minval(TreeNode T) {
		int count=0;
		if(T!=null) {
			LinkQueue L=new LinkQueue();
			L.offer(T);
			count=T.data;
			while(!L.isEmpty()) {
				T=(TreeNode)L.poll();
				count=count<T.data?count:T.data;
				if(T.lchild!=null)
					L.offer(T.lchild);
				if(T.rchild!=null)
					L.offer(T.rchild);
			}
		}
		return count;
	}