一种无需借助栈的严格平衡二叉树建立  

A method to establish a strict balance two fork tree without the help of a stack

作　　者：魏志威 王防修[1] 

机构地区：[1]武汉轻工大学数学与计算机学院,湖北武汉430023

出　　处：《武汉轻工大学学报》2015年第4期47-50,共4页Journal of Wuhan Polytechnic University

基　　金：武汉轻工大学校级大学生创新创业训练计划项目(xsky2015031)

摘　　要：针对当前严格平衡二叉树的建立需要借助栈来实现的问题,提出一种无需借助栈也能建立严格平衡二叉树的算法。为能对关键字进行二分查找,需要对现有的关键字序列进行排序,以便统计关键字的有序序列中每个关键字在二分查找时的比较次数。在统计完所有关键字的二分查找的比较次数后,通过关键字比较次数序列的排序得到严格平衡二叉树序列。最后,用非递归的二叉排序树插入算法依次插入严格平衡二叉树序列的每个关键字,得到的二叉排序树就是一棵严格平衡二叉树。算例仿真表明,无需借助栈也可建立一棵严格平衡二叉树。Because establishment of a strict balanced two binary tree needs the help of the stack,this paper presents an algorithm to establish a strict balanced two binary tree without the help of the stack. In order to search for keywords in half,it needs to sort the existing keyword sequence. It statistics the number of comparision in binary search in the ordered keyword sequence. A strict balanced binary tree sequence will be obtained by the sortion of the times of comparison of the keywords after the statistics. Finally,a strict balance two fork tree is obtained after every keyword has been successively inserted into the two binary sort tree on non recursive insertion algorithm. The results of the examples show that a strict balance two fork tree can also be established without the help of the stack.

关 键 词：选择排序 二叉排序树 严格平衡二叉树 二分查找 查找效率 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]