使用ts简单模拟BST
删除部分略微复杂
/**
* 二叉搜索树
*/
type Types = "right" | "left";
// 节点
class BNode{
public data:number;
public left:BNode|null;
public right:BNode|null;
constructor(data:number){
this.data = data;
this.left = null;
this.right = null;
}
}
class BST{
public root:BNode|null;
public dataArr:Array<number>;
constructor(){
this.root = null;
this.dataArr = []; // 用于保存遍历出来的数据
}
public insert(data:number):void{
let node:BNode = new BNode(data);
if(!this.root){
this.root = node;
return
}
this.insertNode(this.root,node);
}
public search(data:number):(BNode|null){
return this.root && this.root.data === data ? this.root : this.searchNode(<BNode>this.root,data);
}
public MiddleOrderTraverse():Array<number>{
if(this.root){
let data = this.MiddleOrderTraverseNode(this.root);
this.dataArr = [];
return data;
}
return []
}
public preOrderTraverse():Array<number>{
if(this.root){
let data = this.preOrderTraverseNode(this.root);
this.dataArr = [];
return data;
}
return []
}
public postOrderTraverse():Array<number>{
if(this.root){
let data = this.postOrderTraverseNode(this.root);
this.dataArr = [];
return data;
}
return []
}
public min():number|null{
if(this.root){
let minVal:number = this.mNode(this.root,"left");
return minVal;
}
return null;
}
public max():number|null{
if(this.root){
let maxVal:number = this.mNode(this.root,"right");
return maxVal;
}
return null;
}
public remove(data:number){
let current = <BNode|null>this.root;
let prev = <BNode|null>null;
let isleft:boolean = true;
// 如果没有根节点并且 节点树没有对应的数据 返回-1
if(this.root === null || !this.searchNode(<BNode>this.root,data)) return -1;
// 删除根节点
if(data === this.root.data) return this.root = null;
// 查找节点删除节点
while(current!.data !== data){
prev = current;
if(current!.data > data){
current = current!.left;
isleft = true;
}else if(current!.data < data){
current = current!.right;
isleft = false;
}
}
// 删除叶子节点
if(current!.left === null && current!.right === null){
return current === this.root ? this.root = null : isleft ? prev!.left = null : prev!.right = null;
// 删除带有一个子节点地节点
// current带有左子节点
} else if(current!.right === null){
current === this.root ?
this.root = current.left
: isleft
? prev!.left = current!.left
: prev!.right = current!.left;
// current带有右子节点
}else if(current!.left === null){
current === this.root ?
this.root = current.left
: isleft
? prev!.left = current!.right
: prev!.right = current!.right;
}else{
let successor:BNode = this.findNode(current!);
if(current === this.root){
this.root == successor
}
isleft ? prev!.left = successor : prev!.right = successor;
successor.left = current!.left;
}
// 删除带有左右子节点
// 找左子树的最大值(前驱) 或者 找右子树最小值(后继), 总之 最贴近原节点
return true;
}
// 查找前驱与后继相关节点
// 查询后继节点
private findNode(node:BNode):BNode{
let successor:BNode = node;
let current:BNode = node.right!;
let successorParent:BNode = node;
// 循环查找
while(current !== null){
successorParent = successor;
successor = current;
current = current.left!;
}
// 判断寻找的后继节点是否直接就是删除node节点的right节点
if(successor != node.right){
successorParent.left = successor.right;
successor.right = node.right;
}
return successor;
}
// 先序遍历递归调用
private preOrderTraverseNode(node:BNode):number[]{
if(node){
this.dataArr.push(node.data);
node.left
? this.preOrderTraverseNode(node.left)
: null
node.right
? this.preOrderTraverseNode(node.right)
: null;
}
return this.dataArr;
}
// 中序遍历递归调用
private MiddleOrderTraverseNode(node:BNode):number[]{
if(node){
node.left
? this.MiddleOrderTraverseNode(node.left)
: null
this.dataArr.push(node.data);
node.right
? this.MiddleOrderTraverseNode(node.right)
: null;
}
return this.dataArr;
}
// 后序遍历
private postOrderTraverseNode(node:BNode):Array<number>{
if(node){
node.left
? this.postOrderTraverseNode(node.left)
: null
node.right
? this.postOrderTraverseNode(node.right)
: null;
this.dataArr.push(node.data);
}
return this.dataArr;
}
// 使用递归获取max/min值
private mNode(node:BNode,type:Types):number{
return node[type] ? this.mNode(<BNode>node[type],type) : node.data;
}
// 查询操作
private searchNode(node:BNode,data:number):BNode|null{
if(node){
if(node.data > data){
return this.searchNode(<BNode>node.left,data);
}else if(node.data === data){
return node;
}else if(node.data < data){
return this.searchNode(<BNode>node.right,data);
}else{
return null;
}
}
return null;
}
// 使用递归方式进行插入操作
private insertNode(node:BNode,newnode:BNode){
try{
if(newnode.data > node.data){
node.right
? this.insertNode(node.right,newnode)
: node.right = newnode;
}else{
node.left
? this.insertNode(node.left,newnode)
: node.left = newnode;
}
}catch(e){
console.log(e);
}
}
}
let bst = new BST();
bst.insert(10);
bst.insert(9);
bst.insert(11);
bst.insert(9.5);
bst.insert(3);
console.log(bst);
console.log(bst.min())
console.log(bst.max())
console.log(bst.preOrderTraverse())
console.log(bst.MiddleOrderTraverse())
console.log(bst.postOrderTraverse())
console.log(bst.search(9));
console.log(bst.remove(11));
console.log(bst.remove(9));
console.log(bst);
