课程设计——判断二叉树是否为排序二叉树及排序二叉树节点的删除和插入算法

本次的课程设计要求建立一颗二叉树，并且用中序非递归方法遍历该二叉树，然后判断该二叉树是否为二叉排序树，如果是二叉排序树的话进一步要求对结点进行插入和删除操作，并输出操作后的结果。

树结点

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int data;
}BiTreeNode, *BiTree;

首先我们要建立一颗二叉树，这里我们采用二叉树的前序遍历序列和中序遍历序列递归地建立一颗二叉树，代码如下：

//二叉排序树测试用例
int pre[] = { 5, 3, 2, 4, 8, 6 };//前序遍历
int ino[] = { 2, 3, 4, 5, 6, 8 };//中序遍历
void BuildBTree(BiTreeNode **T, int preL, int preR, int inoL, int inoR)//递归建树
{
    if (preL>preR) return;
    int e = pre[preL];
    int root = inoL;
    while (ino[root] != e&&root <= inoR) ++root;
    (*T) = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*T)->lchild = NULL;
    (*T)->rchild = NULL;
    (*T)->data = e;
    BuildBTree(&(*T)->lchild, preL + 1, preL + root - inoL, inoL, root - 1);
    BuildBTree(&(*T)->rchild, preL + root - inoL + 1, preR, root + 1, inoR);
}

然后定义中序非递归遍历函数，这里用辅助栈实现中序非递归遍历二叉树算法，代码如下:

void midvisit(BiTreeNode*root)
{
    //中序非递归遍历
    printf("中序遍历结果:");
    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                printf("%d", p->data);
                p = p->rchild;
            }
        }
    }
    putchar('\n');
}

为了便于对输出进行比较，顺便写了一个前序递归遍历函数，代码如下：

void previsit(BiTreeNode* t)
{
    if (t)
    {
        printf("%d", t->data);
        previsit(t->lchild);
        previsit(t->rchild);
    }
}

接下来我们要判断这颗二叉树是不是排序二叉树，算法的思想为：先对二叉树进行一次中序遍历，并且将遍历结果存储到数组中，复制该数组然后用快速排序对其进行升序排序，再比较排序前和排序后的数组是否一致，如果有一处不一致则该二叉树不是排序二叉树，如果全部一致则为二叉排序树，代码如下：

int cmp(const void*a, const void*b)
{
    return *(int*)a - *(int*)b;
}

bool IsSortTree(BiTreeNode* root)
{//判断是否是二叉排序树
    int size = 0;
    int data[MAXSIZE], sortdata[MAXSIZE];

    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                //printf("%d", p->data);
                data[size++] = p->data;
                p = p->rchild;
            }
        }
    }

    for (int i = 0; i < size; ++i)
        sortdata[i] = data[i];
    qsort(sortdata, size, sizeof(int), cmp);

    for (int i = 0; i < size; ++i)
    {
        if (sortdata[i] != data[i])
            return false;
    }
    return true;
}

接来下的两个函数实现对排序二叉树新增结点和删除结点操作。

BiTreeNode* Insert(BiTreeNode*root, int x)
{
    if (!root){
        root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        root->data = x;
        root->lchild = root->rchild = NULL;
        }
        else{
            if (x < root->data)
                root->lchild = Insert(root->lchild, x);
            else if (x > root->data)
                root->rchild = Insert(root->rchild, x);
        }
        return root;
}
void Del(BiTree&root, int x)
{
        if (root == NULL){
            return;
        }
        if (root->data>x){
            Del(root->lchild, x);
        }
        else if (root->data<x){
            Del(root->rchild, x);
        }
        else{ //查找到了删除节点
            if (root->lchild == NULL){ //左子树为空
                BiTree tempNode = root;
                root = root->rchild;
                free(tempNode);
            }
            else if (root->rchild == NULL){ //右子树为空
                BiTree tempNode = root;
                root = root->lchild;
                free(tempNode);
            }
            else{  //左右子树都不为空
                //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)
                BiTree tempNode = root->lchild;
                if (tempNode->rchild != NULL){
                    tempNode = tempNode->rchild;
                }
                root->data = tempNode->data;
                Del(root->lchild, tempNode->data);
            }
        }
}

这里我们定义了一个非必须的solve()函数，来实现判断二叉树是否为排序二叉树以及后续操作。


void solve(BiTreeNode*root)
{
    //如果是二叉排序树，进行结点的插入或删除。
    if (IsSortTree(root))
    {
        midvisit(root);
        Insert(root, 11); //如果是排序树，插入值11
        midvisit(root);
        Del(root, 5);//删除值为5的结点
        midvisit(root);
    }
    else
        return;//不是二叉排序树 什么也不做
}

最后就是main()函数了。。。

int main()
{
    //freopen("data.txt", "r", stdin);

    BiTreeNode*root;
    BuildBTree(&root, 0, sizeof(pre) / sizeof(pre[0])-1, 0, sizeof(ino) / sizeof(ino[0])-1);
    printf("前序遍历结果:");
    previsit(root); 
    putchar('\n');
    midvisit(root);

    if (IsSortTree(root))
        printf("YES\n");
    else
        printf("NO\n");
    solve(root);
}

完整代码代码如下：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE (100)

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int data;
}BiTreeNode, *BiTree;

//非二叉排序树测试用例
//int pre[] = { 1, 2, 4, 5, 3, 6, 7 };//前序序列
//int ino[] = { 4, 2, 5, 1, 6, 3, 7 };//中序序列

//二叉排序树测试用例
int pre[] = { 5, 3, 2, 4, 8, 6 };
int ino[] = { 2, 3, 4, 5, 6, 8 };
void BuildBTree(BiTreeNode **T, int preL, int preR, int inoL, int inoR)//递归建树
{
    if (preL>preR) return;
    int e = pre[preL];
    int root = inoL;
    while (ino[root] != e&&root <= inoR) ++root;
    (*T) = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*T)->lchild = NULL;
    (*T)->rchild = NULL;
    (*T)->data = e;
    BuildBTree(&(*T)->lchild, preL + 1, preL + root - inoL, inoL, root - 1);
    BuildBTree(&(*T)->rchild, preL + root - inoL + 1, preR, root + 1, inoR);
}

void midvisit(BiTreeNode*root)
{
    //中序非递归遍历
    printf("中序遍历结果:");
    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                printf("%d", p->data);
                p = p->rchild;
            }
        }
    }
    putchar('\n');
}

void previsit(BiTreeNode* t)
{
    if (t)
    {
        printf("%d", t->data);
        previsit(t->lchild);
        previsit(t->rchild);
    }
}
int cmp(const void*a, const void*b)
{
    return *(int*)a - *(int*)b;
}

bool IsSortTree(BiTreeNode* root)
{//判断是否是二叉排序树
    int size = 0;
    int data[MAXSIZE], sortdata[MAXSIZE];

    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                //printf("%d", p->data);
                data[size++] = p->data;
                p = p->rchild;
            }
        }
    }

    for (int i = 0; i < size; ++i)
        sortdata[i] = data[i];
    qsort(sortdata, size, sizeof(int), cmp);

    for (int i = 0; i < size; ++i)
    {
        if (sortdata[i] != data[i])
            return false;
    }
    return true;
}
BiTreeNode* Insert(BiTreeNode*root, int x)
{
    if (!root){
        root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        root->data = x;
        root->lchild = root->rchild = NULL;
        }
        else{
            if (x < root->data)
                root->lchild = Insert(root->lchild, x);
            else if (x > root->data)
                root->rchild = Insert(root->rchild, x);
        }
        return root;
}
void Del(BiTree&root, int x)
{
        if (root == NULL){
            return;
        }
        if (root->data>x){
            Del(root->lchild, x);
        }
        else if (root->data<x){
            Del(root->rchild, x);
        }
        else{ //查找到了删除节点
            if (root->lchild == NULL){ //左子树为空
                BiTree tempNode = root;
                root = root->rchild;
                free(tempNode);
            }
            else if (root->rchild == NULL){ //右子树为空
                BiTree tempNode = root;
                root = root->lchild;
                free(tempNode);
            }
            else{  //左右子树都不为空
                //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)
                BiTree tempNode = root->lchild;
                if (tempNode->rchild != NULL){
                    tempNode = tempNode->rchild;
                }
                root->data = tempNode->data;
                Del(root->lchild, tempNode->data);
            }
        }
}

void solve(BiTreeNode*root)
{
    //如果是二叉排序树，进行结点的插入或删除。
    if (IsSortTree(root))
    {
        midvisit(root);
        Insert(root, 11); //如果是排序树，插入值11
        midvisit(root);
        Del(root, 5);//删除值为5的结点
        midvisit(root);
    }
    else
        return;//不是二叉排序树 什么也不做
}
int main()
{
    //freopen("data.txt", "r", stdin);

    BiTreeNode*root;
    BuildBTree(&root, 0, sizeof(pre) / sizeof(pre[0])-1, 0, sizeof(ino) / sizeof(ino[0])-1);
    printf("前序遍历结果:");
    previsit(root); 
    putchar('\n');
    midvisit(root);

    if (IsSortTree(root))
        printf("YES\n");
    else
        printf("NO\n");
    solve(root);
}

最后编辑于：2019.07.22 10:54:15

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,734评论 6赞 505
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,931评论 3赞 394
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,133评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,532评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,585评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,462评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,262评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,153评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,587评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,792评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,919评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,635评论 5赞 345
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,237评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,855评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,983评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,048评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,864评论 2赞 354

课程设计——判断二叉树是否为排序二叉树及排序二叉树节点的删除和插入算法

推荐阅读更多精彩内容