二叉树基础

什么是二叉排序树

二叉排序树又称二叉查找树，是一种特殊的二叉树，它的每个节点都包含一个数据域，且具有以下特点：

若左子树不为空，则左子树上所有节点的值均小于它的根节点的值

若右子树不为空，则右子树上所有节点的值均大于它的根节点的值

左、右子树也分别为二叉排序树

这种结构使得二叉排序树具有高效的查找、插入和删除操作特性。

二叉排序树的节点结构

二叉排序树由节点组成，每个节点包含三个部分：数据域、左子树指针和右子树指针。在 Java 中，我们可以用类来定义节点：

public class TreeNode {

public TreeNode lChild; // 左子树指针

public TreeNode rChild; // 右子树指针

public Integer data; // 数据域

// 构造方法，初始化数据

public TreeNode(Integer data){

this.data = data;

}

}

二叉排序树的构建

构建思路

构建二叉排序树的核心是插入操作，插入过程遵循以下规则：

若树为空，则新节点作为根节点

若树不为空，则从根节点开始比较：

若新节点值小于当前节点值，则向左子树移动

若新节点值大于当前节点值，则向右子树移动

重复上述过程，直到找到合适的空位置插入新节点

public class BinaryTree {

// 根节点指针

TreeNode root;

// 插入节点方法

public void create(Integer value){

// 1. 创建新节点

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;

}

}

}

// 后续代码省略...

}

二叉排序树的遍历

二叉排序树的遍历分为深度优先遍历和广度优先遍历两大类。

深度优先遍历（递归实现）

深度优先遍历包括先序遍历、中序遍历和后序遍历，它们的区别在于访问根节点的时机不同。

先序遍历（根左右）

// 先序遍历：根 -> 左 -> 右

void beforeOrder(TreeNode root){

if(root == null){

return;

}

System.out.println(root.data); // 访问根节点

beforeOrder(root.lChild); // 遍历左子树

beforeOrder(root.rChild); // 遍历右子树

}

中序遍历（左根右）

// 中序遍历：左 -> 根 -> 右

void inOrder(TreeNode root){

if(root == null){

return;

}

inOrder(root.lChild); // 遍历左子树

System.out.println(root.data); // 访问根节点

inOrder(root.rChild); // 遍历右子树

}

注意：二叉排序树的中序遍历结果是一个有序序列，这是其重要特性

后序遍历（左右根）

// 后序遍历：左 -> 右 -> 根

void afterOrder(TreeNode root){

if(root == null){

return;

}

afterOrder(root.lChild); // 遍历左子树

afterOrder(root.rChild); // 遍历右子树

System.out.println(root.data); // 访问根节点

}

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

层次遍历按照树的层次依次访问每个节点，需要借助队列来实现：

// 层次遍历

void levelOrder(TreeNode root){

LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

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 class Test {

public static void main(String[] args) {

BinaryTree tree = new BinaryTree();

// 插入节点

tree.create(5);

tree.create(3);

tree.create(7);

tree.create(0);

tree.create(4);

tree.create(6);

tree.create(9);

System.out.println("先序遍历：");

tree.beforeOrder(tree.root);