二叉树每个节点最多有两个子树，并且子树有左右之分，其次序不能任意颠倒
java 实现二叉树
public class BinaryTree {
private BiNode root;
public BinaryTree(BiNode root) {
this.root = root;
}
static class BiNode {
char data;
BiNode left;
BiNode right;
public BiNode(char data) {
this.data = data;
}
}
遍历二叉树
- 前序遍历 访问根结点，先序遍历左子树，先序遍历右子树
- 中序遍历 中序遍历左子树，访问根结点，中序遍历右子树
- 后序遍历 后序遍历左子树，后序遍历右子树，访问根结点
二叉树的遍历可以使用递归的算法实习，也可以使用非递归的算法实现
递归遍历
递归遍历算法比较简单直接按照定义递归即可，代码如下：
/**
* Recursive implementation of preOrder traversal
*/
public void perOrderTraverseRecursive() {
System.out.println("perOrderTraverseRecursive:");
perOrderTraverseRecursive(root);
System.out.println();
}
private void perOrderTraverseRecursive(BiNode node) {
if (node != null) {
visit(node);
perOrderTraverseRecursive(node.left);
perOrderTraverseRecursive(node.right);
}
}
/**
* Recursive implementation of inOrder traversal
*/
public void inOrderTraverseRecursive() {
System.out.println("inOrderTraverseRecursive:");
inOrderTraverseRecursive(root);
System.out.println();
}
private void inOrderTraverseRecursive(BiNode node) {
if (node != null) {
inOrderTraverseRecursive(node.left);
visit(node);
inOrderTraverseRecursive(node.right);
}
}
/**
* Recursive implementation of postOrder traversal
*/
public void postOrderTraverseRecursive() {
System.out.println("postOrderTraverseRecursive:");
postOrderTraverseRecursive(root);
System.out.println();
}
private void postOrderTraverseRecursive(BiNode node) {
if (node != null) {
postOrderTraverseRecursive(node.left);
postOrderTraverseRecursive(node.right);
visit(node);
}
}
非递归的遍历算法
非递归的遍历算法使用Stack实现，其中前序遍历和中序遍历相对来说比较简单，结构也类似
代码如下：
/**
* Stack implementation of preOrder traversal
*/
public void preOrderTraverse() {
System.out.println("preOrder Traverse use Stack:");
Stack<BiNode> nodeStack = new Stack<>();
BiNode node = root;
while (!nodeStack.isEmpty() || node != null) {
while (node != null) {
visit(node);
nodeStack.push(node);
node = node.left;
}
if (!nodeStack.isEmpty()) {
node = nodeStack.pop();
node = node.right;
}
}
System.out.println();
}
/**
* Stack implementation of inOrder traversal
*/
public void inOrderTraverse() {
System.out.println("inOrder Traverse use Stack:");
Stack<BiNode> nodeStack = new Stack<>();
BiNode node = root;
while (!nodeStack.isEmpty() || node != null) {
while (node != null) {
nodeStack.push(node);
node = node.left;
}
if (!nodeStack.isEmpty()) {
node = nodeStack.pop();
visit(node); //访问根结点
node = node.right;
}
}
System.out.println();
}
后序遍历的非递归算法麻烦一点，如下给出了后序遍历的两个实现，其中第一个使用一个栈完成，但是逻辑看起来复杂一些，后一个使用两个栈完成，逻辑看起来比较简洁
/**
* Stack implementation of postOrder traversal
*/
public void postOrderTraverse() {
System.out.println("postOrder Traverse use Stack:");
BiNode node = root;
if (node != null) {
Stack<BiNode> stack = new Stack<>();
stack.push(node);
BiNode c;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && node != c.left && node != c.right) {
stack.push(c.left);
} else if (c.right != null && node != c.right) {
stack.push(c.right);
} else {
visit(stack.pop());
node = c;
}
}
}
System.out.println();
}
/**
* Double Stack implementation of postOrder traversal
*/
public void postOrderTraverseWithDoubleStack() {
System.out.println("postOrderTraverse use Double Stack:");
BiNode node = root;
if (node != null) {
Stack<BiNode> s1 = new Stack<>();
Stack<BiNode> s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty()) {
node = s1.pop();
s2.push(node);
if (node.left != null) {
s1.push(node.left);
}
if (node.right != null) {
s1.push(node.right);
}
}
while (!s2.isEmpty()) {
visit(s2.pop());
}
}
System.out.println();
}
创建二叉树
我们根据先序遍历的字符串创建二叉树，使用#表示空指针
比如AB##DE##C#F## 会创建如下一个二叉树:
二叉树创建的代码如下：
/**
* @param s preOrder string represent of Binary Tree， # mean nil
* @return Binary Tree construct by the preOrder string
*/
public static BinaryTree createBiTree(String s) {
System.out.println("createBiTree with preOrder String : " + s);
i = 0;
return new BinaryTree(BinaryTree.createBiTreeNode(s));
}
private static BiNode createBiTreeNode(String s) {
BiNode node = null;
if (s.charAt(i) != '#') {// char is not #， do recursion
node = new BiNode(s.charAt(i));
i++; // when successful create a BiNode ,increase string index
node.left = createBiTreeNode(s);
node.right = createBiTreeNode(s);
} else {// Character # encountered, increase string index
i++;
}
return node;
}
创建二叉树并测试
public static void main(String[] args) {
BinaryTree binaryTree = createBiTree("AB##DE##C#F##");
binaryTree.perOrderTraverseRecursive();
binaryTree.inOrderTraverseRecursive();
binaryTree.postOrderTraverseRecursive();
binaryTree.preOrderTraverse();
binaryTree.inOrderTraverse();
binaryTree.postOrderTraverse();
binaryTree.postOrderTraverseWithDoubleStack();
}
测试结果
createBiTree with preOrder String : AB##DE##C#F##
perOrderTraverseRecursive:
A B D E C F
inOrderTraverseRecursive:
B A E D C F
postOrderTraverseRecursive:
B E F C D A
preOrder Traverse use Stack:
A B D E C F
inOrder Traverse use Stack:
B A E D C F
postOrder Traverse use Stack:
B E F C D A
postOrderTraverse use Double Stack:
B E F C D A
完整代码地址
https://github.com/spraysss/data-structure/blob/master/src/main/java/com/ds/tree/BinaryTree.java
网友评论