7二叉排序树

二叉排序树

性质：（左右子树不空）

左子树所有结点的值都小于根节点

右子树所有结点的值都大于根节点

构建二叉排序树

根据性质一个一个插入即可

优势

中序遍历（左中右）后就已经排好序

难度

删除后可能会改变结构，代码实现

情况分析：

1.叶子结点，直接删除

2.单孩子结点，删除结点后将孩子放在删除的位置

3.左右孩子都有的结点，将排序后前后的任一结点填充到该位置（即左子树的最右边或右子树的最左边那个填充）

代码实现思路：先定位到这个待删除的结点，再给这个结点归类，根据类别删除这个结点

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode{
    struct TreeNode* left,*right;
    int data;
}Node;

void insert(Node* root,int key)
{
    Node* pre=NULL;
    while(root!=NULL)
    {
        pre=root;
        if(key<root->data)
        {
            root=root->left
        }
        else
        {
            root=root->right;
        }
	}
    
    Node* new_node=(Node*)malloc(sizeof(Node));
    new_node->left=NULL;
    new_node->right=NULL;
    new_node->data=key;
    if(key<pre->data)
    {
        pre->left=new_node;
    }
    else
    {
        pre->right=new_node;
    }
    
}

void deleteNode(Node* root,int key)
{
    if(root==NULL)//根节点为空
    {
        return;
	}
    else//正常删除
    {
        if(key<root->data)
        {
            return deleteNode(root->left,key);
        }
        else if(key>root->data)
        {
            return deleteNode(root->right,key);
        }
        else
        {
            //删除
            delete(root);
        }
    }
}

void delete(Node* node)
{
    Node* temp=NULL;
    //删除只有一个孩子或没孩子的结点的情况
    if(node->left==NULL)
    {
        temp=node;
        node=node->right;
    }
    else if(node->right==NULL)
    {
        temp=node;
        node=node->left;
    }
    else//左右子树都不为空
    {
        temp=node;
        Node* s=node;//找左子树的最大值
        s=s->left;
        while(s->right!=NULL)
        {
            temp=s;
            s=s->right;
		}
        //找到后先替换数据
        node->data=s->data;
        
        //开始删除
        if(temp!=node)
        {
            
            temp->right=s->left;
            //在此处free
		}
        else//如果s没有右子树，即定位根本没有进行
        {
            temp->left=s->right;
        }
        
    }
    
    
}

时间复杂度

o(h)=o(log2n)

发布于 2024-11-10