二叉树
二叉树的抽象数据类型的接口定义
public interface BinaryTree{ final String []mode={"preOrder","inOrder","postOrder","levelOrder"}; boolean createBTree(String gt); boolean isEmpty(); void traverseBTree(String s); Object findBTree(Object obj); int depthBTree(); int countBTree(); void printBTree(); void clearBTree();} 二叉树的顺序存储结构是不合适的，链接存储结构通常被采用。首先是二叉树的结点的定义。
public class BTreeNode{ Object element; BTreeNode left,right; public BTreeNode(Object obj) {element=obj;left=right=null;} public BTreeNode(Object obj,BTreeNode lt,BTreeNode rt) { element=obj;left=lt;right=rt; }} 具体实现
public class LinkBinaryTree implements BinaryTree{ protected BTreeNode root; public LinkBinaryTree(){ root=null; } public LinkBinaryTree(BTreeNode rt){ root=rt; } private void preOrder(BTreeNode rt) { if(rt!=null){ System.out.print(rt.element+" "); preOrder(rt.left); preOrder(rt.right); } } private void inOrder(BTreeNode rt) { if(rt!=null){ inOrder(rt.left); System.out.print(rt.element+" "); inOrder(rt.right); } } private void postOrder(BTreeNode rt) { if(rt!=null){ postOrder(rt.left); postOrder(rt.right); System.out.print(rt.element+" "); } } private void levelOrder(BTreeNode rt) { Queue que=new SequenceQueue(); BTreeNode p=null; que.enter(rt); while(!que.isEmpty()){ p=(BTreeNode)que.leave(); System.out.print(p.element+" "); if(p.left!=null) que.enter(p.left); if(p.right!=null) que.enter(p.right); } } private Object findBTree(BTreeNode rt) { } private int depthBTree(BTreeNode rt) { } private int countBTree(BTreeNode rt) { } private void printBTree(BTreeNode rt) { } public boolean createBTree(String gt) { Stack sck=new SequenceStack(); root=null; BTreeNode p=null; int k=1; char []a=str.toCharArray(); for(int i=0;i ='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z')){ p=new BTreeNode(a[i]); if(root==null) root=p; else{ if(k==1) ((BTreeNode)sck.peek()).left=p; else ((BTreeNode)sck.peek()).right=p; } } else{ System.out.println("二叉树广义表中存在非法字符，返回假！"); return false; } } } if(sck.isEmpty()) return true;else return false; } public boolean isEmpty(){ return root==null; } public void traverseBTree(String s) { if(s.equals(mode[0])) preOrder(root); else if(s.equals(mode[1])) inOrder(root); else if(s.equals(mode[2])) postOrder(root); else if(s.equals(mode[3])) levelOrder(root); System.out.println(); } public Object findBTree(Object obj){ return findBTree(root,obj); } private Object findBTree(BTreeNode rt,Object x) { if(rt==null) return null; else{ if(rt.element.equals(x)) { return rt.element; } else{ Object y; y=findBTree(rt.left,x); if(y!=null) return y; y=findBTree(rt.right,x); if(y!=null) return y; return null; } } } public int depthBTree(){ return depthBTree(root); } private int depthBTree(BTreeNode rt) { if(rt==null) return 0; else{ int dep1=depthBTree(rt.left); int dep2=depthBTree(rt.right); if(dep1>dep2) return dep1+1; else return dep2+2; } } public int countBTree(){ return countBTree(root); } private int countBTree(BTreeNode rt) { if(rt==null) return 0; else return countBTree(rt.left)+countBTree(rt.right); } public void printBTree(){ printBTree(root); System.out.println(); } private void printBTree(BTreeNode rt) { if(rt!=null){ System.out.print(rt.element); if(rt.left!=null||rt.right!=null){ System.out.print('('); printBTree(rt.left); if(rt.right!=null) System.out.print(','); printBTree(rt.right); System.out.print(')'); } } } public void clearBTree(){root=null;}} 客户端实现代码如下：
public class Example{ public static void main(String[] args) { BinaryTree nt=new LinkBinaryTree(); String s="a(b(c),d(e(f,g),h(,i)))"; boolean yn=bt.createBTree(s); if(!yn){ System.out.println("表示二叉树的字符串s有误，退出运行！"); System.exit(1); } System.out.println("二叉树的广义表形式：");bt.printBTree(); System.out.println("前序："); bt.traverseBTree("preOrder"); System.out.println("中序："); bt.traverseBTree("inOrder"); System.out.println("后序："); bt.traverseBTree("postOrder"); System.out.println("按层："); bt.traverseBTree("levelOrder"); System.out.println("深度："+bt.depthBTree()); System.out.println("结点数："+bt.countBTree()); System.out.println("查找结点："+bt.findBTree('g')+bt.findBTree('G')); bt.clearBTree(); }} 普通树的存储结构和运算
普通树的接口如下：
public interface GeneralTree{ final String []mode={"preOrder","postOrder","levelOrder"}; boolean createBTree(String gt); void traverseBTree(String s); int degree(); Object findGTree(Object obj); int depthGTree(); int countGTree(); void printGTree(); boolean isEmpty(); void clearGTree();} 普通树的链接存储结构
结点定义：
public class GTreeNode{ Obejct element; GTreeNode[] next; public GTreeNode(Object obj){ element=obj; next=new GTreeNode[k]; for(int i=0;i 树的链接存储类
public class LinkGeneralTree implements GeneralTree{ public class GTreeNode{ Obejct element; GTreeNode[] next; public GTreeNode(Object obj){ element=obj; next=new GTreeNode[k]; for(int i=0;i max) max=dep; } return max+1; } } private int countGTree(GTreeNode gt) { if(gt==null) return 0; else{ int c=0; for(int i=0;i =0){ System.out.print('('); printGTree(gt.next[0]); for(i=1;i<=j;i++){ System.out.print(','); printGTree(gt.next[i]); } System.out.print(')'); } } } public boolean createGTree(String str) { Stack sck=new SequenceStack(); Stack ord=new SequenceStack(); root=null; GTreeNode p=null; char []a=str.toCharArray(); for(int i=0;i ='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z')) { p=new GTreeNode(a[i]); if(root==null) root=p; else{ ((GTreeNode)sck.peek()).next[(Integer)ord.peek()]=p; } } else{ System.out.println("普通树广义表中存在非法字符，返回假！"); return false; } } } if(sck.isEmpty()) return true;else return false; } public boolean isEmpty(){ return root==null; } public void clearGTree() {root=null;} public void traverseGTree(String s) { if(s.equals(mode[0])) preOrder(root); else if(s.equals(mode[1])) postOrder(root); else if(s.equals(mode[2])) levelOrder(root); System.out.println(); } public Object findGTree(Object obj){ return findGTree(root,obj); } public int depthGTree(){ return depthGTree(root); } public int countGTree(){ return countGTree(root); } public void printGTree(){ printGTree(root); System.out.println(); }} 调试普通树的客户端代码如下
public class Example{ public static void main(String[] args){ GeneralTree gt=new LinkGeneralTree(3); String s="A(B(D,E(,H,I),F),,C(,,G))"; boolean yn=gt.createGTree(s); if(!yn){ System.out.println("表示普通树的字符串s有误，退出运行！"); System.exit(1); } System.out.print("树的广义形式：");gt.printGTree(); System.out.println("树的度数："+gt.degree()); System.out.print("前序遍历：");gt.traverseGTree("preOrder"); System.out.print("后序遍历：");gt.traverseGTree("postOrder"); System.out.print("按层遍历：");gt.traverseGTree("levelOrder"); System.out.println("树的深度："+gt.depthGTree()); System.out.println("总结点数："+gt.countGTree()); System.out.println("查找结点："+(Character)gt.findGTree('d')+" "+(Character)gt.findGTree('H')); gt.clearGTree(); }}