|
|
Posted on 2006-12-29 13:01 Hexise 阅读(4410) 评论(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 也写了一个
|