07_二叉搜索树

二叉搜索树又叫二叉排序树，二叉查找树。

7.1 定义

在二叉树的基础上，增加了几个规则约束（左小右大）：

  • 如果它的左子树不空，则左子树上所有的值均小于它的根节点的值
  • 若它的右子树不空，则右子树上所有的值均大于它的根节点的值
  • 它的左、右树又分为二叉排序树

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

7.2 申明

c 实现：

typedef int Element_t;
//定义节点结构
typedef struct treenode {
	Element_t data;
	struct treenode* left;
	struct treenode* right;
}TreeNode_t;

//定义二叉搜索树结构
typedef struct {
	int count;
	TreeNode_t* root;
}BinarySearchTree_t;

Java 实现：

Element:

package com.Sonnet.Element;

public class Element {
    private int data;

    public Element() {}
    public Element(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return String.valueOf(this.data);
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(this.data);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (this.getClass() != obj.getClass()) return false;
        Element other = (Element)obj;
        return this.data == ((Element) obj).data;
    }

    public int getData() {
        return data;
    }
}

TreeNode:

package com.Sonnet.BinarySearchTree;

import com.Sonnet.Element.Element;

public class TreeNode {
    private Element data;
    private TreeNode left;
    private TreeNode right;

    public TreeNode() {};
    public TreeNode(Element data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

BinarySearchTree:

package com.Sonnet.BinarySearchTree;

public class BinarySearchTree {
    private TreeNode root;
    private int count;
}

7.3 创建

c 实现：

/*创建树*/
BinarySearchTree_t* createBinarySearchTree() {
	BinarySearchTree_t* tree = malloc(sizeof(BinarySearchTree_t));
	if (tree == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	tree->count = 0;
	tree->root = NULL;

	return tree;
}

Java 实现：

    public BinarySearchTree() {
        this.root = null;
        this.count = 0;
    }

7.4 插入

7.4.1 递归

c 实现：

/*创建节点*/
static TreeNode_t* createTreeNode(Element_t data) {
	TreeNode_t* node = malloc(sizeof(TreeNode_t));
	if (node == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	node->data = data;
	node->left = NULL;
	node->right = NULL;

	return node;
}

/*插入节点*/
static TreeNode_t* insertNode(BinarySearchTree_t* tree, TreeNode_t* node, Element_t data) {
	if (node == NULL) {
		tree->count++;
		return createTreeNode(data);
	}
	if (data < node->data) {
		node->left = insertNode(tree, node->left, data);
	}
	else if (data > node->data) {
		node->right = insertNode(tree, node->right, data);
	}

	return node;
}

/*递归插入*/
void insertTreeNodeRecur(BinarySearchTree_t* tree, Element_t data) {
	if (tree == NULL) return;
	tree->root = insertNode(tree, tree->root, data);
}

Java 实现：

    /*插入节点*/
    private TreeNode insertNode(TreeNode node,  Element data) {
        if (node == null) {
            this.count++;
            return new TreeNode(data);
        }
        if (data.getData() < node.getData().getData()) {
            node.setLeft(insertNode(node.getLeft(), data));
        }
        else if (data.getData() > node.getData().getData()) {
            node.setRight(insertNode(node.getRight(), data));
        }

        return node;
    }

    /*
        功能： 递归插入
        参数： 节点数据
        返回值： 无
     */
    public void insertTreeNodeRecur(Element data) {
        this.root = insertNode(this.root, data);
    }

7.4.2 非递归

c 实现：

/*插入节点非递归*/
void insertTreeNodeNoRecur(BinarySearchTree_t* tree, Element_t data) {
	if (tree == NULL) return;

	//辅助指针
	TreeNode_t* pre = NULL;
	TreeNode_t* cur = tree->root;

	while (cur) {
		pre = cur;
		if (data < cur->data) {
			cur = cur->left;
		}
		else if (data > cur->data) {
			cur = cur->right;
		}
		//如果相等就直接返回
		else {
			return;
		}
	}

	//创建节点
	TreeNode_t* node = createTreeNode(data);
	if (pre) {
		if (data < pre->data) {
			pre->left = node;
		}
		else {
			pre->right = node;
		}
	}
	//当根节点不存在时，pre和cur都为空
	else {
		tree->root = node;
	}
	tree->count++;
}

Java 实现：

    /*
        功能：非递归插入节点
        参数：节点数据
        返回值：无
     */
    public void insertTreeNodeNoRecur(Element data) {
        //辅助指针
        TreeNode pre = null;
        TreeNode cur = this.root;

        while (cur != null) {
            pre = cur;
            if (data.getData() < cur.getData().getData()) {
                cur = cur.getLeft();
            } else if (data.getData() > cur.getData().getData()) {
                cur = cur.getRight();
            //相等直接返回
            } else {
                return;
            }
        }

        //创建节点
        TreeNode node = new TreeNode(data);

        if (pre != null) {
            if (data.getData() < pre.getData().getData()) {
                pre.setLeft(node);
            } else {
                pre.setRight(node);
            }
            //当根节点为空时，pre和cur都为空
        } else {
            this.root = node;
        }
        this.count++;
    }

7.5 访问节点数据

c 实现：

/*访问节点数据*/
void visitTreeNode(TreeNode_t* node) {
	if (node) {
		printf("%d\t", node->data);
	}
}

Java 实现：

    public void visitTreeNode(TreeNode node) {
        if (node == null) return;
        System.out.print(node.getData() + "\t");
    }

7.6 释放

c 实现：

/*释放节点*/
static void releaseTreeNode(BinarySearchTree_t* tree, TreeNode_t* node) {
	if (node == NULL) return;
	releaseTreeNode(tree, node->left);
	releaseTreeNode(tree, node->right);
	free(node);
	tree->count--;
}

/*释放*/
void releaseBinarySearchTree(BinarySearchTree_t* tree) {
	releaseTreeNode(tree, tree->root);
	printf("tree have %d node\n", tree->count);
	free(tree);
}

Java 实现：

    /*释放节点*/
    private void releaseTreeNode(TreeNode node) {
        if (node == null) {
            return;
        }
        releaseTreeNode(node.getLeft());
        releaseTreeNode(node.getRight());

        node.setLeft(null);
        node.setRight(null);
        this.count--;
    }

    /*
        功能： 释放二叉搜索树
        参数： 无
        返回值： 无
     */
    public void releaseBinarySearchTree() {
        releaseTreeNode(this.root);
        this.root = null;
        System.out.println("this tree have " + this.count + " node");
    }

7.7 中序遍历

c 实现：

/*中序遍历节点*/
static void inOrderTreeNode(TreeNode_t* node) {
	if (node == NULL) return;
	inOrderTreeNode(node->left);
	visitTreeNode(node);
	inOrderTreeNode(node->right);
}

/*中序遍历*/
void inOrderBinarySearchTree(BinarySearchTree_t* tree) {
	inOrderTreeNode(tree->root);
	printf("\n");
}

Java 实现：

    /*中序遍历节点*/
    private void inOrderTreeNode(TreeNode node) {
        if (node == null) return;
        this.inOrderTreeNode(node.getLeft());
        this.visitTreeNode(node);
        this.inOrderTreeNode(node.getRight());
    }

    /*
        功能： 中序遍历
        参数： 无
        返回值: 无
     */
    public void inOrderBinarySearchTree() {
        inOrderTreeNode(this.root);
        System.out.println();
    }

7.8 获取高度

c 实现：

/*高度*/
int heightBinarySearchTree(TreeNode_t* node) {
	if (node == NULL) return 0;

	int rightHeight = heightBinarySearchTree(node->right);
	int leftHeight = heightBinarySearchTree(node->left);
	
	if (leftHeight > rightHeight) {
		return ++leftHeight;
	}
	else {
		return ++rightHeight;
	}
}

Java 实现：

    /*
        功能： 获取二叉搜索树高度
        参数： 根节点
        返回值： 高度
     */
    public int heightBinarySearchTree(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = this.heightBinarySearchTree(root.getLeft());
        int rightHeight = this.heightBinarySearchTree(root.getRight());

        if (leftHeight > rightHeight) {
            return ++leftHeight;
        } else {
            return ++rightHeight;
        }
    }

7.9 搜索

c 实现：

/*搜索*/
TreeNode_t* searchTreeNode(BinarySearchTree_t* tree, Element_t data) {
	TreeNode_t* node = tree->root;

	while (node) {
		if (data < node->data) {
			node = node->left;
		}
		else if (data > node->data) {
			node = node->right;
		}
		else return node;
	}

	return NULL;
}

Java 实现：

    /*
        功能： 搜索节点
        参数： 数据
        返回值： 节点
     */
    public TreeNode searchTreeNode(Element data) {
        TreeNode node = this.root;
        while (node != null) {
            if (data.getData() < node.getData().getData()) {
                node = node.getLeft();
            } else if (data.getData() > node.getData().getData()) {
                node = node.getRight();
            } else {
                return node;
            }
        }
        return null;
    }

e"> Java 实现：

    /*
        功能： 搜索节点
        参数： 数据
        返回值： 节点
     */
    public TreeNode searchTreeNode(Element data) {
        TreeNode node = this.root;
        while (node != null) {
            if (data.getData() < node.getData().getData()) {
                node = node.getLeft();
            } else if (data.getData() > node.getData().getData()) {
                node = node.getRight();
            } else {
                return node;
            }
        }
        return null;
    }
# c语言 # java # 开发语言 # 数据结构
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

AI 资讯日报 | 2026年8月23日：开源提速、算力狂飙，Agent加速落地，AI产业进入资本、技术与商业化全面竞速的新阶段

avatar AI编程社区
cover

Agent 敢开写权限吗？Python 文件写入沙箱守卫实战

avatar AI编程社区

初识智能体

在过去两年中，几乎所有人都体验过大语言模型（如 ChatGPT、Claude、DeepSeek）的强大能力：写周报、润色邮件、解答编程疑难。被动响应：你问一句，它答一句。如果你的 Prompt 没有写清楚约束条件，它无法主动追问或修正目标。知行脱节：大模型能用流畅的文字告诉你“如何部署一个高可用 K8s 集群”，但它无法替你登录服务器敲下命令、查看报错日志并自动回滚。信息孤岛：大模型的知识止步于预

avatar AI编程社区