数据结构和算法.ppt

894101151213614157213894101152112673(a)满二叉树(b)完全二叉树1362455674213(c)非完全二叉树特殊形态的二叉树第30页,共54页，星期六，2024年，5月二叉树的存储结构顺序存储结构用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中第31页,共54页，星期六，2024年，5月abcdhiejklfg(a)完全二叉树(b)非完全二叉树abcdefgh???123456789101112abcdefghijkl(c)完全二叉树的顺序存储形式1234567891011abcde?h??fg(d)非完全二叉树的顺序存储形式第32页,共54页，星期六，2024年，5月链式存储结构设计不同的结点结构可构成不同的链式存储结构。二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点LchilddataRchildLchilddataparentRchild(a)二叉链表结点(b)三叉链表结点链表结点结构形式第33页,共54页，星期六，2024年，5月二叉树的链式存储形式有一棵一般的二叉树，以二叉链表和三叉链表方式存储的结构图二叉树及其链式存储结构(a)二叉树afedcbg(c)三叉链表a??b?c?d?e?f??g?T(b)二叉链表a?b?c?d?e?g??f?T第34页,共54页，星期六，2024年，5月遍历二叉树及其应用遍历二叉树(TraversingBinaryTree)是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。第35页,共54页，星期六，2024年，5月遍历二叉树若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是：DLR——先(根)序遍历。LDR——中(根)序遍历。LRD——后(根)序遍历。第36页,共54页，星期六，2024年，5月构建二叉有哪些信誉好的足球投注网站树又名二叉排序树用递归的方法构建树实现对树的增删改查功能第37页,共54页，星期六，2024年，5月算法第38页,共54页，星期六，2024年，5月查找算法顺序查找从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。第39页,共54页，星期六，2024年，5月查找算法二分法查找先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。第40页,共54页，星期六，2024年，5月查找算法二分法查找第41页,共54页，星期六，2024年，5月排序算法排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程，其定义为：给定一组记录序列：{R1,R2