平衡二叉树建立解读（Java实现）
原创平衡二叉树建立解读（Java实现）
原创
二叉搜索树是一种树形结构，由节点和边组成。每个节点最多有两个子节点（左子节点和右子节点），且左子节点的值小于等于父节点的值，右子节点的值大于父节点的值。如果一个节点的左子树或右子树为空，则称该节点为叶子节点。
平衡二叉树有以下特点：
- 每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 左子节点的值小于等于父节点的值，右子节点的值大于父节点的值。
- 每个节点的左子树和右子树也都是二叉树。
一个二叉搜索树是如何建立的呢？
创建根节点：首先创建一个根节点，它可以是任意一个数值。
插入节点：对于待插入的数据，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。如果当前节点的左子树或右子树为空，则直接插入数据，否则继续遍历子树进行插入操作。
重复上面步骤：不断地进行插入节点的操作，直到所有数据都被插入二叉树中。
具体到计算机语言中可简单概括为：
- 如果当前节点为空，则创建一个新节点，将待插入的数据作为该节点的值，然后返回该节点。
- 如果待插入的数据小于当前节点的值，则递归调用左子树进行插入操作，并将返回的节点设置为当前节点的左子节点。
- 如果待插入的数据大于等于当前节点的值，则递归调用右子树进行插入操作，并将返回的节点设置为当前节点的右子节点。
- 返回当前节点。
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 删除。
腾讯云开发者
