|
|
Posted on 2006-12-29 13:01 Hexise 閱讀(4429) 評論(2) 編輯 收藏 所屬分類: J2SE
樹節點定義:   class?TreeNode? {
 ????public?TreeNode?left;
????public?TreeNode?right;
????public?int?value;
  ????public?TreeNode(TreeNode?left,?TreeNode?right,?int?value)?{
????????this.left?=?left;
????????this.right?=?right;
????????this.value?=?value;
 ????}
 }二叉樹及其操作: public?class?BinaryTree?{
????public?static?int?getTreeHeight(TreeNode?root)?{
????????if?(root?==?null)
????????????return?0;
????????if?(root.left?==?null?&&?root.right?==?null)
????????????return?1;
????????return?1?+?Math
????????????????.max(getTreeHeight(root.left),?getTreeHeight(root.right));
????}
????public?static?void?recursePreOrder(TreeNode?root)?{
????????if?(root?==?null)
????????????return;
????????System.out.println(root.value);
????????if?(root.left?!=?null)
????????????recursePreOrder(root.left);
????????if?(root.right?!=?null)
????????????recursePreOrder(root.right);
????}
????public?static?void?stackPreOrder(TreeNode?root)?{
????????Stack?stack?=?new?Stack();
????????if?(root?==?null)
????????????return;
????????stack.push(root);
????????System.out.println(root.value);
????????TreeNode?temp?=?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();
????????}
????}
????public?static?void?recurseInOrder(TreeNode?root)?{
????????if?(root?==?null)
????????????return;
????????if?(root.left?!=?null)
????????????recurseInOrder(root.left);
????????System.out.println(root.value);
????????if?(root.right?!=?null)
????????????recurseInOrder(root.right);
????}
????public?static?void?stackInOrder(TreeNode?root)?{
????????Stack?stack?=?new?Stack();
????????if?(root?==?null)
????????????return;
????????else
????????????stack.push(root);
????????TreeNode?temp?=?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();
????????}
????}
????public?static?void?main(String[]?args)?{
????????TreeNode?node1?=?new?TreeNode(null,?null,?1);
????????TreeNode?node2?=?new?TreeNode(null,?node1,?2);
????????TreeNode?node3?=?new?TreeNode(null,?null,?3);
????????TreeNode?node4?=?new?TreeNode(node2,?node3,?4);
????????TreeNode?node5?=?new?TreeNode(null,?null,?5);
????????TreeNode?root?=?new?TreeNode(node4,?node5,?0);
????????System.out.println("Tree?Height?is?"?+?getTreeHeight(root));
????????System.out.println("Recurse?In?Order?Traverse");
????????recurseInOrder(root);
????????System.out.println("Stack?In?Order?Traverse");
????????stackInOrder(root);
????????System.out.println("Recurse?Pre?Order?Traverse");
????????recursePreOrder(root);
????????System.out.println("Stack?Pre?Order?Traverse");
????????stackPreOrder(root);
????}
} 用LinkedList重寫的Stack:
 import?java.util.EmptyStackException;
import?java.util.LinkedList;
public?class?Stack?{
????private?LinkedList?list;
????public?Stack()?{
????????this.list?=?new?LinkedList();
????}
????public?boolean?empty()?{
????????return?list.isEmpty();
????}
????public?Object?peek()?{
????????if?(empty())
????????????throw?new?EmptyStackException();
????????return?list.getLast();
????}
????public?Object?pop()?{
????????if?(empty())
????????????throw?new?EmptyStackException();
????????return?list.removeLast();
????}
????public?void?push(Object?o)?{
????????list.add(o);
????}
????public?static?void?main(String[]?args)?{
????????Stack?stack?=?new?Stack();
????????stack.push(new?Integer(1));
????????stack.push(new?Integer(11));
????????stack.push(new?Integer(1111));
????????stack.push(new?Integer(22));
????????stack.push(new?Integer(222));
????????stack.push(new?Integer(31));
????????stack.push(new?Integer(221));
????????while?(!stack.empty())?{
????????????System.out.println(stack.pop());
????????}
????}
}
評論
# re: [復習基礎]Java的二叉樹遍歷操作(遞歸, 非遞歸) 回復 更多評論
2007-06-26 11:35 by
[更新]加入廣度遍歷的BinaryTree:
public class BinaryTree {
public static int getTreeHeight(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math
.max(getTreeHeight(root.left), getTreeHeight(root.right));
}
public static void recursePreOrder(TreeNode root) {
if (root == null)
return;
visit(root);
if (root.left != null)
recursePreOrder(root.left);
if (root.right != null)
recursePreOrder(root.right);
}
public static void stackPreOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
stack.push(root);
visit(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
visit(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
temp = temp.right;
while (temp != null) {
stack.push(temp);
visit(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void recurseInOrder(TreeNode root) {
if (root == null)
return;
if (root.left != null)
recurseInOrder(root.left);
visit(root);
if (root.right != null)
recurseInOrder(root.right);
}
public static void stackInOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
else
stack.push(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
visit(temp);
temp = temp.right;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void widthTraverse(TreeNode root) {
Queue queue = new Queue();
queue.push(root);
traverseLevel(queue);
}
public static void traverseLevel(Queue queue){
for(int i=0; i<queue.size(); i++){
TreeNode node = (TreeNode)queue.pop();
visit(node);
if(node.left != null)
queue.push(node.left);
if(node.right != null)
queue.push(node.right);
}
if(queue.size() > 0)
traverseLevel(queue);
}
private static void visit(TreeNode node) {
System.out.println(node.value);
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(null, null, 1);
TreeNode node2 = new TreeNode(null, node1, 2);
TreeNode node3 = new TreeNode(null, null, 3);
TreeNode node4 = new TreeNode(node2, node3, 4);
TreeNode node5 = new TreeNode(null, null, 5);
TreeNode root = new TreeNode(node4, node5, 0);
System.out.println("Tree Height is " + getTreeHeight(root));
System.out.println("Recurse In Order Traverse");
recurseInOrder(root);
System.out.println("Stack In Order Traverse");
stackInOrder(root);
System.out.println("Recurse Pre Order Traverse");
recursePreOrder(root);
System.out.println("Stack Pre Order Traverse");
stackPreOrder(root);
System.out.println("Width Traverse");
widthTraverse(root);
}
}
用LinkedList實現的Queue：
import java.util.EmptyStackException;
import java.util.LinkedList;
public class Queue {
private LinkedList list;
public Queue() {
this.list = new LinkedList();
}
public boolean empty() {
return list.isEmpty();
}
public Object peek() {
if (empty())
throw new EmptyStackException();
return list.getFirst();
}
public Object pop() {
if (empty())
throw new EmptyStackException();
return list.removeFirst();
}
public void push(Object o) {
list.add(o);
}
public int size(){
return list.size();
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.push(new Integer(1));
queue.push(new Integer(11));
queue.push(new Integer(1111));
queue.push(new Integer(22));
queue.push(new Integer(222));
queue.push(new Integer(31));
queue.push(new Integer(221));
while (!queue.empty()) {
System.out.println(queue.pop());
}
}
}
# re: [復習基礎]Java的二叉樹遍歷操作(遞歸, 非遞歸) 回復 更多評論
2007-09-02 14:36 by
我用generics 也寫了一個
|