【例6.1】 以先根和中根次序遍历序列建立二叉树。
import ds_java.Tree1;
public class Tree1_ex //以先根、中根次序建立二叉树
{
public static void main(String args[])
{
String prestr="ABDGCEFH";
String instr="DGBAECHF";
if(args.length>1)
{
prestr=args[0];
instr=args[1];
}
Tree1 t1=new Tree1(prestr,instr);
t1.preorderTraversal();
t1.inorderTraversal();
t1.postorderTraversal();
}
}
程序运行结果如下：
prestr=ABDGCEFH instr=DGBAECHF first=A k=3
prestr=BDG instr=DGB first=B k=2
prestr=DG instr=DG first=D k=0
prestr=G instr=G first=G k=0
prestr=CEFH instr=ECHF first=C k=1
prestr=E instr=E first=E k=0
prestr=FH instr=HF first=F k=1
prestr=H instr=H first=H k=0
先根次序： A B D G C E F H
中根次序： D G B A E C H F
后根次序： G D B E H F C A
【例6.2】 以标明空子树的先根次序遍历序列建立二叉树。
程序如下：
package ds_java;
import ds_java.TreeNode1;
import ds_java.Tree1;
public class Tree2 extends Tree1 //以标明空子树的先根次序建立二叉树
{
private String str; //表示二叉树带空子树的先根遍历序列
private int i=0;
public Tree2() //构造空二叉树
{
super();
}
public Tree2(String s)
{
str=s;
System.out.println("str="+str);
if(str.length()>0)
root=enter();
}
public TreeNode1 enter() //返回所建立二叉树的根结点
{
TreeNode1 p=null;
char ch=str.charAt(i);
i++;
if(ch!='.')
{
p=new TreeNode1(ch+""); //非"."时，建立结点
p.left=enter(); //建立左子树，递归调用
p.right=enter(); //建立右子树，递归调用
}
return p; //ch="."时，返回null
}
}
源程序Tree2_ex.java调用Tree2类建立一棵二叉树。程序如下：
import ds_java.Tree2;
public class Tree2_ex //以标明空子树的先根次序建立二叉树
{
public static void main(String args[])
{
String prestr="CE..FH...";
if (args.length>0)
prestr=args[0];
Tree2 t2=new Tree2(prestr);
t2.preorderTraversal();
t2.inorderTraversal();
t2.postorderTraversal();
}
}
程序运行结果如下：
str=CE..FH...
先根次序： A B D G C E F H
中根次序： D G B A E C H F
后根次序： G D B E H F C A
【例6.3】 建立链式结构的完全二叉树。
程序如下：
import ds_java.TreeNode1;
import ds_java.Tree1;
public class Tree3 extends Tree1 //建立链式结构的完全二叉树
{
private String str;
public Tree3() //构造空二叉树
{
super();
}
public Tree3(String s) //构造完全二叉树
数据结构与算法题库 {
str=s;
System.out.println("str="+str);
root=enter(1); //以编号为1的元素作为根结点，建立一棵二叉树
}
public TreeNode1 enter(int i) //建立一棵子树，以编号为i的元素作为子树的根结点
{
TreeNode1 p=null;
char ch;
if(i<=str.length())
{
ch=str.charAt(i-1); //取字符串中第i-1个元素作为编号为i结点的元素值
System.out.println(" i="+i+" ch="+ch);
p=new TreeNode1(ch+""); //建立结点p
p.left=enter(2*i); //建立p的左子树
p.right=enter(2*i+1); //建立p的右子树
}
return p;
}
public static void main(String args[])
{
String varstr="ABCDEFGH";
if(args.length>0)
varstr=args[0];
Tree3 t3=new Tree3(varstr);
t3.preorderTraversal();
t3.inorderTraversal();
t3.postorderTraversal();
}
}
程序运行结果如下：
str=ABCDEFGH
i=1 ch=A
i=2 ch=B
i=4 ch=D
i=8 ch=H
i=5 ch=E
i=3 ch=C
i=6 ch=F
i=7 ch=G
先根次序： A B D H E C F G
中根次序： H D B E A F C G
后根次序： H D E B F G C A
【例6.4】 以广义表表示建立二叉树。
import ds_java.TreeNode1;
import ds_java.Tree2;
public class Tree4 extends Tree2 //以广义表表示建立二叉树
{
private String str;
private int i=0;
public Tree4() //构造空二叉树
{
super();
}
public Tree4(String s)
{
str=s;
System.out.println("str="+str);
if(str.length()>0)
root=enter(); //以str的全部元素建立一棵二叉树
}
public TreeNode1 enter() //以str的部分元素（从i开始）建立一棵子树
{
TreeNode1 p=null;
char ch=str.charAt(i);
if(ch>='A' && ch<='Z') //大写字母
发表评论