java 实现二叉树【递归/非递归】
最近想把数据结构/算法 再重新好好学习下，大学时候根本没心思学习，也可以说事现学的吧。呵呵，二叉树的介绍就不多说了，直接上代码吧，在代码上加说明。
1. 二叉树结构:
2. 代码实现
public class BinaryTree {
private Node root = null;
BinaryTree(){
root = new Node(1,"A");
}
public void createBinaryTree(){
Node nodeB = new Node(2,"B");
Node nodeC = new Node(3,"C");
Node nodeD = new Node(4,"D");
Node nodeE = new Node(5,"E");
Node nodeF = new Node(6,"F");
Node nodeG = new Node(7,"G");
Node nodeJ = new Node(8,"J");
root.leftChild = nodeB;
root.rightChild = nodeC;
root.leftChild.leftChild = nodeD;
root.leftChild.rightChild = nodeG;
root.leftChild.rightChild.leftChild = nodeJ;
root.rightChild.rightChild = nodeE;
root.rightChild.rightChild.leftChild = nodeF;
}
// 递归计算节点数
public int size(Node root){
if(root == null){
return 0;
}
return 1 + size(root.leftChild) + size(root.rightChild);
}
//递归计算高度
public int height(Node root){
if(root == null){
return 0;
}
int i = height(root.leftChild);
int j = height(root.rightChild);
return i > j ? i + 1 : j + 1;
}
//递归实现先序遍历
public void preOrder(Node root){
if(root != null){
visited(root);
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
//递归实现中序遍历
public void inOrder(Node root){
if(root != null){
inOrder(root.leftChild);
visited(root);
inOrder(root.rightChild);
}
}
//递归实现后续遍历
public void postOrder(Node root){
if(root != null){
postOrder(root.leftChild);
postOrder(root.rightChild);
visited(root);
}
}
//非递归实现先序遍历
public void preNoRecOrder(Node root){
Stack<Node> stack = new Stack<Node>();
Node node = root;
while(node != null || stack.size() != 0){
while(node != null){ // root节点和左子节点入栈
visited(node); //由于先序， 所以输出根节点
stack.push(node);
node = node.leftChild;
}
while(stack.size() > 0){
node = stack.pop();
node = node.rightChild;
if(node != null){// 当后入栈的节点有右子节点，则需要对此节点进行遍历
break;
}
}
}
}
//非递归实现中序遍历
public void inNoRecOrder(Node root){
Stack<Node> stack = new Stack<Node>();
Node node = root;
while(node != null || stack.size() > 0){
while(node != null){ // 左子节点入栈
stack.push(node);
node = node.leftChild;
}
while(stack.size() > 0){
node = stack.pop();
visited(node);
node = node.rightChild;
if(node != null){ // 最后入栈的左子节点有右子节点的话需要对该节点进行遍历
break;
}
}
}
}
public void postNoRecOrder(Node root){
Stack<Node> stack = new Stack<Node>();
Node node = root;
Node printNode = null;
while(node != null){
// 左子点入栈
while(node != null){
stack.push(node);
node = node.leftChild;
}
while(stack.size() > 0 ){
node = stack.pop();
// 输出栈中的节点，也是上一层的根节点，所以当右子节点为空 或者右子节点已经输出 所以输出该节点
if(node.rightChild == null || node.rightChild == printNode){
visited(node);
printNode = node;
if(stack.isEmpty()){//当栈为空时 程序结束，否则 重复输出，可以试试，哈哈 开始我就是不停输出
return;
}
}else{
if(node.rightChild != printNode){
stack.push(node);
node = node.rightChild;
break;
}
}
}
}
}
public void visited(Node node){
System.out.println("key = " + node.key + " ; value = " + node.value);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.createBinaryTree();
System.out.println("节点数: " + tree.size(tree.root));
System.out.println("深度 ： " + tree.height(tree.root));
System.out.println(" =====先序遍历 递归===");
tree.preOrder(tree.root);
System.out.println(" =====先序遍历 非递归=== ");
tree.preNoRecOrder(tree.root);
System.out.println(" =====中序遍历 递归=== ");
tree.inOrder(tree.root);
System.out.println(" =====中序遍历 非递归=== ");
tree.inNoRecOrder(tree.root);
System.out.println(" =====后序遍历 递归=== ");
tree.postOrder(tree.root);
System.out.println(" =====后序遍历 非递归=== ");
tree.postNoRecOrder(tree.root);
}
class Node{
private int key;
private String value;
private Node leftChild;
private Node rightChild;
Node(int key,String value){
this.key = key;
this.value = value;
}
}
}
输出结果：
节点数: 8
深度 ： 4
=====先序遍历 递归===
key = 1 ; value = A
key = 2 ; value = B
key = 4 ; value = D
key = 7 ; value = G
key = 8 ; value = J
key = 3 ; value = C
key = 5 ; value = E
key = 6 ; value = F
=====先序遍历 非递归===
key = 1 ; value = A
key = 2 ; value = B
key = 4 ; value = D
key = 7 ; value = G
key = 8 ; value = J
key = 3 ; value = C
key = 5 ; value = E
key = 6 ; value = F
=====中序遍历 递归===
key = 4 ; value = D
key = 2 ; value = B
key = 8 ; value = J
key = 7 ; value = G
key = 1 ; value = A
key = 3 ; value = C
key = 6 ; value = F
key = 5 ; value = E
=====中序遍历 非递归===
key = 4 ; value = D
key = 2 ; value = B
key = 8 ; value = J
key = 7 ; value = G
key = 1 ; value = A
key = 3 ; value = C
key = 6 ; value = F
key = 5 ; value = E
=====后序遍历 递归===
key = 4 ; value = D
key = 8 ; value = J
key = 7 ; value = G
key = 2 ; value = B
key = 6 ; value = F
key = 5 ; value = E
key = 3 ; value = C
key = 1 ; value = A
=====后序遍历 非递归===
key = 4 ; value = D
key = 8 ; value = J
key = 7 ; value = G
key = 2 ; value = B
key = 6 ; value = F
key = 5 ; value = E
key = 3 ; value = C
key = 1 ; value = A
3. 总结：
对于递归的算法，其实就是不断递归下去，一直到无子节点的时候return，然后层层往上return，最后算出结果，当我们不好理解时，就当成只有一个两层的二叉树，来理解相对容易些。
对于非递归的算法，主要是思想是 把左子节点入栈，一直到最下面的那一层，然后stack栈 从下往上pop出来，这时我们根据遍历顺序，来进行相应的输出即可。
如果还有更好的算法，欢迎交流