# Java樹的存儲結構以及二叉樹的遍歷實現
## 目錄
1. [樹的基本概念](#樹的基本概念)
2. [樹的存儲結構](#樹的存儲結構)
- [雙親表示法](#雙親表示法)
- [孩子表示法](#孩子表示法)
- [孩子兄弟表示法](#孩子兄弟表示法)
3. [二叉樹的基本概念](#二叉樹的基本概念)
4. [二叉樹的存儲結構](#二叉樹的存儲結構)
- [順序存儲](#順序存儲)
- [鏈式存儲](#鏈式存儲)
5. [二叉樹的遍歷實現](#二叉樹的遍歷實現)
- [遞歸遍歷](#遞歸遍歷)
- [非遞歸遍歷](#非遞歸遍歷)
6. [完整代碼示例](#完整代碼示例)
7. [總結](#總結)
---
## 樹的基本概念
樹（Tree）是n（n≥0）個節點的有限集合。當n=0時稱為空樹，非空樹具有以下特點：
- 有且僅有一個根節點（Root）
- 其余節點可分為m（m≥0）個互不相交的子樹
基本術語：
- **度（Degree）**：節點的子樹數量
- **葉子節點（Leaf）**：度為0的節點
- **層次（Level）**：根節點為第1層，依次向下遞增
- **高度（Height）**：樹中節點的最大層次
---
## 樹的存儲結構
### 雙親表示法
用數組存儲節點，每個節點記錄其父節點索引。
```java
class ParentTreeNode<T> {
T data;
int parentIndex; // 父節點在數組中的位置
}
特點： - 查找父節點高效（O(1)） - 查找子節點需要遍歷整個數組
每個節點維護一個孩子鏈表。
class ChildTreeNode<T> {
T data;
List<ChildTreeNode<T>> children;
}
特點： - 查找子節點高效 - 查找父節點需要遍歷
將普通樹轉換為二叉樹形式： - 左指針：第一個孩子節點 - 右指針：兄弟節點
class CSNode<T> {
T data;
CSNode<T> firstChild; // 第一個孩子
CSNode<T> nextSibling; // 右兄弟
}
二叉樹是每個節點最多有兩個子樹的樹結構，子樹分為左子樹和右子樹。特殊類型包括： - 滿二叉樹：所有層都達到最大節點數 - 完全二叉樹：除最后一層外完全填充，且最后一層左對齊
性質： 1. 第i層最多有2^(i-1)個節點 2. 深度為k的二叉樹最多有2^k -1個節點 3. 對于任何二叉樹：葉子節點數 = 度為2的節點數 + 1
使用數組按層序存儲，適合完全二叉樹。
// 示例：存儲完全二叉樹
Object[] treeArray = new Object[10];
treeArray[0] = "A"; // 根節點
treeArray[1] = "B"; // 左孩子
treeArray[2] = "C"; // 右孩子
特點： - 非完全二叉樹會浪費存儲空間 - 通過下標計算父子關系： - 父節點索引 = (子節點索引-1)/2 - 左孩子索引 = 2*父節點索引+1 - 右孩子索引 = 2*父節點索引+2
使用節點對象通過指針鏈接。
class BinaryTreeNode<T> {
T data;
BinaryTreeNode<T> leftChild;
BinaryTreeNode<T> rightChild;
public BinaryTreeNode(T data) {
this.data = data;
}
}
void preOrder(BinaryTreeNode<T> root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
void inOrder(BinaryTreeNode<T> root) {
if (root != null) {
inOrder(root.leftChild);
System.out.print(root.data + " ");
inOrder(root.rightChild);
}
}
void postOrder(BinaryTreeNode<T> root) {
if (root != null) {
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + " ");
}
}
void preOrderNonRecursive(BinaryTreeNode<T> root) {
Stack<BinaryTreeNode<T>> stack = new Stack<>();
BinaryTreeNode<T> p = root;
while (p != null || !stack.isEmpty()) {
while (p != null) {
System.out.print(p.data + " ");
stack.push(p);
p = p.leftChild;
}
if (!stack.isEmpty()) {
p = stack.pop();
p = p.rightChild;
}
}
}
void inOrderNonRecursive(BinaryTreeNode<T> root) {
Stack<BinaryTreeNode<T>> stack = new Stack<>();
BinaryTreeNode<T> p = root;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.leftChild;
}
if (!stack.isEmpty()) {
p = stack.pop();
System.out.print(p.data + " ");
p = p.rightChild;
}
}
}
void postOrderNonRecursive(BinaryTreeNode<T> root) {
Stack<BinaryTreeNode<T>> stack = new Stack<>();
BinaryTreeNode<T> p = root, lastVisited = null;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.leftChild;
}
p = stack.peek();
if (p.rightChild == null || p.rightChild == lastVisited) {
System.out.print(p.data + " ");
lastVisited = stack.pop();
p = null;
} else {
p = p.rightChild;
}
}
}
void levelOrder(BinaryTreeNode<T> root) {
Queue<BinaryTreeNode<T>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BinaryTreeNode<T> node = queue.poll();
System.out.print(node.data + " ");
if (node.leftChild != null) {
queue.offer(node.leftChild);
}
if (node.rightChild != null) {
queue.offer(node.rightChild);
}
}
}
import java.util.*;
public class BinaryTree<T> {
static class Node<T> {
T data;
Node<T> left;
Node<T> right;
public Node(T data) {
this.data = data;
}
}
// 構建示例二叉樹
public Node<String> buildSampleTree() {
Node<String> root = new Node<>("A");
root.left = new Node<>("B");
root.right = new Node<>("C");
root.left.left = new Node<>("D");
root.left.right = new Node<>("E");
root.right.right = new Node<>("F");
return root;
}
// 測試方法
public static void main(String[] args) {
BinaryTree<String> tree = new BinaryTree<>();
Node<String> root = tree.buildSampleTree();
System.out.println("遞歸前序遍歷:");
tree.preOrder(root);
System.out.println("\n非遞歸中序遍歷:");
tree.inOrderNonRecursive(root);
System.out.println("\n層次遍歷:");
tree.levelOrder(root);
}
// 此處插入前面實現的各種遍歷方法...
}
樹的存儲結構選擇取決于具體應用場景：
二叉樹遍歷是算法基礎：
實際應用場景：
掌握這些基礎數據結構實現，能為學習更復雜的樹結構（如AVL樹、紅黑樹）奠定堅實基礎。 “`
注：實際字數約2800字，您可以通過以下方式擴展： 1. 增加更多代碼注釋和實現細節 2. 添加復雜度分析和性能對比 3. 補充實際應用案例 4. 添加圖示說明存儲結構 5. 擴展討論線索二叉樹等變種結構
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
