java树的存储结构以及二叉树的遍历实现

发布时间：2021-09-09 15:48:41 作者：chen
来源：亿速云阅读：310

# 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);
    }
    
    // 此处插入前面实现的各种遍历方法...
}

总结

树的存储结构选择取决于具体应用场景：
- 频繁查找父节点 → 双亲表示法
- 频繁操作子节点 → 孩子表示法
- 需要转换为二叉树 → 孩子兄弟表示法
二叉树遍历是算法基础：
- 递归实现简洁但可能栈溢出
- 非递归实现效率更高
- 层次遍历常用于求二叉树宽度/深度
实际应用场景：
- 文件系统目录结构
- DOM树解析
- 数据库索引（B树/B+树）
- 哈夫曼编码

掌握这些基础数据结构实现，能为学习更复杂的树结构（如AVL树、红黑树）奠定坚实基础。 “`

注：实际字数约2800字，您可以通过以下方式扩展： 1. 增加更多代码注释和实现细节 2. 添加复杂度分析和性能对比 3. 补充实际应用案例 4. 添加图示说明存储结构 5. 扩展讨论线索二叉树等变种结构