《二叉排序树的查找与性能分析.docx》由会员分享，可在线阅读，更多相关《二叉排序树的查找与性能分析.docx（3页珍藏版）》请在三一办公上搜索。
1、二叉排序树的查找与性能分析二叉排序树的查找与性能分析 问题分析： 本实验是通过建立一个二叉树，并通过输入报名号，查找出与此报名号对应的学生的其他信息，并通过查找的次数来分析此程序的性能，最后与做平衡二叉树的查找与性能分析的那组比较，分析。 设计思路： 首先进行二叉链表的存储表示，将数据类型和基本操作定义好。 一 二叉排序树的查找 二叉排序树的查找包含二叉排序树的建立，二叉排序树的插入，二叉树的遍历，二叉排序树的生成，以及二叉排序树的查找等部分。 1 二叉排序树的建立 二叉数是每个结点至多只有两颗子树的树形结构即左子树和右子树，在二叉树的第i层上至多有2(i-1)个结点。 而二叉排序树是动态的，
2、中序遍历后，二叉排序树将是一个递增有序序列。二叉排序树可以是一个空树，也可以是一个有如下性质的二叉树： 左子树非空，左子树上所有结点的值均小于根结点的值； 右子树非空，右子树上所有结点的值均大于根结点的值； 左右子树本身又各是一颗二叉排序树。 利用链式存储结构，由一个数据元素和分别指向左右结点的指针构成，即二叉链表。首先可以按线序次序输入二叉树结点的值，如果是空指针则为空树，这样就可以生成根结点，再利用递归构造左子树和右子树。并将关键字即学号插入二叉排序中; 在建立时就可将二叉树中序遍历。 2 二叉排序树的插入 在二叉排序树中插入新节点，要保证插入后的二叉树仍然符合二叉排序树的定义。插入过程如
3、下: 若二叉排序树为空，则待插入结点s作为根结点插入到空树中； 当非空时，将待插结点关键字s-key和树根关键字t-key进行比较，若s-keyt=t-key，则无需插入；若s-keykey，则插入到根的左子树；若s-keyt-key，则插入到根的右子树。而子树的插入过程与树中的插入过程相同。 如此进行下去，知道把结点s作为新的树叶插入到二叉排序树中，或者直到发现已相同的关键字结点为止。 3 二叉排序树的遍历 利用递归算法可以对二叉树进行遍历，中序访问左子树，再访问根结点，最后中序访问右子树。 4 二叉排序树的生成 从空的二叉树开始，经过一系列的查找，插入操作以后，生成了一颗二叉排序树。 且注
4、意每次插入的新节点都是二叉排序树上的新的叶子节点；由不同的顺序的关键字序列，会得到不同的二叉树；对于一个任意的关键字序列构造一颗二叉排序树，其实质上对关键字进行排序。 5 二叉排序树的查找 在二叉排序树中进行查找的过程和二分查找类似，也是一个通过比较关键字，逐步缩小查找范围的过程。 若查找成功，则是一条从根结点到待查结点的路径；若查找失败，则是一条根结点到某个叶子结点的路径，由上可知，查找过程中和关键字比较的次数不超过树的深度。 二 二叉排序树查找的性能分析 由于所要查找的数据量不同，则其查找的性能也不同。且二叉排序树的平均查找长度与树的形态有关。最好情况是：二叉排序树和二叉判定树形态相同；最坏情况是：二叉排序树为单支树，则其平均查找长度与顺序查找相同。 分别输入不同的二叉排序树观察并计算其平均查找长度及时间空间复杂度 将已给的信息建立二叉树，且根据学号查找数据并显示，并判断此方法的性能。
