树节点定义:
classTreeNode{
publicTreeNodeleft;
publicTreeNoderight;
publicintvalue;
publicTreeNode(TreeNodeleft,TreeNoderight,intvalue){
this.left=left;
this.right=right;
this.value=value;
}
}
二叉树及其操作:
publicclassBinaryTree{
publicstaticintgetTreeHeight(TreeNoderoot){
if(root==null)
return0;
if(root.left==null&;&;root.right==null)
return1;
return1+Math
.max(getTreeHeight(root.left),getTreeHeight(root.right));
}
publicstaticvoidrecursePreOrder(TreeNoderoot){
if(root==null)
return;
System.out.println(root.value);
if(root.left!=null)
recursePreOrder(root.left);
if(root.right!=null)
recursePreOrder(root.right);
}
publicstaticvoidstackPreOrder(TreeNoderoot){
Stackstack=newStack();
if(root==null)
return;
stack.push(root);
System.out.println(root.value);
TreeNodetemp=root.left;
while(temp!=null){
stack.push(temp);
System.out.println(temp.value);
temp=temp.left;
}
temp=(TreeNode)stack.pop();
while(temp!=null){
temp=temp.right;
while(temp!=null){
stack.push(temp);
System.out.println(temp.value);
temp=temp.left;
}
if(stack.empty())
break;
temp=(TreeNode)stack.pop();
}
}
publicstaticvoidrecurseInOrder(TreeNoderoot){
if(root==null)
return;
if(root.left!=null)
recurseInOrder(root.left);
System.out.println(root.value);
if(root.right!=null)
recurseInOrder(root.right);
}
publicstaticvoidstackInOrder(TreeNoderoot){
Stackstack=newStack();
if(root==null)
return;
else
stack.push(root);
TreeNodetemp=root.left;
while(temp!=null){
stack.push(temp);
temp=temp.left;
}
temp=(TreeNode)stack.pop();
while(temp!=null){
System.out.println(temp.value);
temp=temp.right;
while(temp!=null){
stack.push(temp);
temp=temp.left;
}
if(stack.empty())
break;
temp=(TreeNode)stack.pop();
}
}
publicstaticvoidmain(String[]args){
TreeNodenode1=newTreeNode(null,null,1);
TreeNodenode2=newTreeNode(null,node1,2);
TreeNodenode3=newTreeNode(null,null,3);
TreeNodenode4=newTreeNode(node2,node3,4);
TreeNodenode5=newTreeNode(null,null,5);
TreeNoderoot=newTreeNode(node4,node5,0);
System.out.println("TreeHeightis"+getTreeHeight(root));
System.out.println("RecurseInOrderTraverse");
recurseInOrder(root);
System.out.println("StackInOrderTraverse");
stackInOrder(root);
System.out.println("RecursePreOrderTraverse");
recursePreOrder(root);
System.out.println("StackPreOrderTraverse");
stackPreOrder(root);
}
}
用LinkedList重写的Stack:
importjava.util.EmptyStackException;
importjava.util.LinkedList;
publicclassStack{
privateLinkedListlist;
publicStack(){
this.list=newLinkedList();
}
publicbooleanempty(){
returnlist.isEmpty();
}
publicObjectpeek(){
if(empty())
thrownewEmptyStackException();
returnlist.getLast();
}
publicObjectpop(){
if(empty())
thrownewEmptyStackException();
returnlist.removeLast();
}
publicvoidpush(Objecto){
list.add(o);
}
publicstaticvoidmain(String[]args){
Stackstack=newStack();
stack.push(newInteger(1));
stack.push(newInteger(11));
stack.push(newInteger(1111));
stack.push(newInteger(22));
stack.push(newInteger(222));
stack.push(newInteger(31));
stack.push(newInteger(221));
while(!stack.empty()){
System.out.println(stack.pop());
}
}
}
------------------