数据结构课程设计报告二进制排序树（存储在序列表结构中）

数据结构课程设计报告二进制排序树（存储在序列表结构中）计算机科学与技术

2摘要设计

2.1二进制排序树的定义

二进制排序树是动态树表.

二进制排序树的定义: 二进制排序树是空树或具有以下属性的二进制树:

（1）每个节点都有一个关键字作为搜索基础，并且所有节点的关键字代码互不相同

相同；

（2）如果其左子树不为空二叉排序树 数据结构，则左子树上所有节点的值小于根节点的值; （3）如果其右子树不为空，则在右子树上所有节点的值大于根节点的值； （4）左右子树都是二叉排序树.

2.2二进制链表的存储结构

二叉树的节点应至少包含三个字段，用于存储节点的数据，左子节点指针leftChild和右子节点指针rightChild. 整个二叉树的链表必须有一个标头指针，该指针指向二叉树的根节点，其作用是充当该树的访问点.

2.3构建二进制排序树

从一个空的二进制排序树开始，经过一系列搜索和插入操作，将生成一个二进制排序树.

根据二进制排序树的定义二叉排序树 数据结构，建立二进制排序树的过程是根据要排序的序列元素的顺序动态生成二进制树的节点，并将它们逐一插入到二进制树中. 如果p是根节点指针，b是要插入的当前元素，则过程可以描述为:

（1）如果它是一棵空树（p = nil），则动态生成一个节点，并且其数据字段是要插入的当前元素

b，左右指针字段为“ null”，p指向节点.

（2）如果不是空树，则将b与根节点数据（p）进行比较

如果b

左右子树的插入方法与二进制排序树的插入方法相同. 不断调用上述插入过程，直到将所有要排序的序列都排序到一个二进制排序树中为止.

可以看出，构建二进制排序树就是多次调用二进制排序树的插入算法.

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