import java.util.Stack; //可自行导入包
class BTNode<E> //二叉链中结点类
{ E data; //数据元素
BTNode lchild; //指向左孩子结点
BTNode rchild; //指向右孩子结点
public BTNode() //默认构造方法
{
lchild=rchild=null;
}
public BTNode(E d) //重载构造方法
{
data=d;
lchild=rchild=null;
}
}
public class BTreeClass //二叉树类
{
BTNode<Character> b; //根结点
String bstr; //二叉树的括号表示串
public BTreeClass() //构造方法
{
b=null;
}
public void CreateBTree(String str) //创建以b为根结点的二叉链存储结构
{
Stack<BTNode> st=new Stack<BTNode>(); //建立一个栈
BTNode<Character> p=null;
boolean flag=true;
char ch;
int i=0;
while (i<str.length()) //循环扫描str中每个字符
{
ch=str.charAt(i);
//System.out.println(v);
switch(ch)
{
case '(':
st.push(p); //刚刚新建的结点有孩子,将其进栈
flag=true;
break;
case ')':
st.pop(); //栈顶结点的子树处理完，出栈
break;
case ',':
flag=false; //开始处理栈顶结点的右孩子
break;
default:
p=new BTNode<Character>(ch); //用ch值新建一个结点
if (b==null)
b=p; //若尚未建立根结点,p作为根结点
else //已建立二叉树根结点
{
if (flag) //新结点p作为栈顶结点的左孩子
{
if (!st.empty())
st.peek().lchild=p;
}
else //新结点p作为栈顶结点的右孩子
{
if (!st.empty())
st.peek().rchild=p;
}
}
break;
}
i++; //继续遍历
}
}
public String toString() //返回二叉链的括号表示串
{
bstr="";
toString1(b);
return bstr;
}
private void toString1(BTNode<Character> t) //被DispBTNode方法调用
{
if (t!=null)
{ bstr+=t.data; //输出根结点值
if (t.lchild!=null || t.rchild!=null)
{
bstr+="("; //有孩子结点时输出"("
toString1(t.lchild); //递归输出左子树
if (t.rchild!=null)
bstr+=","; //有右孩子结点时输出","
toString1(t.rchild); //递归输出右子树
bstr+=")"; //输出")"
}
}
}
public BTNode<Character> FindNode(char x) //查找值为x的结点算法
{
return FindNode1(b,x);
}
private BTNode<Character> FindNode1(BTNode<Character> t,char x) //被FindNode方法调用
{
BTNode<Character> p;
if (t==null) return null; //t为空时返回null
else if (t.data==x) return t; //t所指结点值为x时返回t
else
{ p=FindNode1(t.lchild,x); //在左子树中查找
if (p!=null) return p; //在左子树中找到p结点，返回p
else return FindNode1(t.rchild,x); //返回在右子树中查找结果
}
}
public int Height() //求二叉树高度的算法
{
return Height1(b);
}
private int Height1(BTNode<Character> t) //被Height方法调用
{
int lchildh,rchildh;
if (t==null)
return 0; //空树的高度为0
else
{
lchildh=Height1(t.lchild); //求左子树高度lchildh
rchildh=Height1(t.rchild); //求右子树高度rchildh
return Math.max(lchildh,rchildh)+1;
}
}
public int Count(){
//可根据Height编写这个类
return Count(b);
}
public int Count(BTNode<Character> t){
int count=0 ;
if(t!=null){
if (t.lchild==null && t.rchild==null){
count++;
}else{
count+=Count(t.lchild);
count+=Count(t.rchild);
}
}
return count;
}
}
}
/*以上为树的基本构建方法，还需要测试类才能实现以上代码，还可用来查找某个节点
———————————————————————————————————————————
//使用BTreeClass即以下代码编写求叶子结点数目的函数
import java.util.*;
@SuppressWarnings("unchecked")
public class Demo4 {
public static void displeaf1(BTreeClass bt) //基于先序遍历输出叶子结点
{
displeaf11(bt.b);
}
private static void displeaf11(BTNode<Character> t)
{ if (t!=null)
{
if (t.lchild==null && t.rchild==null)
System.out.print(t.data+" "); //输出叶子结点
displeaf11(t.lchild); //遍历左子树
displeaf11(t.rchild);//遍历右子树
}
}
public static void main(String[] args)
{
String s="A(B,C(E,F))";
BTreeClass bt=new BTreeClass();
bt.CreateBTree(s);
System.out.println("bt: "+bt.toString());
System.out.println("叶子结点数目: "+bt.Count());
System.out.print("displeaf1: ");//叶子结点
displeaf1(bt);
}
}
———————————————————————————————————————————
//编写根据先序序列和中序序列得出二叉树
import java.util.*;
public class Demo3 {
public static BTreeClass CreateBT1(String pre,String in) {//由先序序列pre和中序序列in构造二叉链
BTreeClass bt=new BTreeClass();
bt.b=CreateBT11(pre,0,in,0,pre.length());
return bt;
}
private static BTNode<Character> CreateBT11(String pre,int i,String in,int j,int n)
{
BTNode<Character> t;
char ch;
int p,k;
if (n<=0) return null;
ch=pre.charAt(i);
t=new BTNode<Character>(ch); //创建根结点(结点值为ch)
p=j; //p指中序序列的开始元素
while (p<j+n) //在中序序列中找等于ch的位置k
{ if (in.charAt(p)==ch)
break; //在in中找到后退出循环
p++;
}
k=p-j; //确定根结点在in中的位置p
t.lchild=CreateBT11(pre,i+1,in,j,k); //递归构造左子树
t.rchild=CreateBT11(pre,i+k+1,in,p+1,n-k-1); //递归构造右子树
return t;
}
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
String pre="ABDCEF";
String in="DBAECF";
//String post="GDBEFCA";
BTreeClass bt=new BTreeClass();
bt=CreateBT1(pre,in);
System.out.println("bt: "+bt.toString());
}
}
//第一次发，不怎么弄，部分代码来源于书本，如有错误，欢迎指出