数据结构笔记

1.冒泡排序:是相邻的两个元素之间比较,将关键字大
的元素放在后面,一趟排序结束后最大的元素排在了最
后面。
2.快速排序:是以第一个元素为基准,经过一趟排序后
,将记录分成两个部分,第一部分都比基准元素小,而
另一部分都比基准元素大。先从右往左找,比基准小的
与基准对换位置,再从左往右找,把比基准大的与基准对换位置,和基准一样的不变
3.直接插入排序:是将一个记录插入到已排好序的有序
表中,从而得到一个新的、记录数增1的有序表。
4.希尔排序:先将间隔N分成1组,组内进行直接插入排
序,小的数放在左边,大的数放在右边
5.深度优先搜索:类似先序遍历,先进入最深一级的结
点,再返回上一级节点进入兄弟节点
6.广度优先搜索:类似按层遍历,搜索完一层再进入下
一层
7.邻接表:表示图的相邻关系,顶点以Vi表示,一般V1
以0或1表示
8.先根遍历:先访问根节点,然后左、右
9.后根遍历:先访问左右,最后访问根节点
10.中根遍历,先访问左,再根节点,最后访问右
11.ltag或rtag为0,指向lchild或rchild
12.结点的度:结点拥有的子树数
13.叶子结点:度为0的结点
13.分支结点:度不为0的结点
14.树的度:树内各结点的度的最大值
15.二叉树定义:每个结点最多两颗子树