二叉查找树（BST）AS3版

￡神魔★判官ぃ 2022-08-25 12:51 172阅读 0赞

也称为二叉搜索树或者二叉排序树（Binary Search Tree）二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：  
１、每个结点都有一个作为查找依据的关键码(key)，所有结点的关键码互不相同。  
２、左子树(如果存在)上所有结点的关键码都小于根结点的关键码。  
３、右子树(如果存在)上所有结点的关键码都大于根结点的关键码。  
４、左子树和右子树也是二叉查找树。  
  
定义一个BST：  
  
  
package kono.utils.collections  
\{  
import kono.utils.BTnode;  
  
//二叉查找树（BST）， binary search tree （BST）  
public class BStree implements Icollection  
\{  
//二叉查找树根结点， the root node of the binary search tree  
private var tree:BTnode;  
  
//查找判断的依据函数，  
//the compare function will use to confirm that the left child????s data is less than the current data,  
//while the right child????s data is greater than the current data  
private var compare:Function;  
  
//默认的判断函数判读的依据是BST存储了整数， default function used for the integer comparing  
public function BStree(compareTo:Function = null)  
\{  
tree = null;  
if(compareTo == null)  
\{  
compare = function(a:Number, b:Number):int  
\{  
return int(a - b);  
\}  
\}  
else  
\{  
compare = compareTo;  
\}  
\}  
  
//增加一个数据到BST， add a new data to BST  
public function add(data:\*):void  
\{  
var cursor:BTnode = tree;  
var done:Boolean = true;  
if(!tree)  
\{  
tree = new BTnode(data);  
\}  
else  
\{  
while(done)  
\{  
if(compare(data, cursor.nodeData) <= 0)  
\{  
if(cursor.leftChild)  
\{  
cursor = cursor.leftChild;  
\}  
else  
\{  
cursor.leftChild = new BTnode(data);  
done = false;  
\}  
\}  
else  
\{  
if(cursor.rightChild)  
\{  
cursor = cursor.rightChild;  
\}  
else  
\{  
cursor.rightChild = new BTnode(data);  
done = false;  
\}  
\}  
\}  
\}  
\}  
  
//从BST中删除一个指定数据， remove a given data from the BST;  
//@ target： 要删除的数据，如果删除成功返回true，失败或未找到返回false，  
//@ target： to remove from the BST, return true if success, and return false if failed or can not find it in the BST  
public function remove(target:\*):Boolean  
\{  
var cursor:BTnode = tree;  
var parentCursor:BTnode = null;  
var t:int;  
while(cursor)  
\{  
t = compare(target, cursor.nodeData)  
if(t == 0)  
\{  
if(cursor == tree && cursor.leftChild == null)  
\{  
tree = tree.rightChild;  
return true;  
\}  
if(cursor.leftChild == null)  
\{  
if(cursor == parentCursor.leftChild)  
\{  
parentCursor.leftChild = cursor.rightChild;  
return true;  
\}  
else  
\{  
parentCursor.rightChild = cursor.leftChild;  
return true;  
\}  
\}  
else  
\{  
cursor.nodeData = cursor.leftChild.rightMostData;  
cursor.leftChild.removeRightMost();  
return true;  
\}  
\}  
else  
\{  
parentCursor = cursor;  
cursor = t < 0 ? cursor.leftChild : cursor.rightChild;  
\}  
\}  
return false;  
\}  
  
//清空BST， clear all the items in the BST  
public function clear():void  
\{  
tree = new BTnode(null);  
tree = null;  
\}  
  
//返回BST中包含的结点， get the total number in the BST  
public function get size():uint  
\{  
return BTnode.getSize(tree);  
\}  
  
//中序转换结点数据到array中， write all of the data in the BST into a Array  
public function toArray():Array  
\{  
var a:Array = new Array();  
var inorder:Function = function (node:BTnode):void  
\{  
a.push(node.nodeData);  
\}  
tree.inorderPrint(inorder);  
return a;  
\}  
  
//判断BST是否包含给定数据， check if the BST contains the given item  
public function contains(item:\*):Boolean  
\{  
var cursor:BTnode = tree;  
var t:int;  
while(cursor)  
\{  
t = compare(item, cursor.nodeData)  
if(t == 0)  
return true;  
else  
\{  
cursor = t < 0 ? cursor.leftChild : cursor.rightChild;  
\}  
\}  
return false;  
\}  
  
//打印BST结构， print the BST????s frame  
public function print():void  
\{  
tree.print(2);  
\}  
  
//返回BST的信息， return a string representing the BST  
public function toString():String  
\{  
return "\[BStree, size=" + size + "\]";  
\}  
\}  
\}  
  
本文转自  
[http://www.moorwind.com/read.php?41][http_www.moorwind.com_read.php_41]

[http_www.moorwind.com_read.php_41]: http://www.moorwind.com/read.php?41