当前位置：首页 > news >正文

Tree 底层源码实现（二叉树、递归、迭代）

news 2025/6/29 1:42:35

树（Tree）是一种非线性数据结构，由一组节点和它们之间的边组成。在树中，每个节点都有零个或多个子节点，除了根节点外，每个节点都有且仅有一个父节点。树可以被用于许多应用程序，如文件系统、XML文档、数据库索引和编译器语法树等。

二叉树

Java中的树可以通过节点类（Node Class）来实现，这个类通常包含节点的值、指向子节点的指针以及其他一些属性。
下面是一个示例代码，它实现了一个二叉树（Binary Tree）：

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

在这个示例中，TreeNode类包含一个整数值（val），以及左右子树的指针（left和right）。为了实现不同类型的树，可以在节点类中添加其他属性。

下面是一个示例代码，它实现了一个二叉搜索树（Binary Search Tree）：

class BSTNode {int val;BSTNode left;BSTNode right;BSTNode(int x) { val = x; }
}class BinarySearchTree {BSTNode root;public BinarySearchTree() {root = null;}public void insert(int value) {root = insert(root, value);}private BSTNode insert(BSTNode node, int value) {if (node == null) {return new BSTNode(value);}if (value < node.val) {node.left = insert(node.left, value);} else if (value > node.val) {node.right = insert(node.right, value);}return node;}
}

在这个示例中，BinarySearchTree类是一个包含BSTNode节点的根节点的类。insert方法用于将值插入到树中。在这个实现中，如果要插入的值小于节点的值，则将值插入左子树中；如果要插入的值大于节点的值，则将值插入右子树中。如果节点为空，则将新值插入该位置。

递归方法

在Java中，树的实现可以使用递归方法（Recursion）或者迭代方法（Iteration）。下面是一些关于树的递归方法的示例代码：

前序遍历（Preorder Traversal）

public void preOrderTraversal(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}
}

中序遍历（Inorder Traversal）

public void inOrderTraversal(TreeNode root) {if (root != null) {inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}
}

后序遍历（Postorder Traversal）

public void postOrderTraversal(TreeNode root) {if (root != null) {postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}
}

以上方法都是通过递归实现的，它们在遍历树时将节点的值打印到控制台。在这些示例代码中，如果节点为空，则返回。

迭代方法

除了递归方法之外，Java中还可以使用迭代方法实现树的遍历。下面是一个示例代码，它实现了二叉树的中序遍历（Inorder Traversal）：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();res.add(curr.val);curr = curr.right;}return res;
}