美文网首页
课程设计——判断二叉树是否为排序二叉树及排序二叉树节点的删除和插

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

作者: LetUsGoOn | 来源:发表于2019-05-26 18:08 被阅读0次

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

树结点

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);
}

相关文章

  • 浅谈红黑树

    二叉树排序 二叉树排序主要包括，节点信息的设计、节点的插入和树的中序遍历 节点信息（包括左右孩子和节点value）...

  • 2018-08-04

    排序二叉树的遍历 所谓排序二叉树是指树中的每个节点大于其左子节点，小于其左子节点。排序二叉树的遍历大体上可以分为三...

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

    本次的课程设计要求建立一颗二叉树，并且用中序非递归方法遍历该二叉树，然后判断该二叉树是否为二叉排序树，如果是二叉排...

  • 排序二叉树

    什么是排序二叉树？ 首先它是二叉树，二叉树的每个结点最多有两个子节点 排序二叉树就是左节点（如果存在的话）一定小于...

  • 二叉树应用

    1 项目要求 建立一棵二叉树 前序、中序、层次非递归遍历该二叉树 判断该二叉树是否为二叉排序树 如果是二叉排序树，...

  • 树

    1 二叉树的最近公共祖先（leetcode 236) 2 判断是否为平衡二叉树 3 判断二叉树是否为满二叉树 4 ...

  • 面试题

    面试题 二叉树 非递归实现二叉树遍历 节点: 前序遍历 中序遍历 后序遍历 排序 快速排序 其他问题 算法题 给一...

  • [数据结构]排序二叉树 解题报告

    Problem Description 建立并中序遍历一个排序二叉树 排序二叉树是指左子树的所有节点的值均小于它根...

  • 平衡二叉树

    输入一棵二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 Ja...

  • 二叉树2-平衡二叉树、完全二叉树、二叉树剪枝

    110.平衡二叉树 给定一个二叉树，判断它是否是高度平衡的二叉树。 一棵高度平衡二叉树定义为：一个二叉树每个节点 ...

网友评论

      本文标题：课程设计——判断二叉树是否为排序二叉树及排序二叉树节点的删除和插

      本文链接：https://www.haomeiwen.com/subject/hncftctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|课程设计——判断二叉树是否为排序二叉树及排序二叉树节点的删除和插|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！