有关树的一些基础知识点请参考【这篇文章】。
本文主要记录Java语言描述的二叉树相关的一些操作，如创建、遍历等。
首先，我们需要一个表示树中节点的数据结构TreeNode，代码如下：
public class TreeNode<T> {
public T data;
public TreeNode<T> lChild;
public TreeNode<T> rChild;
public TreeNode<T> parent;
public TreeNode() {
}
public TreeNode(T data) {
this.data = data;
this.lChild = null;
this.rChild = null;
this.parent = null;
}
public TreeNode(T data, TreeNode<T> parent, boolean isLeftC) {
this.data = data;
this.parent = parent;
if (isLeftC) {
parent.lChild = this;
} else {
parent.rChild = this;
}
}
}
在二叉树的工具类BinaryTree中，提供了很多的方法，详细介绍如下：
（1）创建二叉树的时候，通过传入的字符串来自动生成二叉树的结构。注意：字符串是前序遍历的结构，每个节点都有左右两个节点，如果某个节点为空，则用“#”符号表示；节点与节点之间用空格隔开。
（2）使用递归和非递归的方式进行二叉树的前、中、后序遍历的方法。
（3）对二叉树进行层序遍历的方法。
（4）获取树的深度和树中节点总数的方法。
以下是BinaryTree类中的详细代码：
public class BinaryTree {
private TreeNode<String> root;
private int size;
// 根据初始化字符串生成二叉树
public BinaryTree(String content) {
root = createBTree(new Scanner(content));
}
// 直接将一棵TreeNode树赋值为二叉树
public BinaryTree(TreeNode<String> root) {
this.root = root;
}
// 根据字符串创建二叉树
private TreeNode<String> createBTree(Scanner scanner) {
String data = scanner.next();
if ("#".equals(data)) return null;
TreeNode<String> node = new TreeNode<>(data);
size++;
node.lChild = createBTree(scanner);
node.rChild = createBTree(scanner);
return node;
}
// 获取二叉树的深度
public int getBTreeDepth() {
return getBTreeDepth(root);
}
private int getBTreeDepth(TreeNode root) {
return root == null ? 0 : Math.max(getBTreeDepth(root.lChild), getBTreeDepth(root.rChild)) + 1;
}
// 返回二叉树中节点个数
public int size() {
return size;
}
// 前序遍历二叉树（useRec：是否使用递归方式）
public void traverseBefore(boolean useRec) {
if (useRec) {
traverseBeforeRec(root);
} else {
traverseBeforeNonRec();
}
}
// 前序遍历二叉树（递归）
private void traverseBeforeRec(TreeNode node) {
if (node == null) {
System.out.print("#");
} else {
System.out.print(node.data);
traverseBeforeRec(node.lChild);
traverseBeforeRec(node.rChild);
}
}
// 前序遍历二叉树（非递归）
private void traverseBeforeNonRec() {
Stack<TreeNode<String>> stack = new Stack<>();
TreeNode<String> currRoot = root;
while (true) {
if (currRoot != null) {
System.out.print(currRoot.data);
stack.push(currRoot.rChild);
currRoot = currRoot.lChild;
} else {
System.out.print("#");
if (stack.size() == 0) break;
currRoot = stack.pop();
}
}
}
// 中序遍历二叉树
public void traverseMiddle(boolean useRec) {
if (useRec) {
traverseMiddleRec(root);
} else {
traverseMiddleNonRec();
}
}
// 中序遍历二叉树（递归）
private void traverseMiddleRec(TreeNode node) {
if (node == null) {
System.out.print("#");
} else {
traverseMiddleRec(node.lChild);
System.out.print(node.data);
traverseMiddleRec(node.rChild);
}
}
// 中序遍历二叉树（非递归）
private void traverseMiddleNonRec() {
Stack<TreeNode<String>> stack = new Stack<>();
TreeNode<String> currRoot = root;
while (true) {
if (currRoot != null) {
stack.push(currRoot);
currRoot = currRoot.lChild;
} else {
System.out.print("#");
if (stack.size() == 0) break;
TreeNode<String> middleNode = stack.pop();
System.out.print(middleNode.data);
currRoot = middleNode.rChild;
}
}
}
// 后序遍历二叉树
public void traverseAfter(boolean useRec) {
if (useRec) {
traverseAfterRec(root);
} else {
traverseAfterNonRec();
}
}
// 后序遍历二叉树（递归）
private void traverseAfterRec(TreeNode node) {
if (node == null) {
System.out.print("#");
} else {
traverseAfterRec(node.lChild);
traverseAfterRec(node.rChild);
System.out.print(node.data);
}
}
// 后序遍历二叉树（非递归）
private void traverseAfterNonRec() {
Stack<TreeNode<String>> stack = new Stack<>();
TreeNode<String> lastNode = null;
TreeNode<String> currRoot = root;
while (true) {
if (currRoot != null) {
if (lastNode != null && currRoot.rChild == lastNode) {
System.out.print(currRoot.data);
lastNode = currRoot;
currRoot = stack.peek().rChild;
if (root.rChild == currRoot && currRoot == lastNode) {
System.out.print(root.data);
break;
}
} else if (lastNode != null && currRoot.lChild == lastNode) {
if (currRoot.rChild == null) {
System.out.print("#" + currRoot.data);
lastNode = currRoot;
currRoot = stack.pop();
}
} else {
stack.push(currRoot);
currRoot = currRoot.lChild;
}
} else {
System.out.print("#");
currRoot = stack.peek().rChild;
if (currRoot == null) {
System.out.print("#");
lastNode = stack.pop();
System.out.print(lastNode.data);
currRoot = stack.pop();
}
}
}
}
// 层序遍历二叉树
public void traverseCeng() {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
System.out.print("#");
} else {
System.out.print(node.data);
queue.offer(node.lChild);
queue.offer(node.rChild);
}
}
}
}
测试类代码：
public class TestTree {
private static final String TREE_CONTENT = "A B D # G # # E # # C # F H # # #";
public static void main(String args[]) {
System.out.println("根据字符串" + TREE_CONTENT + "生成二叉树");
BinaryTree bTree = new BinaryTree(TREE_CONTENT);
System.out.print("二叉树前序遍历结果：");
bTree.traverseBefore(false);
System.out.print("\n二叉树中序遍历结果：");
bTree.traverseMiddle(false);
System.out.print("\n二叉树后序遍历结果：");
bTree.traverseAfter(false);
System.out.print("\n二叉树层序遍历结果：");
bTree.traverseCeng();
System.out.println("\n二叉树深度：" + bTree.getBTreeDepth());
System.out.println("二叉树中节点个数：" + bTree.size());
}
}
运行结果：
根据字符串A B D # G # # E # # C # F H # # #生成二叉树
二叉树前序遍历结果：ABD#G##E##C#FH###
二叉树中序遍历结果：#D#G#B#E#A#C#H#F#
二叉树后序遍历结果：###G##E###HFC
二叉树层序遍历结果：ABCDE#F#G##H#####
二叉树深度：4
二叉树中节点个数：8