《数据结构学习笔记.docx》由会员分享，可在线阅读，更多相关《数据结构学习笔记.docx（10页珍藏版）》请在三一办公上搜索。
1、数据结构1 .数据结构的分类：1.按逻辑结构分类：集合；线性结构【一维数组；队列；栈】非线性结构【树；图;多维数组】按存储结构分类：顺序存储；链式存储；索引存储；散列存储2 .树和二叉树1. 树树的度数的总和加1等于树的结点数之和。N=K+1.树的遍历：前序遍历【先根结点，后子结点】；后序遍历【先叶子结点，后根结点】； 层次遍历【按树的结构层次遍历】2. 二叉树的重要特性；（1）在二叉树的第i层上最多有2的（i1）次方个结点。（2）深度为k的二叉树最多有2的k次方一1个结点。（3）对于任何一棵二叉树，其叶子结点数为N0,度为2的结点数为N 2,则No=N2+1。（4）如果对一棵有n个结点的完全
2、二叉树的结点按层序编号（从第一层到_log2n_l+1层，每层从左到右），则对任一结点i （IMiMn），有：如果i=1，则结点i无父结点，是二叉树的根；如果i1，则父结点是l_i/2_l。如果2in，则结点i为叶子结点，无左结点；否则，其左子结点为2i。如果2i+1n，则结点i无右子结点，否则，其右子结点为2i。二叉树的遍历:前序遍历【根一左一右】；中序遍历【左一根一右】；后序遍历【左一根右】；层次遍历【按层次遍历】树到二叉树之间的转换：规则：同层结点中只保留左子树结点，其余兄弟结点均转换为右子树。依次类推。方法：只保留父结点与其下的左子结点的连线，其他所有结点连线删除。水平连接 同根的兄弟
3、结点，然后整理成二叉树。注意：二叉树的中序遍历和树的后序遍历是对应的。可以依次检验转换是否正确。3. 查找二叉树(二叉排序树)一颗查找二叉树，或者是一颗空树，或者满足以下递归条件：(1) 查找树的左、右子树各是一颗查找树。(2) 若查找树的左子树非空，则其左子树的各节点值均小于根节点的值。(3) 若查找树的右子树非空，则其右子树上的各节点值均大于根节点的值。查找二叉树的插入结点操作，分以下几种情况进行相应处理：(1) 如果相同键值的结点已经在二叉树中，则不再插入。(2) 如果查找二叉树是空树，则以新结点为查找二叉树。(3) 将要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点
4、的左子结点，还是右子结点，并进行相应插入。查找二叉树上删除一个节点时，要考虑三种情况：(4) 若待删除的节点p是叶子节点，直接删除。(5) 若待删除节点p只有一个子节点，则将这个子节点与待删除节点的父节点直接 连接。(6) 若待删除节点p有两个子节点，则在其左子树上用中序遍历查找关键值最大的 节点S，用节点S的值代替节点P的值。4. 最优二叉树(哈夫曼树)树的带权路径长度最小的树称为最优二叉树。树的带权路径长g=SUM (叶子节点的权 树*叶子节点的路径长度) 节点的路径长度为节点到根节点的长度。哈夫曼树的构造：(1) 将所有的权值作为根节点构造森林。(2) 从中选择两个根的权值最小的树作为左
5、右子树构造一颗新树，将这两颗树从 森林中删除，并将新树添加进去。(3) 重复步骤(2)直到森林中只有一颗树。数据结构与昇法基础及c =希赛树;8、线:A3和二叉树索二叉树专索二叉树的表示Lbit LchildDataRchildRbit对标志域规定如下：LbijO, Lchild是通常的指针Lbit=1, Lchild是线索Rbit=O, Rchild是通常的指针Rbit=1, Rchild是线索-www.CSAI.cn根据前序排列(A B D EH C F G I )填充空指针的左右指针。中序和后序排列也是同 样的方法。数据结构与舁法基础树和二叉树8、平衡二叉树平衡二叉树的定义平衡二叉树(Balanced Binary Tree)o它或者是一棵空树；或者是一棵这样的树：树中任一结点的左、右子树的深度相差不超过1。如定义结点的平衡度为其右子树的深度减去其左子树的深度，则对于平衡 查找树，它的每个结点的平衡度只能为-1, 0, 1三个值之一。www.CSAI.cn数据结构与算法基础树和二叉树ARR型平衡旋转（单向左旋平衡处理）www.CSAI.cn希赛数据结构与舁法基础不错，分享一下
