二叉树一直面试中的重头戏，所以需要我们在二叉树上花很多时间去掌握它。我先实现二叉树的基本操作，后面再去探究它深层次的东西。
本次实现了二叉树的创建、前序、中序、后序、层次遍历，及打印二叉树。打印二叉树的路径还没有实现。后面再补。
下面是实现代码：
先定义接口：
package com.guobing.tree;
public interface Tree_Interface {
final String [] mode = {"preOrder", "inOrder", "postOrder", "levelOrder"};
boolean createBTree(String gt);
boolean isEmpty();
void traverseBTree(String s);
Object findBTree(BTreeNode rt, Object obj);
int depthBTree(BTreeNode rt);
int countBTree(BTreeNode rt);
void printBTree(BTreeNode rt);
void clearBTree();
void init(BTreeNode bt);
}
下面是实现代码：
package com.guobing.tree;
import com.guobing.queue.Queue;
import com.guobing.stack.LinkedStack;
/**
* @function 二叉树的链式存储结构和操作实现
* @author guobing
*
*/
public class LinkBinaryTree implements Tree_Interface {
public BTreeNode root; //定义树根指针
/**
* 清空二叉树
*/
@Override
public void clearBTree() {
root = null;
}
/**
* 求二叉树的结点
*/
@Override
public int countBTree(BTreeNode rt) {
if(rt == null)
return 0;
else
return countBTree(rt.left) + countBTree(rt.right) + 1;
}
@Override
public boolean createBTree(String gt) {
LinkedStack ls = new LinkedStack();
ls.initStack();
root = null;
BTreeNode p = null;
int k = 1;
char [] a = gt.toCharArray();
for(int i = 0; i<a.length; i++) {
switch(a[i]) {
case ' ':
break;
case '(':
ls.push(p);
k = 1;
break;
case ')':
if(ls.isEmpty()) {
System.out.println("二叉树广义表字符串出错，返回假");
return false;
}
ls.pop();
break;
case ',':
k = 2;
break;
default:
if((a[i]>= 'a' && a[i] <= 'z') || (a[i] >= 'A' && a[i] <= 'Z')) {
p = new BTreeNode(a[i]);
if(root == null)
root = p;
else {
if(k == 1)
((BTreeNode)ls.peek()).left = p;
else((BTreeNode)ls.peek()).right = p;
}
}
else {
System.out.println("二叉树广义表中存在非法字符，返回假！");
return false;
}
}
}
if(ls.isEmpty())
return true;
else
return false;
}
/**
* 计算二叉树深度
*/
@Override
public int depthBTree(BTreeNode rt) {
if(root == null)
return 0;
else {
int dep1 = depthBTree(rt.left);
int dep2 = depthBTree(rt.right);
if(dep1 > dep2)
return dep1 + 1;
else return dep2 + 1;
}
}
/**
* 查询二叉树
*/
@Override
public Object findBTree(BTreeNode rt, Object obj) {
if(rt == null)
return null;
else {
if(rt.element.equals(obj)) {
return rt.element;
}else {
Object y;
y = findBTree(rt.left, obj);
if(y != null)
return y;
y = findBTree(rt.right, obj);
if(y != null)
return y;
}
}
return null;
}
/**
* 判断二叉树是否为空
*/
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
/**
* 打印二叉树
*/
@Override
public void printBTree(BTreeNode rt) {
if(rt != null)
System.out.println(rt.element);
if(rt.left != null || rt.right != null) {
System.out.println("(");
printBTree(rt.left);
if(rt.right != null) {
System.out.println(",");
printBTree(rt.right);
System.out.println(")");
}
}
}
/**
* 遍历二叉树
*/
@Override
public void traverseBTree(String s) {
if(s.equals(mode[0]))
preOrder(root);
if(s.equals(mode[1]))
inOrder(root);
if(s.equals(mode[2]))
postOrder(root);
if(s.equals(mode[3]))
levelOrder(root);
System.out.println();
}
/**
* 先序遍历算法
*/
private void preOrder(BTreeNode rt) {
if(rt != null) {
System.out.print(rt.element + " ");
preOrder(rt.left);
preOrder(rt.right);
}
}
/**
* 中序遍历算法
*/
private void inOrder(BTreeNode rt) {
if(rt != null) {
inOrder(rt.left);
System.out.print(rt.element + " ");
inOrder(rt.right);
}
}
/**
* 后序遍历算法
*/
private void postOrder(BTreeNode rt) {
if(rt != null) {
postOrder(rt.left);
postOrder(rt.right);
System.out.print(rt.element + " ");
}
}
/**
* 层次遍历算法
*/
private void levelOrder(BTreeNode rt) {
Queue qu = new Queue();
qu.init();
BTreeNode p = null;
qu.enter(rt);
while(!qu.isEmpty()) {
p = (BTreeNode)qu.leave();
System.out.print(p.element + "");
if(p.left != null)
qu.enter(p.left);
if(p.right != null)
qu.enter(p.right);
}
}
/**
* 初始化二叉树
*/
@Override
public void init(BTreeNode bt) {
root = bt;
}
public static void main(String [] args) {
LinkBinaryTree lb = new LinkBinaryTree();
BTreeNode bn = new BTreeNode("a");
lb.init(bn);
String s = "a(b(c),d(e(f, g),h(,i)))";
boolean bol = lb.createBTree(s);
if(!bol) {
System.out.println("表示二叉树的字符串有误，退出运行");
System.exit(1);
}
System.out.print("广义表形式：");
lb.printBTree(bn);
System.out.print("先序：");lb.traverseBTree("preOrder");
System.out.print("中序：");lb.traverseBTree("inOrder");
System.out.print("后序：");lb.traverseBTree("postOrder");
System.out.print("层次遍历：");lb.traverseBTree("levelOrder");
}
}
/**
* @function 二叉树结点的定义，链式存储结构
* @author guobing
*/
class BTreeNode {
Object element;
BTreeNode left, right;
public BTreeNode(Object obj) {
this.element = obj;
left = right = null;
}
public BTreeNode(Object obj, BTreeNode lt, BTreeNode rt) {
this.element = obj;
this.left = lt;
this.right = rt;
}
}
/**
* @function： 二叉树结点的定义 ，顺序存储结构
* @warning 不适合存储单支结点较多的二叉树，会引起存储空间的浪费
* @author guobing
*/
class ArrayBTreeNode {
Object element;
int left, right;
public ArrayBTreeNode(Object obj) {
this.element = obj;
left = right = 0;
}
public ArrayBTreeNode(Object obj, int lt, int rt) {
this.element = obj;
this.left = lt;
this.right = rt;
}
}
测试结果：
当前栈顶元素的值为：com.guobing.tree.BTreeNode@150bd4d 当前栈顶元素的值为：com.guobing.tree.BTreeNode@1bc4459 当前栈顶元素的值为：com.guobing.tree.BTreeNode@150bd4d 当前栈顶元素的值为：com.guobing.tree.BTreeNode@12b6651 当前栈顶元素的值为：com.guobing.tree.BTreeNode@4a5ab2 当前栈顶元素的值为：com.guobing.tree.BTreeNode@4a5ab2 当前栈顶元素的值为：com.guobing.tree.BTreeNode@12b6651 当前栈顶元素的值为：com.guobing.tree.BTreeNode@1888759 广义表形式：a 先序：a b c d e f g h i 中序：c b a f e g d h i 后序：c b f g e i h d a 层次遍历：首元素出队列：com.guobing.tree.BTreeNode@150bd4d a首元素出队列：com.guobing.tree.BTreeNode@1bc4459 b首元素出队列：com.guobing.tree.BTreeNode@12b6651 d首元素出队列：com.guobing.tree.BTreeNode@f62373 c首元素出队列：com.guobing.tree.BTreeNode@4a5ab2 e首元素出队列：com.guobing.tree.BTreeNode@1888759 h首元素出队列：com.guobing.tree.BTreeNode@19189e1 f首元素出队列：com.guobing.tree.BTreeNode@1f33675 g首元素出队列：com.guobing.tree.BTreeNode@7c6768 i
完毕！