数据结构二叉排序树应用一

这篇具有很好参考价值的文章主要介绍了数据结构二叉排序树应用一。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2022.11.19


任务描述

本关任务:输入一个无序序列,创建一棵二叉排序树。

相关知识

为了完成本关任务,你需要掌握:1.二叉排序树定义,2.如何创建一棵二叉排序树。

二叉排序树定义
二叉排序树:即一个二叉树,它的每一个结点的左孩子的data值比当前结点的data值小,而右孩子结点的data值比当前结点的data值大。
数据结构二叉排序树应用一
如何创建一棵二叉排序树
二叉排序树的创建过程:

  1. 创建一个根节点,将无序序列的第一个元素放入根节点;
  2. 依次将后面的无序序列依次插入二叉排序树,若比根节点值小,则递归插入左子树,否则递归插入右子树。

编程要求

本关的编程任务是补全右侧代码片段insertBiSortTree和creatBiSortTree中Begin至End中间的代码,具体要求如下:

  1. 在insertBiSortTree中,实现向升序二叉排序树插入元素;
  2. 在creatBiSortTree中,实现创建升序二叉排序树。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入
15
18 10 16 13 7 5 4 8 15 14 20 1 6 3 19
预期输出
1 3 4 5 6 7 8 10 13 14 15 16 18 19 20

输入说明
第一行:元素个数n
第二行:n个无序数列

输出说明
二叉排序树的中序遍历是有序序列,程序输出中序遍历结果

开始你的任务吧,祝你成功!文章来源地址https://www.toymoban.com/news/detail-475618.html

C/C++代码

//
//  binary_sort_tree.cpp
//  BinarySortTree
//
//  Created by ljpc on 2018/5/11.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include "binary_sort_tree.h"

BiTreeNode* insertBiSortTree(BiTreeNode* root, int key)
// 功能:实现向升序二叉排序树插入元素
// 输入:待插入元素key
// 返回:升序二叉排序树根节点
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if (root == NULL)
    {
        BiTreeNode *newNode = new BiTreeNode(key);
        return newNode;
    }
    if (root->data > key)
    {
            
        if (root->left != NULL)
        {
            insertBiSortTree(root->left, key);
        }
        else
        {
            BiTreeNode *newNode = new BiTreeNode(key);
            root->left = newNode;
        }
    }
    else if (root->data < key)
    {
        if (root->right != NULL)
        {
            insertBiSortTree(root->right, key);
        }
        else
        {
            BiTreeNode *newNode = new BiTreeNode(key);
            root->right = newNode;
        }
    }
    return root;
    /********** End **********/
}

BiTreeNode* creatBiSortTree(int* arr, int n)
// 功能:实现创建升序二叉排序树
// 输入:无序整数数列arr,数列个数n
// 返回:升序二叉排序树根节点
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
    if (arr == NULL)
    {
        return NULL;
    }
    int *p = arr;
    BiTreeNode* root = NULL;
    for (int i = 0; i < n; i++) {
        root = insertBiSortTree(root, *p++);
    }
    return root;
    /********** End **********/
}


到了这里,关于数据结构二叉排序树应用一的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之排序二叉树

    排序二叉树 基本概念 二叉树是一种从上往下的树状结构的数据结构,从根节点开始每个节点最多有两个子节点,左边的为左子节点,右边的为右子节点。 排序二叉树–有顺序,且没有重复元素的二叉树。顺序为: 对每个节点而言: 1)如果左子树不为空,则左子树上的所有

    2024年02月02日
    浏览(41)
  • 数据结构学习笔记——二叉排序树

    查找算法中,基于树这种数据结构进行查找即为树形查找,可将其分为 二叉排序树 、 平衡二叉树 和 B树 三种树形查找方法: 二叉排序树也称为二叉查找树或二叉搜索树(注意:与二分查找的判定树不同),其中各结点值的大小关系是: 左子树根结点右子树 ,且左、右子树

    2024年02月09日
    浏览(56)
  • 数据结构实现二叉排序树

    摘  要 二叉排序树(Binary Search Tree,BST),又叫做二叉查找树,二叉搜索树,是一种对查找和排序都有用的特殊二叉树。因为二叉排序树的中序遍历有序性,即得到的递增的序列,由于有序,因此其查找与二分查找类似,每次都可以缩小查找范围,查询效率较高。同时因为二叉排

    2024年02月03日
    浏览(34)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(54)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(40)
  • 数据结构-二叉排序树(建立、查找、修改)

    二叉排序树是动态查找表的一种,也是常用的表示方法。 其中,它具有如下性质: 1.若它的左子树非空,则其左子树的所有节点的关键值都小于根节点的关键值。 2.若它的右子树非空,则其右子树的所有节点的关键值都大于根结点的关键值。 3.它的左右子树也分别都是二叉排

    2024年02月04日
    浏览(44)
  • 【开卷数据结构 】二叉排序树(BST)

    目录 二叉排序树(BST) 二叉排序树的定义 二叉排序树的操作 二叉排序树的查找 代码演示 二叉排序树的插入 代码演示 二叉排序树的构造 代码演示 二叉排序树的删除 Q:什么是二叉排序树 A: 二叉排序树或者是一棵空树,或者是具有如下性质的二叉树 1) 若它的左子树不空

    2024年02月11日
    浏览(41)
  • 11. 数据结构之二叉树

    上一节,简单概述了树这种数据结构,以及树结构向下,具有某些一些特征的树,比如二叉树,B树,B+树,堆等。其中,二叉树是一个很重要的模块。也是在一些技术面试中,可能会问到的问题。本节,我们就二叉树,做详细介绍。 二叉树是一个 逻辑结构 , 底层可以用数组

    2024年02月07日
    浏览(46)
  • 【数据结构】:二叉树与堆排序的实现

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M0)个互不相交的集合T1、

    2024年02月08日
    浏览(41)
  • 数据结构--6.5二叉排序树(插入,查找和删除)

    目录 一、创建  二、插入 三、删除   二叉排序树(Binary Sort Tree)又称为二叉查找树,它或者是一棵空树,或者是具有下列性质的二叉树: ——若它的左子树不为空,则左子树上所有结点的值均小于它的根结构的值; ——若它的右子树不为空,则右子树上所有结点的值均大

    2024年02月09日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包