java实现二叉树

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class MyBiTree {
private Node root;

public class Node{
char data;
Node left;
Node right;
Node(char data){
this.data = data;
left = null;
right = null;
}
}
}

操作

前中序列构建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 根据 前 中 序列 构建二叉树
public Node build(String preOrder,String inOrder){
if(preOrder.isEmpty())
return null;
char rootValue = preOrder.charAt(0);
int rootIndex = inOrder.indexOf(rootValue);

Node root = new Node(rootValue);
root.left = build(
preOrder.substring(1,1+rootIndex),
inOrder.substring(0,rootIndex)
);
root.right = build(
preOrder.substring(1+rootIndex),
inOrder.substring(1+rootIndex)
);

return root;
}

递归前序遍历

1
2
3
4
5
6
7
public void preOrder(Node root){
if(root != null){
System.out.print(root.data+" ");
preOrder(root.left);
preOrder(root.right);
}
}

递归后续遍历

1
2
3
4
5
6
7
public void afterOrder(Node root){
if(root != null){
afterOrder(root.left);
afterOrder(root.right);
System.out.print(root.data+" ");
}
}