数据结构C语言实现14.自平衡二叉查找树_AVL树
引言 在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 AVL树得名于它的发明者G.M. Adelson- ...
数据结构C语言实现13.二叉搜索树_BST
引言 二叉搜索树(Binary Search Tree),也称BST树、二叉搜索树、有序二叉树(ordered binary tree),排序二叉树(sorted binary tree). 它是指一棵空树或者具有下列性质的二叉树: 1. 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结 ...
数据结构C语言实现12.线索二叉树
引言 我们知道,二叉树遍历的实质是对非线性结构的树进行线性化的过程,它使得每个节点(除了第一个和最后一个节点外)在这种线性序列中有且仅有一个直接前驱和一个直接后继.但是在二叉链表的存储方式中,我们只能找到每个节点的左右孩子信息,而不能直接得到一个节点在先序,中序和后序遍历这一序列中的前驱和后继信 ...
数据结构C语言实现11.二叉树
引言
二叉树是一种非常重要的非线性结构,许多实际问题抽象出来的数据结构往往都是二叉树的形式.与树相比,二叉树更加规范并更具确定性,并且实现二叉树的存储结构及其算法都较为简单,因此二叉树就显得格外重要.
在计算机科学中,二叉树(Binary tree)是每个节点最多有两个子树的树结构。通 ...
数据结构C语言实现10.树
引言 前面我们介绍了的线性表,栈和队列等数据结构都属于线性结构,他们的共同特点是:各元素之间逻辑关系呈现出简单的一对一关系.而非线性结构的各元素之间,其逻辑关系则呈现出一对多或多对多的关系. 树形结构是一类重要的非线性结构,其逻辑关系呈现出一对多的关系.树形结构中元素(结点)之间具有明确的层次 ...
排序_6.归并排序
归并排序简介:
前面介绍的插入排序,交换排序和选择排序这三类排序算法都是将无序的记录序列按关键字的大小排成一个有序序列.而归并排序则是将两个或两个以上的有序序列合并成一个有序序列的过程.
归并排序(Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n ...
排序_5.选择排序
选择排序简介:
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
算法描述:选择排序 ...
排序_4.希尔排序
希尔排序简介:
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
但插入排序一般来说是低效的,因为插入排序每次只能将数 ...
排序_3.插入排序
插入排序简介:所谓插入排序,就是把一个记录按其关键字的大小插入到一个有序的记录序列中,插入后该序列依然有序.
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序在实现上,通常 ...
排序_2.快速排序
快速排序简介:
快速排序(QuickSort)是对冒泡排序的一种改进的交换排序算法,又称 分区交换排序(partition-exchange sort). 在平均状况下,快速排序排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。 事实上,快速 ...