当前位置: 首页 > >

二叉树删除节点

发布时间:

二叉树删除节点的分为三种情况:
①当待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null。
②待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点。
③待删除节点包含两个子节点,那么我们可以采用两种方式,一种是查找待删除节点左子树上的最大值,一种是查找待删除节点右节点上的最小值。
先如今我先采用后中方式:找Min 值 作为临时节点 ?->>>顶替删除的节点??>>>>>>删除这个临时节点。



代码解析:
getSmallest: 是获取Min的函数。
remove:
removeNode:(这个函数才是关键,需要自己明白每一步,最好每一步都自己console.log一遍)

function getSmallest( node ){
while(node.left != null ){
node = node.left;
}
return node;
}

function remove( data ){
root = removeNode( this.root, data );
}

function removeNode(node, data){
if( node == null ){
return null;
}
if( data == node.data ){
if( node.left == null && node.right == null ){
return null;
}
if( node.left == null ){
return node.right;
}
if(node.right == null){
return node.left;
}
var tempNode = getSmallest(node.right);
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
}else if( data < node.data ){
node.left = removeNode( node.left, data );
return node;
}else{
node.right = removeNode(node.right, data);
return node;
}
}



----------
附录完整的代码:

function Node(data, left, right){
this.data = data;
this.show = show;
this.left = left;
this.right = right;
}

function show(){
return this.data;
}

function BST(){
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
this.remove = remove;
this.removeNode = removeNode;
this.getSmallest = getSmallest;
}

function insert(data){
var n = new Node( data, null, null );
if( this.root == null ){
this.root = n;
}else{
var current = this.root;
var parent;
while(true){
if( data < current.data ){
parent = current;
current = current.left;
if( current == null ){
parent.left = n;
break;
}
}else{
parent = current;
current = current.right;
if( current == null ){
parent.right = n;
break;
}
}
}
}
}

function inOrder( node ){
if( !( node == null ) ){
inOrder(node.left);
console.log( node.show() + " " );
inOrder(node.right);
}
}
function getSmallest( node ){
while(node.left != null ){
node = node.left;
}
return node;
}

function remove( data ){
root = removeNode( this.root, data );
}

function removeNode(node, data){
if( node == null ){
return null;
}
if( data == node.data ){
if( node.left == null && node.right == null ){
return null;
}
if( node.left == null ){
return node.right;
}
if(node.right == null){
return node.left;
}
var tempNode = getSmallest(node.right);
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
}else if( data < node.data ){
node.left = removeNode( node.left, data );
return node;
}else{
node.right = removeNode(node.right, data);
return node;
}
}


var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("After sort:");
console.log( nums.inOrder( nums.root ) );
nums.remove(3);
console.log("after remove: ");
console.log( nums.inOrder( nums.root ) );
nums.remove(45);
console.log("after remove: ");
console.log( nums.inOrder( nums.root ) );

最后附上测试截图:


说一下:这里的核心代码是在 《数据结构与算法 Javascript描述》中
大家伙最*去看看吧



友情链接: