二叉树 in Java
最近在看 Data Structures outside in Java看到 二叉树 于是自己学着写了一个
运行结果是 中序遍历：
The recursive travell:
D B F H E G A C
The stack way travell:
D B F H E G A C
Notes：
遍历的方法
1：递归调用： 思路清晰，编程简单。但是问题也很严重，需要消耗很多的栈空间，经过测试，我把节点开到10000的时候 StackOverFlow了，同时时间效率可能也不高。
2：手动写栈，模拟：代码复杂了一点，但是不会暴栈
import java.util.Date;import java.util.Stack;/** * Just a demo about BinaryTree in Java * @author Jason * 2010.5.22 * Notes: If wants to attach of deletea subTree of anode, just modify the leftChild/rightChild attribute. */public class BinaryTree<T> {private T data;public BinaryTree<T> parent;public BinaryTree<T> leftChild;public BinaryTree<T> rightChild;// constructor public BinaryTree (){this.data=null;this.parent=null;this.leftChild=null;this.rightChild=null;}// constructor without parapublic BinaryTree (T data){this.data=data;this.parent=null;this.leftChild=null;this.rightChild=null;}public void setData(T data){this.data=data;}public T getData(){return this.data;}// inorder travell with recursive waypublic void travellRecursive(BinaryTree<T> root){if(root.leftChild!=null)travellRecursive(root.leftChild);System.out.print(root.getData()+" ");if(root.rightChild!=null) travellRecursive(root.rightChild);}// inorder travell with self made stackpublic void travellStack( BinaryTree<T> root){if(root==null)return;class StackNode{public int millStone;public BinaryTree<T> node;public StackNode ( BinaryTree<T> n, int m){this.node=n;this.millStone=m;}}java.util.Stack<StackNode> stack=new Stack<StackNode>();stack.push( new StackNode(root, 1) );StackNode temp;while(!stack.empty()){temp=stack.pop();switch (temp.millStone){case 1:temp.millStone=2;stack.push(temp);if(temp.node.leftChild!=null)stack.push( new StackNode(temp.node.leftChild, 1) );break;case 2:temp.millStone=3;stack.push(temp);System.out.print(temp.node.getData()+" ");if(temp.node.rightChild!=null)stack.push( new StackNode(temp.node.rightChild, 1) );break;case 3:break;default:break;}}}// find the whole root of this treepublic BinaryTree<T> findRoot(){if(this.parent==null)return this;BinaryTree<T> nextParent=this.parent;while(nextParent.parent!=null)nextParent=nextParent.parent;return nextParent;}// this is just a demo to teststatic BinaryTree<String> generateTree(){BinaryTree<String> treeA=new BinaryTree<String>("A");BinaryTree<String> treeB=new BinaryTree<String>("B");BinaryTree<String> treeC=new BinaryTree<String>("C");BinaryTree<String> treeD=new BinaryTree<String>("D");BinaryTree<String> treeE=new BinaryTree<String>("E");BinaryTree<String> treeF=new BinaryTree<String>("F");BinaryTree<String> treeG=new BinaryTree<String>("G");BinaryTree<String> treeH=new BinaryTree<String>("H");treeF.rightChild=treeH;treeH.parent=treeF;treeE.rightChild=treeG;treeG.parent=treeE;treeE.leftChild=treeF;treeF.parent=treeE;treeB.rightChild=treeE;treeE.parent=treeB;treeB.leftChild=treeD;treeD.parent=treeB;treeA.rightChild=treeC;treeC.parent=treeA;treeA.leftChild=treeB;treeB.parent=treeA;//BinaryTree<String> BinaryFather=treeH;//for(int i=1;i<=10000;i++)//{//BinaryTree<String> treeTemp=new BinaryTree<String>(String.valueOf(i));//treeTemp.parent=BinaryFather;//BinaryFather.leftChild=treeTemp;//BinaryFather=treeTemp;//}return treeH;}public static void main(String[] args) {BinaryTree<String> root=generateTree();root=root.findRoot();Date date1=new Date();System.out.println("The recursive travell:");root.travellRecursive(root);//System.out.println("Time cost is :"+(new Date().getTime()-date1.getTime()));System.out.println();date1=new Date();System.out.println("The stack way travell:");root.travellStack(root);//System.out.println("Time cost is :"+(new Date().getTime()-date1.getTime()));}}
页:
[1]