-
二叉树遍历（递归）
添加时间:2013-5-4 点击量:// 测试二叉树遍历，递归算法
public class TestBinaryTree {
public static void main（String[] args） {
Node<String> g = new Node<String>（G， null， null）；
Node<String> e = new Node<String>（E， null， null）；
Node<String> f = new Node<String>（F， null， null）；
Node<String> d = new Node<String>（D， null， g）；
Node<String> b = new Node<String>（B， d， e）；
Node<String> c = new Node<String>（C， null， f）；
Node<String> a = new Node<String>（A， b， c）；
System.out.println（生成的二叉树：）；
System.out.println（ A）；
System.out.println（ | ）；
System.out.println（ |---------|）；
System.out.println（ B C）；
System.out.println（ | |）；
System.out.println（ |---------| -----|）；
System.out.println（ D E F）；
System.out.println（ |）；
System.out.println（ ----|）；
System.out.println（ G）；
System.out.println（二叉树深度： + BinaryTree.getDepth（a））；
System.out.print（前序遍历：）；
BinaryTree.priorderTraversal（a）；
System.out.println（）；
System.out.print（中序遍历：）；
BinaryTree.inorderTraversal（a）；
System.out.println（）；
System.out.print（后序遍历：）；
BinaryTree.postorderTraversal（a）；
System.out.println（）；
}
}
// 二叉树
class BinaryTree {
// 前序遍历
static <T> void priorderTraversal（Node<T> node） {
if （node != null） {
visitNode（node）；
priorderTraversal（node.getLeftChild（））；
priorderTraversal（node.getRightChild（））；
}
}
// 中序遍历
static <T> void inorderTraversal（Node<T> node） {
if （node != null） {
inorderTraversal（node.getLeftChild（））；
visitNode（node）；
inorderTraversal（node.getRightChild（））；
}
}
// 后序遍历
static <T> void postorderTraversal（Node<T> node） {
if （node != null） {
postorderTraversal（node.getLeftChild（））；
postorderTraversal（node.getRightChild（））；
visitNode（node）；
}
}
// 二叉树深度
static <T> int getDepth（Node<T> node） {
if （node == null） {
return 0;
}
int leftDepth = 0;
int rightDepth = 0;
leftDepth = getDepth（node.getLeftChild（））；
rightDepth = getDepth（node.getRightChild（））；
return （leftDepth > rightDepth ？ leftDepth : rightDepth） + 1;
}
// 接见节点
static <T> void visitNode（Node<T> node） {
System.out.print（node.getKey（） + ）；
}
}
// 节点
class Node<T> {
private T key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node（） {
}
public Node（T key， Node<T> leftChild， Node<T> rightChild） {
super（）； www.2cto.com
this.key = key;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public T getKey（） {
return key;
}
public void setKey（T key） {
this.key = key;
}
public Node<T> getLeftChild（） {
return leftChild;
}
public void setLeftChild（Node<T> leftChild） {
this.leftChild = leftChild;
}
public Node<T> getRightChild（） {
return rightChild;
}
public void setRightChild（Node<T> rightChild） {
this.rightChild = rightChild;
}
}
输出成果：
所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
生成的二叉树：
A
|
|---------|
B C
| |
|---------| -----|
D E F
|
----|
G
二叉树深度：4
前序遍历：A B D G E C F
中序遍历：D G B E A C F
后序遍历：G D E B F C A
