GitHub源碼分享
項目主頁：https://github.com/gozhuyinglong/blog-demos
本文源碼：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures
1. 二叉樹（Binary Tree）
二叉樹是一棵特殊的樹，其結(jié)構(gòu)簡單但很重要。二叉樹的特點是每個節(jié)點最多有兩棵子樹，并且有左右之分。
- 滿二叉樹
如果一棵二叉樹的所有葉子節(jié)點都在最后一層，稱為滿二叉樹。滿二叉樹的結(jié)點總數(shù) =（n為層數(shù)）。如下圖二叉是的層數(shù)為3，其結(jié)點總數(shù)為
滿二叉樹
- 完全二叉樹
一棵深度為k的有n個結(jié)點的二叉樹，對樹中的節(jié)點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。顯示下圖中a和b是完全二叉樹，而c不是完全二叉樹（倒數(shù)第二層不連續(xù)）
完全二叉樹
小結(jié)：一棵滿二叉樹一定是一棵完全二叉樹；而一棵完全二叉樹不一定是滿二叉樹。
2. 二叉樹的五種形態(tài)
二叉樹是遞歸定義的，其節(jié)點有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：
二叉樹的五種形態(tài)
- 空二叉樹（圖a）
- 只有一個根節(jié)點的二叉樹（圖b）
- 只有左子樹（圖c）
- 只有右子樹（圖d）
- 完全二叉樹（圖e）
3. 二叉樹的遍歷（前序、中序、后序）
- 前序遍歷：先輸出父節(jié)點，再遍歷左子樹，最后遍歷右子樹。
- 中序遍歷：先遍歷左子樹，再輸出父節(jié)點，最后遍歷右子樹。
- 后序遍歷：先遍歷左子樹，再遍歷右子樹，最后輸出父節(jié)點。
小結(jié)：用輸出父節(jié)點的順序來判斷是前序、中序還是后序遍歷
4. 代碼實現(xiàn)
通過Java代碼實現(xiàn)下圖中二叉樹，并通過三種方式遍歷該二叉樹（前序、中序、后序）。
二叉樹
Node類為節(jié)點類，其中element表示節(jié)點元素，left為左子節(jié)點，right為右子節(jié)點。
BinaryTree類實現(xiàn)二叉樹的具體操作，如前序遍歷、中序遍歷、后序遍歷。
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");
Node h = new Node("H");
Node i = new Node("I");
tree.setRoot(a);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
d.left = h;
c.left = f;
c.right = g;
g.right = i;
System.out.println("---------------前序遍歷");
tree.preOrder();
System.out.println("---------------中序遍歷");
tree.inOrder();
System.out.println("---------------后序遍歷");
tree.postOrder();
}
private static class BinaryTree {
private Node root; // 根
public void setRoot(Node root) {
this.root = root;
}
/**
* 前序遍歷
*/
public void preOrder() {
preOrder(root, 0);
}
/**
* 前序遍歷
*
* @param node
* @param depth 層級（用于輔助輸出）
*/
public void preOrder(Node node, int depth) {
if (node == null) {
return;
}
// 輸出當(dāng)前節(jié)點
this.print(node, depth);
// 遞歸左子節(jié)點
if (node.left != null) {
preOrder(node.left, depth + 1);
}
// 遞歸右子節(jié)點
if (node.right != null) {
preOrder(node.right, depth + 1);
}
}
/**
* 中序遍歷
*/
public void inOrder() {
inOrder(root, 0);
}
/**
* 中序遍歷
*
* @param node
* @param depth 層級（用于輔助輸出）
*/
public void inOrder(Node node, int depth) {
if (node == null) {
return;
}
// 遞歸左子節(jié)點
if (node.left != null) {
inOrder(node.left, depth + 1);
}
// 輸出當(dāng)前節(jié)點
this.print(node, depth);
// 遞歸右子節(jié)點
if (node.right != null) {
inOrder(node.right, depth + 1);
}
}
/**
* 后序遍歷
*/
public void postOrder() {
postOrder(root, 0);
}
/**
* 后序遍歷
*
* @param node
* @param depth 層級（用于輔助輸出）
*/
public void postOrder(Node node, int depth) {
if (node == null) {
return;
}
// 遞歸左子節(jié)點
if (node.left != null) {
postOrder(node.left, depth + 1);
}
// 遞歸右子節(jié)點
if (node.right != null) {
postOrder(node.right, depth + 1);
}
// 輸出當(dāng)前節(jié)點
this.print(node, depth);
}
/**
* 按照層級輸出節(jié)點元素
*
* @param node
* @param depth
*/
private void print(Node node, int depth) {
StringBuilder t = new StringBuilder();
for (int i = 0; i < depth; i++) {
t.append("\t");
}
System.out.printf("%s%s\n", t.toString(), node.element);
}
}
private static class Node {
private final Object element; // 節(jié)點元素
private Node left; // 左子節(jié)點
private Node right; // 右子節(jié)點
public Node(Object element) {
this.element = element;
}
}
}
輸出結(jié)果：
---------------前序遍歷
A
B
D
H
E
C
F
G
I
---------------中序遍歷
H
D
B
E
A
F
C
G
I
---------------后序遍歷
H
D
E
B
F
I
G
C
A
獲取更多內(nèi)容
微信搜索：碼農(nóng)StayUp
個人主頁：https://gozhuyinglong.github.io
