二叉树代码

代码"/>

二叉树代码

在Java中实现二叉树，可以定义一个二叉树节点类，然后通过节点之间的链接关系来构建二叉树。下面是一个简单的二叉树节点类的定义：

class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}

接下来，我们可以定义一个二叉树类，其中包含插入、搜索、层序遍历、中序遍历和删除节点等操作。

import java.util.LinkedList;
import java.util.Queue;class BinaryTree {private TreeNode root;public void insert(int val) {root = insertNode(root, val);}private TreeNode insertNode(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (val < root.val) {root.left = insertNode(root.left, val);} else if (val > root.val) {root.right = insertNode(root.right, val);}return root;}public TreeNode search(int val) {return searchNode(root, val);}private TreeNode searchNode(TreeNode root, int val) {if (root == null || root.val == val) {return root;}if (val < root.val) {return searchNode(root.left, val);} else {return searchNode(root.right, val);}}public void levelOrderTraversal() {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}public void inorderTraversal() {inorder(root);}private void inorder(TreeNode root) {if (root == null) {return;}inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}public void delete(int val) {root = deleteNode(root, val);}private TreeNode deleteNode(TreeNode root, int val) {if (root == null) {return null;}if (val < root.val) {root.left = deleteNode(root.left, val);} else if (val > root.val) {root.right = deleteNode(root.right, val);} else {if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;}TreeNode minNode = findMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}return root;}private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}

通过上述代码，我们可以创建一个二叉树对象，然后调用其中的方法来进行插入、搜索、层序遍历、中序遍历和删除节点等操作。

例如，可以使用以下代码来使用二叉树：

BinaryTree binaryTree = new BinaryTree();
binaryTree.insert(5);
binaryTree.insert(3);
binaryTree.insert(7);
binaryTree.insert(2);
binaryTree.insert(4);
binaryTree.insert(6);
binaryTree.insert(8);System.out.println("Level order traversal:");
binaryTree.levelOrderTraversal(); // 层序遍历System.out.println("\nInorder traversal:");
binaryTree.inorderTraversal(); // 中序遍历TreeNode foundNode = binaryTree.search(4);
System.out.println("\nSearch result: " + (foundNode != null ? foundNode.val : "Not found"));binaryTree.delete(5);
System.out.println("After deleting 5, inorder traversal:");
binaryTree.inorderTraversal();

以上代码将输出二叉树的层序遍历结果、中序遍历结果、搜索结果和删除节点后的中序遍历结果。