二叉搜索樹
- 定義
- 形式與基本性質
- 代碼基本實作
- 相關問題
  - L2-004 這是二叉搜索樹嗎？
    - 輸入格式：
    - 輸出格式：
    - 思路
    - 題解

二叉搜索樹

定義

二叉查找樹（英語：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 = https://www.cnblogs.com/Delta2019/p/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 = https://www.cnblogs.com/Delta2019/p/value;
        return;
    }
    if (value < root->data)
        insert(root->left, value);
    else
        insert(root->right, value);
}
void preOrder(Node *root, vector &res)
{
    if (root)
    {
        res.push_back(root->data);
        preOrder(root->left, res);
        preOrder(root->right, res);
    }
}
void preOrderMirror(Node *root, vector &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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20772.html

標籤：C++

上一篇：C++ 后置回傳型別

下一篇：delphi 呼叫webservice的問題

二叉搜索樹_BST