Tvivanomy

一个和两个排序树节点的类型定义

typedef结构节点{

KeyType键；

结构节点* lchild，* rchild;

} BSTNode；

第二，主要操作

BSTNode* SearchBST(BSTNode* bt, KeyType k);//查找
int InsertBST(BSTNode*& p, KeyType k);//插入节点
BSTNode* CreateBST(BSTNode* bt, KeyType a[], int n);//生成二叉树
int DeleteBST(BSTNode*& bt, KeyType k);//删除节点
void Delete1(BSTNode*& p);//左子树或右子树存在的情况下删除
void Delete2(BSTNode* p, BSTNode*& r);//左子树且右子树存在的情况下删

三个. 伪代码

1. 查找节点

BSTNode* SearchBST(BSTNode* bt, KeyType k)
{
    if (bt为空 || bt->key == k)
        返回bt;
    if (bt->key > k)
        return SearchBST(bt->lchild, k);
    else
        return SearchBST(bt->rchild, k);
}

2. 插入节点

int InsertBST(BSTNode*& p, KeyType k)
{
    if (p为空) {
        创建节点p;
        p->key = k;
        p的左孩子和右孩子赋为NULL;
        return OK;
    }
    else if (p->key == k)
        return 0;
    else if (p->key > k)
        return InsertBST(p->lchild, k);
    else
        return InsertBST(p->rchild, k);
}

3. 生成排序的二叉树

BSTNode* CreateBST(BSTNode* bt, KeyType a[], int n)
{
    建立二叉树指针bt;
    while (i < n) {
        InsertBST(bt, a[i]);
        i++;
    }
    返回bt;
}

4. 删除节点

int DeleteBST(BSTNode*& bt, KeyType k)
{
    if (bt为空)
        return 0;
    else {
        if (bt->key == k)
            return DeleteBST(bt->lchild, k);
        else if (bt->key == k)
            return DeleteBST(bt->rchild, k);
        else {
            删除bt;
            return OK;
        }
    }
}
void Delete1(BSTNode*& p)
{
    if (p的右孩子为空) {
        q = p;
        p指向p的左孩子;
        删除q;
    }
    else if (p的左孩子为空) {
        q = p;
        p指向p的右孩子;
        删除q;
    }
    else {//左右孩子都不为空
        Delete2(p, p->lchild);
    }
}
void Delete2(BSTNode* p, BSTNode*& r)
{
    if (r的右孩子不为空)
        Delete2(p, r->rchild);
    else {
        p->key = r->key;
        q = r;
        r指向r的左孩子;
        删除q;
    }
}

四个完整的代码

#include<iostream>
#define OK 1
using namespace std;
typedef int KeyType;
typedef struct node {
    KeyType key;
    struct node* lchild, * rchild;
}BSTNode;
BSTNode* SearchBST(BSTNode* bt, KeyType k);//查找
int InsertBST(BSTNode*& p, KeyType k);//插入节点
BSTNode* CreateBST(BSTNode*& bt,KeyType a[], int n);//生成二叉树
int DeleteBST(BSTNode*& bt, KeyType k);//删除节点
void Delete1(BSTNode*& p);//左子树或右子树存在的情况下删除
void Delete2(BSTNode* p, BSTNode*& r);//左子树且右子树存在的情况下删除
int InOrderTraverse(BSTNode* bt);
BSTNode* SearchBST(BSTNode* bt, KeyType k)
{
    if (bt == NULL || bt->key == k)
        return bt;
    if (bt->key > k)
        return SearchBST(bt->lchild, k);
    else
        return SearchBST(bt->rchild, k);
}
int InsertBST(BSTNode*& p, KeyType k)
{
    if (p == NULL) {
        p = new BSTNode;
        p->key = k;
        p->lchild = NULL; p->rchild = NULL;
        return OK;
    }
    else if (p->key == k)
        return 0;
    else if (p->key > k)
        return InsertBST(p->lchild, k);
    else
        return InsertBST(p->rchild, k);
}
BSTNode* CreateBST(BSTNode*& bt,KeyType a[], int n)
{
    int i = 0;
    while (i < n) {
        InsertBST(bt, a[i]);
        i++;
    }
    return bt;
}
int DeleteBST(BSTNode*& bt, KeyType k)
{
    if (bt == NULL)
        return 0;
    else {
        if (bt->key > k)
            return DeleteBST(bt->lchild, k);
        else if (bt->key < k)
            return DeleteBST(bt->rchild, k);
        else {
            Delete1(bt);
            return OK;
        }
    }
}
void Delete1(BSTNode*& p)
{
    BSTNode* q;
    if (p->rchild == NULL) {
        q = p;
        p = p->lchild;
        delete q;
    }
    else if (p->lchild == NULL) {
        q = p;
        p = p->rchild;
        delete q;
    }
    else
        Delete2(p, p->lchild);
}
void Delete2(BSTNode* p, BSTNode*& r)
{
    BSTNode* q;
    if (r->rchild != NULL)
        Delete2(p, r->rchild);
    else {
        p->key = r->key;
        q = r;
        r = r->lchild;
        delete q;
    }
}
int InOrderTraverse(BSTNode* bt)
{
    if (bt != NULL) {
        InOrderTraverse(bt->lchild);
        cout << bt->key<<" ";
        InOrderTraverse(bt->rchild);
    }
    return OK;
}
int main()
{
    BSTNode* bt=NULL;
    KeyType a[100];
    int n;
    cout << "输入关键字个数：";
    cin >> n;
    cout << "输入所有关键字：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    CreateBST(bt,a, n);
    cout << "中序输出：";
    InOrderTraverse(bt);
    cout << endl;
    int k;
    cout << "输入欲删除关键字：";
    cin >> k;
    DeleteBST(bt, k);
    cout << "中序输出：";
    InOrderTraverse(bt);
    cout << endl;
}

五个，案例输出

六. 摘要

1. 代码中有三种情况可用于删除节点. 当删除的节点的左子树和右子树存在时，找到左子树的最大节点建立二叉排序树，即被删除节点的前身，或找到右子节点. 树的最小节点是已删除节点的后继节点.

2. 递归广泛用于各种操作中；在编写有关树的代码时，您可以更多地考虑使用递归，因为树上有左右两个孩子的分支建立二叉排序树，因此递归的使用变得非常清晰和简单.

发布于2020-04-19 15: 17王林涛（Tvivanomy）阅读（...）评论（...）编辑

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-206552-1.html