# 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进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
