Java数据结构二叉树难点解析
什么是二叉树
二叉树是一种非常常见的数据结构，它具有以下特点：
- 每个节点都最多有两个子节点。
- 左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。
二叉树可以用递归的方式实现，如下所示：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTree {
public TreeNode root;
public void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else {
node.right = insert(node.right, val);
}
return node;
}
}
二叉树遍历
二叉树遍历有三种方式：
前序遍历
前序遍历的顺序是：根节点，左子树，右子树。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
中序遍历
中序遍历的顺序是：左子树，根节点，右子树。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
后序遍历
后序遍历的顺序是：左子树，右子树，根节点。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
result.add(stack2.pop().val);
}
return result;
}
二叉树的应用
二叉树常常被用来实现搜索和排序算法。一个常见的例子是二叉搜索树，它支持快速插入，删除和查找操作，时间复杂度为O(log n)。
例如，我们可以使用二叉搜索树实现一个简单的数据管理系统，该系统支持以下操作：
- Add(key, value) 将一个key-value对添加到数据管理系统中。
- Remove(key) 从数据管理系统中删除key-value对。
- Get(key) 获取key对应的value。
下面是一个用Java实现的二叉搜索树：
class BSTNode {
int key;
String value;
BSTNode left;
BSTNode right;
public BSTNode(int key, String value) {
this.key = key;
this.value = value;
}
}
public class BinarySearchTree {
private BSTNode root;
public void add(int key, String value) {
root = add(root, key, value);
}
private BSTNode add(BSTNode node, int key, String value) {
if (node == null) {
return new BSTNode(key, value);
}
if (key < node.key) {
node.left = add(node.left, key, value);
} else if (key > node.key) {
node.right = add(node.right, key, value);
} else {
node.value = value;
}
return node;
}
public void remove(int key) {
root = remove(root, key);
}
private BSTNode remove(BSTNode node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = remove(node.left, key);
} else if (key > node.key) {
node.right = remove(node.right, key);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
BSTNode minNode = findMin(node.right);
node.key = minNode.key;
node.value = minNode.value;
node.right = remove(node.right, minNode.key);
}
}
return node;
}
private BSTNode findMin(BSTNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
public String get(int key) {
return get(root, key);
}
private String get(BSTNode node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
return get(node.left, key);
} else if (key > node.key) {
return get(node.right, key);
} else {
return node.value;
}
}
}
上述代码中，我们用二叉搜索树来管理key-value对，实现了Add，Remove，Get三个操作。例如，添加一个key-value对：
BinarySearchTree bst = new BinarySearchTree();
bst.add(1, "a");
示例说明
示例1
我们有一个如下图所示的二叉树：
1
/ \
2 3
/ \ / \
4 5 6 7
我们可以使用前序遍历和中序遍历的结果来重建这个二叉树：
- 前序遍历：1 2 4 5 3 6 7
- 中序遍历：4 2 5 1 6 3 7
其中，前序遍历的第一个节点是根节点，而中序遍历的根节点在中间。我们可以通过中序遍历找到根节点的位置，分别构建左子树和右子树，递归进行下去即可。
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
break;
}
}
root.left = buildTree(preorder, preStart + 1, preStart + inIndex - inStart, inorder, inStart, inIndex - 1);
root.right = buildTree(preorder, preStart + inIndex - inStart + 1, preEnd, inorder, inIndex + 1, inEnd);
return root;
}
示例2
我们有一个如下图所示的二叉树：
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
我们要求二叉树中和为8的路径。我们可以使用递归的方式，遍历整棵树，在遍历的同时将当前路径的和作为参数传入。如果当前节点是叶子节点并且路径和等于给定值，则打印当前路径，否则递归遍历左子树和右子树。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
List<Integer> path = new ArrayList<>();
pathSum(root, sum, path, result);
return result;
}
private void pathSum(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
if (node == null) {
return;
}
path.add(node.val);
sum -= node.val;
if (sum == 0 && node.left == null && node.right == null) {
result.add(new ArrayList<>(path));
}
pathSum(node.left, sum, path, result);
pathSum(node.right, sum, path, result);
path.remove(path.size() - 1);
}
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java数据结构二叉树难点解析 - Python技术站
微信扫一扫 
支付宝扫一扫 