二叉搜索树是一种树形结构,由节点和边组成。每个节点最多有两个子节点(左子节点和右子节点),且左子节点的值小于等于父节点的值,右子节点的值大于父节点的值。如果一个节点的左子树或右子树为空,则称该节点为叶子节点。
平衡二叉树有以下特点:
一个二叉搜索树是如何建立的呢?
创建根节点:首先创建一个根节点,它可以是任意一个数值。
插入节点:对于待插入的数据,如果小于当前节点的值,则将其插入到当前节点的左子树中;如果大于当前节点的值,则将其插入到当前节点的右子树中。如果当前节点的左子树或右子树为空,则直接插入数据,否则继续遍历子树进行插入操作。
重复上面步骤:不断地进行插入节点的操作,直到所有数据都被插入二叉树中。
具体到计算机语言中可简单概括为:
java实现
class Node {
int key;
Node left;
Node right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
BinarySearchTree() {
root = null;
}
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) {
root.left = insertRec(root.left, key);
} else if (key > root.key) {
root.right = insertRec(root.right, key);
}
return root;
}
void inorder() {
inorderRec(root);
}
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
}
public class Main {
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
tree.inorder();
}
}
BinarySearchTree
类中的一个方法,用于向二叉搜索树中插入新的节点。:
Node insertRec(Node root, int key) {
- 这是一个递归方法的定义,它接收一个节点root
和一个要插入的值key
作为参数,并返回更新后的节点。
if (root == null) {
- 这个条件判断语句检查当前节点是否为空,如果是空节点,则表示已经找到了一个可以插入新值的位置。
root = new Node(key);
- 如果当前节点为空,这里会创建一个新的节点,并将新值key
赋给这个节点。
return root;
- 返回更新后的节点。
if (key < root.key) {
- 如果当前节点不为空,并且新值小于当前节点的值,那么就需要在当前节点的左子树中插入新值。
root.left = insertRec(root.left, key);
- 通过递归调用insertRec
方法,在当前节点的左子树中插入新值。
else if (key > root.key) {
- 如果新值大于当前节点的值,那么就需要在当前节点的右子树中插入新值。
root.right = insertRec(root.right, key);
- 通过递归调用insertRec
方法,在当前节点的右子树中插入新值。
return root;
- 返回更新后的节点
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。