Démonstration animée de l'arbre binaire de recherche Visualisez votre code avec des animations
二叉搜索树 (BST) 是一种特殊类型的二叉树，其中节点的左子节点的值小于该节点的值，右子节点的值大于该节点的值。 这个属性称为 BST 属性，它使得高效地搜索、插入和删除树中的元素成为可能。
BST 的根是左子树中具有最大值且右子树中具有最小值的节点。 每个左子树都是一个 BST，其节点的值小于根，每个右子树都是一个 BST，其节点的值大于根。
二叉搜索树 是一种基于节点的二叉树数据结构，具有以下属性：
- 节点的左子树仅包含键小于该节点键的节点。
- 节点的右子树仅包含键大于该节点键的节点。
- 这意味着根左边的所有内容都小于根的值，根右边的所有内容都大于根的值。 由于这种执行，二分查找非常容易。
-
左子树和右子树也必须是二叉搜索树。
不能有重复的节点（BST可能有重复的值，处理方式不同）
二分查找树中重复值的处理方法：
- 您根本不能允许重复的值。
- 我们必须始终遵循一致的过程，即要么将重复值存储在根的左侧，要么将重复值存储在根的右侧，但要与您的方法保持一致。
- 我们可以将计数器与节点一起保存，如果我们发现重复值，那么我们可以增加计数器
以下是可以在 BST 上执行的各种操作：
- 将节点插入 BST 中 ： 新密钥始终插入到叶子处。 从根开始搜索键直到叶节点。 一旦找到叶节点，新节点就会添加为叶节点的子节点。
- C++
- C
- Java
- Python3
- JavaScript
C++
// C++ program to insert a node // in a BST #include <bits/stdc++.h> using namespace std; // Given Node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to do inorder traversal of BST void inorder(struct node* root) { if
(root != NULL) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Inserting value 50 root = insert(root, 50); // Inserting value 30 insert(root, 30); // Inserting value 20 insert(root, 20); // Inserting value 40 insert(root, 40); // Inserting value 70 insert(root, 70); // Inserting value 60 insert(root, 60); // Inserting value 80 insert(root, 80); // Print the BST inorder(root); return 0; } // This code is contributed by shubhamsingh10 |
C
Java
Python3
Javascript
输出
20 30 40 50 60 70 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 中序遍历 ：在二叉搜索树（BST）的情况下，中序遍历以非降序给出节点。 我们首先访问左孩子，然后是根，然后是右孩子。
- C++
- C
- Java
- Python3
C++
// C++ program to implement
// inorder traversal of BST
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to do inorder traversal of BST void inorder(struct node* root) { if
(root != NULL) { inorder(root->left); cout << " " << root->key; inorder(root->right); } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call inorder(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
20 30 40 50 60 70 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 前序遍历 ：先序遍历先访问根节点，然后遍历左右子树。 它用于创建树的副本。 前序遍历还用于获取表达式树的前缀表达式。
- C++
- C
- Java
- Python3
C++
// C++ program to implement
// preorder traversal #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to do preorder traversal of BST void preOrder(struct node* root) { if
(root != NULL) { cout << " " << root->key; preOrder(root->left); preOrder(root->right); } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call preOrder(root); return 0; } // this code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
50 30 20 40 70 60 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 后序遍历 ：后序遍历首先遍历左右子树，然后访问根节点。 它用于删除树。 简单来说，最后访问每个子树的根。
- C++
- C
- Java
- Python3
C++
// C++ program to print total // count of nodes in BST
#include <iostream> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to do postorder traversal of BST void postOrder(struct node* root) { if
(root != NULL) { postOrder(root->left); postOrder(root->right); cout << " " << root->key; } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call postOrder(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
20 40 30 60 80 70 50
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 层序遍历 ：BST的层序遍历是树的广度优先遍历。 它首先访问特定级别的所有节点，然后再移动到下一个级别。
- C++
- C
- Java
- Python3
C++
// C++ program to implement
// level order traversal
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Returns height of the BST int height(struct node* node) { if
(node == NULL) return 0; else { // Compute the depth of each subtree int lDepth = height(node->left);
int rDepth = height(node->right);
// Use the larger one if (lDepth > rDepth) return (lDepth + 1); else return (rDepth + 1); } } // Print nodes at a given level void printGivenLevel(struct node* root, int level) { if
(root == NULL) return; if
(level == 1) cout <<" "<< root->key; else if (level > 1) { // Recursive Call printGivenLevel(root->left, level - 1); printGivenLevel(root->right, level - 1); } } // Function to line by line print // level order traversal a tree void printLevelOrder(struct node* root) { int
h = height(root); int
i; for (i = 1; i <= h; i++) { printGivenLevel(root, i); cout <<"\n"; } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL;
// Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80);
// Function Call printLevelOrder(root);
return 0; } // this code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
50 30 70 20 40 60 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 打印给定级别的节点 ：打印 BST 特定级别的所有节点。
- C++
- C
- Java
- Python3
C++
// C++ program to print nodes // at a given level #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Print nodes at a given level void printGivenLevel(struct node* root, int level) { if
(root == NULL) return; if
(level == 1) cout <<" "<< root->key; else if (level > 1) { // Recursive Call printGivenLevel(root->left, level - 1); printGivenLevel(root->right, level - 1); } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call printGivenLevel(root, 2); return 0; } // this code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
30 70
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 打印所有叶子节点 ：如果一个节点的左子节点和右子节点都为NULL，则该节点是叶子节点。
- C++
- C
- Java
- Python3
C++
// C++ program to print all
// leaf nodes of a BST
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to print leaf nodes // from left to right
void printLeafNodes(struct node* root) { // If node is null, return if
(!root) return; // If node is leaf node, // print its data if
(!root->left && !root->right) { cout <<" "<< root->key; return; } // If left child exists, // check for leaf recursively if
(root->left) printLeafNodes(root->left); // If right child exists, // check for leaf recursively if
(root->right) printLeafNodes(root->right); } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call printLeafNodes(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
20 40 60 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 打印所有非叶节点 ：如果一个节点的左子节点或右子节点不为 NULL，则该节点是非叶节点。
- C++
- C
- Java
- Python3
C++
// C++ program to print all
// non leaf nodes of a BST
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to print all non-leaf // nodes in a tree void printNonLeafNode(struct node* root) { // Base Cases if
(root == NULL || (root->left == NULL && root->right == NULL)) return; // If current node is non-leaf, if
(root->left != NULL || root->right != NULL) { cout <<" "<< root->key; } // If root is Not NULL and its one // of its child is also not NULL printNonLeafNode(root->left); printNonLeafNode(root->right); } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call printNonLeafNode(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
50 30 70
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- BST 的右视图 ：二叉搜索树的右视图是从右侧访问树时可见的节点集。
- C++
- C
- Java
- Python3
C++
// C++ program to print
// right view of a BST
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to print the right view // of a binary tree.
void rightViewUtil(struct node* root, int level, int* max_level) { // Base Case if
(root == NULL) return; // If this is the last Node of its level if
(*max_level < level) { cout <<"\t"<< root->key; *max_level = level; } // Recur for right subtree first, // then left subtree rightViewUtil(root->right, level + 1, max_level); rightViewUtil(root->left, level + 1, max_level); } // Wrapper over rightViewUtil() void rightView(struct node* root) { int
max_level = 0; rightViewUtil(root, 1, &max_level); } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call rightView(root); return 0; }
// This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
50 70 80
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- BST 的左视图 ：二叉搜索树的左视图是从左侧访问树时可见的节点集。
- C++
- C
- Java
- Python3
C++
// C++ program to print
// left view of a BST #include<bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to print left view of // binary tree void leftViewUtil(struct node* root, int level, int* max_level) { // Base Case if
(root == NULL) return; // If this is the first node // of its level if
(*max_level < level) { cout <<" "<< root->key; *max_level = level; } // Recur for left and right subtrees leftViewUtil(root->left, level + 1, max_level); leftViewUtil(root->right, level + 1, max_level); } // Wrapper over leftViewUtil() void leftView(struct node* root) { int
max_level = 0; leftViewUtil(root, 1, &max_level); } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call leftView(root); return 0; }
// This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
50 30 20
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- BST 的高度 ：使用节点的左右子树的高度递归计算，并将两个子树的高度中的最大值加 1 为节点分配高度。
- C++
- C
- Java
- Python3
C++
// C++ program to print
// height of a BST #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Returns height of the BST int height(struct node* node) { if
(node == NULL) return 0; else {
// Compute the depth of each subtree int lDepth = height(node->left);
int rDepth = height(node->right);
// Use the larger one if (lDepth > rDepth) return (lDepth + 1); else return (rDepth + 1); } } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call cout << " " << height(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
3
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 删除 BST 的节点 ：用于从 BST 中删除具有特定键的节点并返回新的 BST。
删除节点的不同场景：
- 要删除的节点是叶子节点：很简单，将其置空即可。
- 要删除的节点有一个子节点：只需用子节点替换该节点即可。
- 要删除的节点有两个子节点：
- 需要弄清楚要删除的节点将被什么替换。
- 希望对现有树结构的破坏最小化
- 可以从已删除节点的左子树或右子树中表出替换节点。
- 如果从左子树中取if，我们必须取左子树中的最大值。
- 如果从右子树取if，我们必须取右子树中的最小值。
- 选择一种方法并坚持下去。
- C++
- C
- Java
- Python3
C++
// C++ program to delete
// a node of BST #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to do inorder traversal of BST void inorder(struct node* root) { if
(root != NULL) { inorder(root->left); cout <<" "<< root->key; inorder(root->right); } } // Function that returns the node with minimum // key value found in that tree struct node* minValueNode(struct node* node) { struct node* current = node; // Loop down to find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; } // Function that deletes the key and // returns the new root
struct node* deleteNode(struct node* root, int key) { // base Case if
(root == NULL) return root; // If the key to be deleted is // smaller than the root's key, // then it lies in left subtree if
(key < root->key) { root->left = deleteNode(root->left, key); } // If the key to be deleted is // greater than the root's key, // then it lies in right subtree else if (key > root->key) { root->right = deleteNode(root->right, key); } // If key is same as root's key, // then this is the node // to be deleted else { // Node with only one child // or no child if (root->left == NULL) { struct node* temp = root->right;
free(root); return temp; } else if (root->right == NULL) { struct node* temp = root->left;
free(root); return temp; }
// Node with two children: // Get the inorder successor(smallest // in the right subtree) struct node* temp = minValueNode(root->right);
// Copy the inorder successor's // content to this node root->key = temp->key;
// Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root; }
// Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL;
// Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80);
// Function Call root = deleteNode(root, 60); inorder(root);
return 0; }
// This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
20 30 40 50 70 80
时间复杂度：
O(log N)，其中N是BST辅助空间的节点数
：
O(1)
- BST 的最小节点 ：用于返回 BST 中值最小的节点。
- C++
- C
- Java
- Python3
C++
// C++ program print smallest // element of BST #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function that returns the node with minimum // key value found in that tree struct node* minValueNode(struct node* node) { struct node* current = node; // Loop down to find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call cout <<" "<< minValueNode(root)->key; return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
20
时间复杂度：
O(log N)，其中N是BST辅助空间的节点数
：
O(1)
- BST 中的节点总数 ：该函数返回 BST 中的节点总数。
- C++
- C
- Java
- Python3
C++
// C++ program to print total // count of nodes in BST
#include <bits/stdc++.h> using namespace std; // Given Node node struct node { int
key; struct node *left, *right; }; // Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Function to insert a new node with // given key in BST struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if
(node == NULL) return newNode(key); // Otherwise, recur down the tree if
(key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } // Return the node pointer return node; } // Function to get the total count of // nodes in a binary tree
int nodeCount(struct node* node) { if
(node == NULL) return 0; else return nodeCount(node->left)
+ nodeCount(node->right) + 1; } // Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL; // Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); // Function Call cout <<" "<< nodeCount(root); return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出
7
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
- 删除BST ：用于彻底删除BST并释放内存。
- C++
- C
- Java
- Python3
C++
// C++ program to delete a BST #include <bits/stdc++.h> using namespace std; // Given Node node struct node { int key; struct node *left, *right; };
// Function to create a new BST node struct node* newNode(int item) { struct node* temp = (struct node*)malloc( sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; }
// Function to insert a new node with // given key in BST
struct node* insert(struct node* node, int key) { // If the tree is empty, return a new node if (node == NULL) return newNode(key);
// Otherwise, recur down the tree if (key < node->key) { node->left = insert(node->left, key); }
else if (key > node->key) { node->right = insert(node->right, key); }
// Return the node pointer return node; }
// Function to do inorder traversal of BST void inorder(struct node* root) { if (root != NULL) { inorder(root->left); cout<< " "<< root->key; inorder(root->right); }
}
// Function to delete the BST struct node* emptyBST(struct node* root) { struct node* temp; if (root != NULL) {
// Traverse to left subtree emptyBST(root->left);
// Traverse to right subtree emptyBST(root->right);
cout<<"\nReleased node:"<< root->key; temp = root;
// Require for free memory free(temp); }
return root; }
// Driver Code int main() { /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */ struct node* root = NULL;
// Creating the BST root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80);
cout<<"BST before deleting:\n"; inorder(root);
// Function Call root = emptyBST(root);
return 0; } // This code is contributed by shivanisinghss2110 |
C
Java
Python3
输出：
删除前的 BST： 20 30 40 50 60 70 80 发布节点：20 已发布节点：40 发布节点：30 已发布节点：60 发布节点：80 已发布节点：70 发布节点：50
时间复杂度：
O(N)，其中N是BST辅助空间的节点数
：
O(1)
BST的应用：
- 图算法： BST 可用于实现图算法，例如最小生成树算法。
- 优先级队列： BST可用于实现优先级队列，其中具有最高优先级的元素位于树的根部，而具有较低优先级的元素存储在子树中。
- 自平衡二叉搜索树： BST可以用作AVL树、红黑树等自平衡数据结构。
-
数据存储和检索：
BST 可用于快速存储和检索数据，例如在数据库中，搜索特定记录可以在对数时间内完成。
优点：
- 快速搜索： 在 BST 中搜索特定值的平均时间复杂度为 O(log n)，其中 n 是树中的节点数。 这比在数组或链表中搜索元素要快得多，在最坏的情况下，数组或链表的时间复杂度为 O(n)。
- 中序遍历： BST可以按顺序遍历，即访问左子树、根和右子树。 这可用于对数据集进行排序。
- 空间效率高： BST 空间效率高，因为与数组和链表不同，它们不存储任何冗余信息。
缺点：
- 倾斜树： 如果一棵树变得倾斜，则搜索、插入和删除操作的时间复杂度将是 O(n) 而不是 O(log n)，这会使树效率低下。
- 需要额外的时间： 自平衡树在插入和删除操作期间需要额外的时间来保持平衡。
- 效率： BST 对于具有许多重复项的数据集效率不高，因为它们会浪费空间。