二叉排序树的构建与遍历

二叉排序树是一种特殊的二叉树，它的每个节点都满足：左子树所有节点值小于当前节点，右子树所有节点值大于当前节点。

一、二叉排序树的核心结构

首先定义树节点TreeNode，包含左孩子、右孩子和节点值：

public class TreeNode { public TreeNode lChild; public TreeNode rChild; public Integer data; public TreeNode(Integer data){ this.data = data; } }

二、二叉排序树的构建（插入操作）

构建二叉排序树的过程，本质是依次插入节点并维护 “左小右大” 规则的过程。

以BinaryTree类的create方法为例：

public class BinaryTree { TreeNode root; public void create(Integer value) { TreeNode newNode = new TreeNode(value); if (root == null) { root = newNode; return; } TreeNode curNode = root; while (true) { if (curNode.data < newNode.data) { if (curNode.rChild == null) { curNode.rChild = newNode; return; } curNode = curNode.rChild; } else { if (curNode.lChild == null) { curNode.lChild = newNode; return; } curNode = curNode.lChild; } } } }

三、二叉排序树的遍历方式

遍历是按一定规则访问树中所有节点的操作，二叉排序树常用深度优先遍历（先序、中序、后序）和广度优先遍历（层次遍历）。

1. 深度优先遍历

（1）先序遍历（根→左→右）

void beforeOrder(TreeNode root) { if (root == null) return; System.out.println(root.data); beforeOrder(root.lChild); beforeOrder(root.rChild); }

（2）中序遍历（左→根→右）

二叉排序树的中序遍历结果是 “升序序列”：

void inOrder(TreeNode root) { if (root == null) return; inOrder(root.lChild); System.out.println(root.data); inOrder(root.rChild);

（3）后序遍历（左→右→根）

void afterOrder(TreeNode root) { if (root == null) return; afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }

2. 广度优先遍历（层次遍历）

按 “从上到下、从左到右” 的顺序访问节点，借助队列实现：

void levelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { root = queue.pop(); System.out.println(root.data); if (root.lChild != null) { queue.add(root.lChild); } if (root.rChild != null) { queue.add(root.rChild); } } }

四、二叉排序树的查找操作

利用 “左小右大” 的特性，查找操作可以快速定位节点：

public TreeNode find(TreeNode root, Integer target) { if (root == null) return null; TreeNode cur = root; while (cur != null) { if (cur.data.equals(target)) { return cur; } else if (cur.data < target) { cur = cur.rChild; } else { cur = cur.lChild; } } return null; }

五、测试验证

package com.qcby; public class Test { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); // 构建二叉排序树 bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(9); bt.levelOrder(bt.root); Integer target = 8; TreeNode result = bt.find(bt.root, target); if (result != null) { System.out.println("找到了"); } else { System.out.println("没找到"); } } }

结果：