二叉搜索樹 定義 二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹： 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節 ...
目錄
二叉搜索樹
定義
二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
- 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
- 若任意節點的右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值；
- 任意節點的左、右子樹也分別為二叉查找樹；
推薦講解視頻：
https://www.bilibili.com/video/BV1Qx411m7Lb
https://www.bilibili.com/video/BV1Qx411m7jE
https://www.bilibili.com/video/BV1os411Y7Rt正月點燈籠@BILIBILI
形式與基本性質
滿二叉樹：
在一棵二叉樹中，如果所有分支結點都有左孩子和右孩子結點，並且葉子結點都集中在二叉樹的最下層，這樣的樹叫做滿二叉樹
完全二叉樹：
若二叉樹中最多只有最下麵兩層的結點的度數可以小於2，並且最下麵一層的葉子結點都是依次排列在該層最左邊的位置上，則稱為完全二叉樹
區別：
滿二叉樹是完全二叉樹的特例，因為滿二叉樹已經滿了，而完全並不代表滿。所以形態你也應該想象出來了吧，滿指的是出了葉子節點外每個節點都有兩個孩子，而完全的含義則是最後一層沒有滿。
二叉樹的五個重要性質：
- 在二叉樹的第i層上最多有2 i-1 個節點 。（i>=1）
- 二叉樹中如果深度為k,那麼最多有2k-1個節點。(k>=1）
- n0=n2+1 n0表示度數為0的節點 n2表示度數為2的節點
- 在完全二叉樹中，具有n個節點的完全二叉樹的深度為[log2n]+1，其中[log2n]+1是向下取整。
- 若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點：
- 若 i=1，則該結點是二叉樹的根，無雙親, 否則，編號為 [i/2] 的結點為其雙親結點;
- 若 2i>n，則該結點無左孩子， 否則，編號為 2i 的結點為其左孩子結點；
- 2i+1>n，則該結點無右孩子結點， 否則，編號為2i+1 的結點為其右孩子結點。
代碼基本實現
實現中大量用了遞歸的方法，可以說遞歸思想是精髓。
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *left = nullptr;
Node *right = nullptr;
};
//迭代方法實現建樹，插入節點
void insertByIterate(Node *&root, int value) //註意root為Node*類型的引用，因為要對root本身進行修改
{
Node *node = new Node;
node->data = value;
if (root == nullptr)
{
root = node;
return;
}
else
{
Node *temp = root;
while (temp)
{
// if (value == temp->data) //避免插入重覆元素
// return;
if (value < temp->data)
{
if (temp->left)
{
temp = temp->left;
}
else
{
temp->left = node;
return;
}
}
else
{
if (temp->right)
{
temp = temp->right;
}
else
{
temp->right = node;
return;
}
}
}
}
}
//遞歸方法實現實現建樹，插入節點
// ! 可能無法記錄父節點，自身層數
void insertByRecursion(Node *&root, int value)
{
if (root == nullptr)
{
root = new Node;
root->data = value;
return;
}
// if (data == root->data) //禁止重覆元素
// return;
if (value < root->data)
insertByRecursion(root->left, value);
else
insertByRecursion(root->right, value);
}
void preorder(Node *root) //中序後序同理
{
if (root)
{
cout << root->data << ' ';
preorder(root->left);
preorder(root->right);
}
}
int main(void)
{
int arr[7] = {6, 1, 2, -10, 4, 5, 7};
Node *tree = nullptr;
for (size_t i = 0; i < 7; i++)
{
insertByRecursion(tree, arr[i]);
}
preorder(tree);
cout << endl;
return 0;
}
相關問題
L2-004 這是二叉搜索樹嗎？
一棵二叉搜索樹可被遞歸地定義為具有下列性質的二叉樹：對於任一結點，
- 其左子樹中所有結點的鍵值小於該結點的鍵值；
- 其右子樹中所有結點的鍵值大於等於該結點的鍵值；
- 其左右子樹都是二叉搜索樹。
所謂二叉搜索樹的“鏡像”，即將所有結點的左右子樹對換位置後所得到的樹。
給定一個整數鍵值序列，現請你編寫程式，判斷這是否是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果。
輸入格式：
輸入的第一行給出正整數 N（≤1000）。隨後一行給出 N 個整數鍵值，其間以空格分隔。
輸出格式：
如果輸入序列是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果，則首先在一行中輸出 YES ，然後在下一行輸出該樹後序遍歷的結果。數字間有 1 個空格，一行的首尾不得有多餘空格。若答案是否，則輸出 NO。
輸入樣例 1：
7
8 6 5 7 10 8 11
輸出樣例 1：
YES
5 7 6 8 11 10 8
輸入樣例 2：
7
8 10 11 8 6 7 5
輸出樣例 2：
YES
11 8 10 7 5 6 8
輸入樣例 3：
7
8 6 8 5 10 9 11
輸出樣例 3：
NO
思路
題解
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *left = 0;
Node *right = 0;
} *tree = 0;
int n;
typedef vector<int> arr;
void insert(Node *&root, int value)
{
if (root == 0)
{
root = new Node;
root->data = value;
return;
}
if (value < root->data)
insert(root->left, value);
else
insert(root->right, value);
}
void preOrder(Node *root, vector<int> &res)
{
if (root)
{
res.push_back(root->data);
preOrder(root->left, res);
preOrder(root->right, res);
}
}
void preOrderMirror(Node *root, vector<int> &res)
{
if (root)
{
res.push_back(root->data);
preOrderMirror(root->right, res);
preOrderMirror(root->left, res);
}
}
void postOrder(Node *tree)
{
static int count(0);
if (tree)
{
postOrder(tree->left);
postOrder(tree->right);
cout << tree->data;
count++;
if (count != n)
cout << " ";
}
}
void postOrderMirror(Node *tree)
{
static int count(0);
if (tree)
{
postOrderMirror(tree->right);
postOrderMirror(tree->left);
cout << tree->data;
count++;
if (count != n)
cout << " ";
}
}
int main(void)
{
cin >> n;
vector<int> input;
int temp;
for (int i = 0; i < n; i++)
{
cin >> temp;
insert(tree, temp);
input.push_back(temp);
}
vector<int> res_pre, res_premirror;
preOrder(tree, res_pre);
preOrderMirror(tree, res_premirror);
if (input == res_pre)
{
cout << "YES" << endl;
postOrder(tree);
}
else if (input == res_premirror)
{
cout << "YES" << endl;
postOrderMirror(tree);
}
else
{
cout << "NO" << endl;
}
return 0;
}
