二叉樹的一些算法

1、class BiTNodeint cin=0;int parent;AnyType data;BiTNode leftChild,rightChild; int height=0;BiTNode()data=null; leftChild=rightChild=null;BiTNode(AnyType thedata) data=thedata; leftChild=rightChild=null;BiTNode(AnyType thedata,BiTNode lt,BiTNode rt) data=thedata;leftChild=lt;rightChild=rt;public BiTNo

2、de getleftChild( ) return leftChild;public BiTNode getrightChild( ) return rightChild;public Object getdata( )return data; inaryTreeAnyType extends Comparableprivate BiTNode rootNode=new BiTNode(); TreeNode root=new TreeNode();int count=0;private int i=0;static int l=0;iwJpublic BiTNode createBinary

3、Tree(AnyType preOrder) BiTNode rootNode=null;if(ipreOrder.length)AnyType data=preOrderi;i+;if(data!=null) rootNode=new BiTNode(data); rootNode.leftChild=createBinaryTree(preOrder); rootNode.rightChild=createBinaryTree(preOrder);return rootNode;/層次遍歷int cou=0;public void LevelOrderTraverse() newQueue

4、BiTNode q =newLinkedListBiTNode();BiTNode p = rootNode;if (p != null)q.add(p);while (q.size() 0) System.out.print(q.element().data + );BiTNode node = q.remove(); if (node.leftChild != null) q.add(node.leftChild);if (node.rightChild != null) q.add(node.rightChild);/統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)public int countLeafNode(Bi

5、TNode t)if(t=null) return 0;else if(t.leftChild=null&t.rightChild=null) l+;countLeafNode(t.leftChild); countLeafNode(t.rightChild); return l;/交換二叉樹的左右子樹public BiTNode change(BiTNode t) BiTNode tmp=new BiTNode(); if(t!=null)tmp=t.leftChild; t.leftChild=t.rightChild; t.rightChild=tmp;if(t.leftChild!=n

6、ull)change(t.leftChild);if(t.leftChild!=null) change(t.rightChild); return t;/判斷所給定的二叉樹是不是完全二叉樹public boolean wanquan(ArrayListBiTNode list)QueueBiTNode q =new LinkedListBiTNode();BiTNode p = rootNode; if (p != null)q.add(p); while (q.size() 0) if(q.element().leftChild=null&q.element().rightChild!=n

7、ull) /flag=false;return false;BiTNode node=q.remove(); list.add(node);if (node.leftChild != null) q.add(node.leftChild);if (node.rightChild != null) q.add(node.rightChild);if(node.leftChild!=null&node.rightChild=null&q.element().leftC hild!=null)/flag=false;return false;if(q. size()!=0&node.leftChil

8、d=null&node.rightChild=null&q.el ement().leftChild!=null)return false;return true;/統(tǒng)計(jì)節(jié)點(diǎn)的個(gè)數(shù)public int countNode()return countNode(rootNode);public int countNode(BiTNode t)int m,n;if(t=null) return 0;m=countNode(t.leftChild);n=countNode(t.rightChild);return m+n+1;Tt判斷二叉樹是不是堆public boolean dui(BiTNode

9、node) ArrayListBiTNodelist=newArrayListBiTNode();if(!wanquan(list) retur nfalse;/ 必須是完全二叉樹count11+;BiTNode l, r;r = node.rightChild;l = node.leftChild;if (l != null) if (node.data.hashCode() l.data.hashCode()return true;if (r != null) if (node.data.hashCode() r.data.hashCode()return true;if (node.le

10、ftChild != null) dui(node.leftChild);if (node.rightChild != null) dui(node.rightChild);if(count11this.countNode(node) return false;elsereturn true;/判斷是否為二叉排序樹int count1=0;public boolean search(BiTNode t) count1+;if (t.leftChild!= null) if (t. data.hashCode()t.leftChild.data.hashCode() return false;i

11、f (t.rightChild!= null) if (t. data.hashCode()t.rightChild.data.hashCode() return false;if (t.leftChild != null) search(t.leftChild);if (t.rightChild != null) search(t.rightChild);if(count1this.countNode(t)return false;elsereturn true;/ /二叉排序樹的查找方法public boolean contains(AnyType x)return contains(x,

12、rootNode);public boolean contains(AnyType x,BiTNode t) if(t=null) return false;int compareResult=pareTo(t.data); if(compareResult0)return contains(x,t.rightChild); elsereturn true;public AnyType findMin() throws Exceptionreturn findMin(rootNode).data; private BiTNode findMin(BiTNode t) if(t=null)ret

13、urn null;else if(t.leftChild=null) return t;return findMin(t.leftChild);public AnyType findMax() throws Exceptionreturn findMax(rootNode).data; private BiTNode findMax(BiTNode t) if(t=null)return null;else if(t.rightChild=null)return t;return findMax(t.rightChild);/計(jì)算樹的深度public int depth()return dep

14、th(rootNode);public int depth (BiTNode t ) / 返回二叉樹的深度 int depthleftChild,depthrightChild;if(t=null) return 0; depthleftChild = depth( t.leftChild ); depthrightChild = depth( t.rightChild );return Math.max(depthleftChild,depthrightChild)+1;/孩子鏈表的存儲(chǔ)public TreeNode CreateBiTree() throws IOException Buf

15、feredReader reader = newBufferedReader(newInputStreamReader(System.in);linkedList=newString value = linkedList=newLinkedListTreeNode();/作為指針TreeNode p=null;TreeNode q=null;/保存孩子的字符串?dāng)?shù)組 至多20個(gè)孩子 char c=null;if (value.equals( ) return null; else /輸入的第一個(gè)字符不空TreeNode root二new TreeNode(); root, data二value;

16、/入隊(duì)列l(wèi)inkedLis t.add(root);/當(dāng)隊(duì)列不空建立起子節(jié)點(diǎn)while (linkedList.size()0) p=linkedList.removeFirst();System. out .println(“請(qǐng)輸入+p.data+的所有孩子)；String str=reader.readLine(); c=str.toCharArray(); if(!str.equals( )TreeNode node二new TreeNode();node.data=c0;p.se tF irs tChild(node);q二node;for(int j=1;jc.length;j+)T

17、reeNode next二new TreeNode();next.data=cj;q.se tNext sibling(next);linkedList.add(q);q=q.getNextsibling();q.setNextsibling(null); linkedList.add(q);return root; ilijjpublic void preOrder( TreeNode t )if(t!=null) System.out.print(t.data);count+;preOrder(t.firstChild); preOrder(t.nextsibling);/ /后序遍歷pu

18、blic void postOrder( TreeNode t ) if(t!=null) postOrder(t.firstChild); postOrder(t.nextsibling);System.out.print(t.data);/ /層次遍歷IJJJJnewpublic void LevelOrderTraverse2() QueueTreeNode q = LinkedListTreeNode();newTreeNode p = root;if (p != null)q.add(p);while (q.size() 0) System.out.print(q.element().data);TreeNode node = q.remove();if (node.firstChild != null) q.add(node.firstChild);if (node.nextsibling!= null) q.add(node.nextsibling);/ /統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)public int countLeafNode(TreeNode t)if(t=null) return 0;else if(t.