二叉搜索树-基本功能实现（BST）

2021-08-08

如题目＞▽＜

二叉树搜索树的概念

二叉搜索(排序)树（Binary Search Tree）是以一棵二叉树来组织的经典数据结构。每个节点是一个对象，包含的属性有left，right和data，left为该节点的左孩子，right为该节点的右孩子，data是它的值，如果相应的孩子节点不存在，则将该节点设置为NULL

BST的核心

设x为BST的一个节点，则有

y是当前节点的右节点，则有x.data<y.data
y是当前节点的左节点，则有x.data>y.data
BST没有相同的节点

BST的数据结构

struct Node{//节点
    int data;
    Node *left, *right;
};
struct Tree{//将该树打包成一个，只存放根节点
    Node *root;
};

BST的功能函数

插入

因为左子树的值小于根节点，右子树的值大于根节点，根据这个特点，我们可以从根节点开始，逐层递归，直到递归到叶节点再判断插在左子树还是右子树上
注意： 根节点直接建立，不需要递归

代码

void insert(Tree *tree,int val){//传入树，以及所需要插入的值
    Node *node = new (Node);
    node->data = val;
    node->left = NULL;
    node->right = NULL;

    if(tree->root==NULL){//根节点建立
        tree->root = node;
    }
    else{
        Node *tmp = tree->root;
        while(tmp!=NULL){
            if(tmp->data<val){//当前值大于节点值，放在右子树上
                if(tmp->right==NULL){
                    tmp->right = node;
                    return;
                }
                else
                tmp = tmp->right;
            }
            else{
                if(tmp->left==NULL){//当前值小于节点值，放在左子树上
                    tmp->left = node;
                    return;
                }
                else
                tmp = tmp->left;
            }
        }
    }
}

求树的深度

树的深度：该二叉树的最大层数
我们可以比较左子树和右子树的层数，将较大的层数加上当前层数（+1）逐层递归，直到递归到叶节点。

代码

int get_height(Node *node){//求树的深度
    if(node==NULL){
        return 0;//出口
    }
    else{
        return max(get_height(node->left), get_height(node->right))+1;//比较两个子树的深度加当前节点数进行递归
    }
}

求树的最值

因为我们的BST永远保持左子树小于右子树，所以最大值一定在最右面一条路的叶节点上，同理，最小值一定在左面一条路的左子树上。

代码

这里给出求最大值的代码，最小值同理

int get_max_binary(Node *node){//获取最大值
    while(node->right!=NULL){
        node = node->right;//一直向右寻找
    }
    return node->data;
}

当前树不是BST

这种情况下我们就需要将所有的节点进行遍历以找到最值

int get_max_normal(Node *node){
    if(node==NULL){
        return -1;
    }
    else{
        int mx = node->data;
        mx = max(get_max_normal(node->left), mx);
        mx = max(get_max_normal(node->right), mx);
        return mx;
    }
}

遍历

一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树

前序遍历

DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面）

void preorder(Node *node){//前序遍历
    if(node!=NULL){
        cout << node->data << " ";
        preorder(node->left);
        preorder(node->right);
    }
}

中序遍历

LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）

void inorder(Node *node){//中序遍历
    if(node!=NULL){
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
}

后序遍历

LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

void postorder(Node *node){//后序遍历
    if(node!=NULL){
        postorder(node->left);
        postorder(node->right);
        cout << node->data << " ";
    }
}