K*********n
发帖数: 2852 | 1 是一般意义的二叉树，不是二叉搜索树(BST)。
对于BST，如果待删节点有两个孩子，那么就可以把左子树最右的叶子结点或者右子树最
左的叶子结点搞上来取代删掉的结点，这样保持BST的性质不变。
假如是个普通的二叉树，怎么办呢……网上找了半天都是BST的，CLRS里面说的也是BST
。
我想，一个最简单的办法就是随便找一个叶子结点，来取代删掉的结点就可以了，因为
一般二叉树没有说有什么性质的限定，所以就不care了。一般是不是没有给定树的性质
的限定，不必在乎这种一般的二叉树的删除问题？ |
h**********l
发帖数: 6342 | 2 难道不是吗？
树最
BST
【在 K*********n 的大作中提到】
: 是一般意义的二叉树，不是二叉搜索树(BST)。
: 对于BST，如果待删节点有两个孩子，那么就可以把左子树最右的叶子结点或者右子树最
: 左的叶子结点搞上来取代删掉的结点，这样保持BST的性质不变。
: 假如是个普通的二叉树，怎么办呢……网上找了半天都是BST的，CLRS里面说的也是BST
: 。
: 我想，一个最简单的办法就是随便找一个叶子结点，来取代删掉的结点就可以了，因为
: 一般二叉树没有说有什么性质的限定，所以就不care了。一般是不是没有给定树的性质
: 的限定，不必在乎这种一般的二叉树的删除问题？
|
K*********n
发帖数: 2852 | 3 就是，不会考这种问题是吧。好久不复习数据结构，今天写一个非BST的二叉树，写着写
着就遇到这个问题了，手生，莫笑哈。
【在 h**********l 的大作中提到】
: 难道不是吗？
:
: 树最
: BST
|
p*****2
发帖数: 21240 | 4
树最
BST
随便找个叶子写起来也不是很简洁吧？
【在 K*********n 的大作中提到】
: 是一般意义的二叉树，不是二叉搜索树(BST)。
: 对于BST，如果待删节点有两个孩子，那么就可以把左子树最右的叶子结点或者右子树最
: 左的叶子结点搞上来取代删掉的结点，这样保持BST的性质不变。
: 假如是个普通的二叉树，怎么办呢……网上找了半天都是BST的，CLRS里面说的也是BST
: 。
: 我想，一个最简单的办法就是随便找一个叶子结点，来取代删掉的结点就可以了，因为
: 一般二叉树没有说有什么性质的限定，所以就不care了。一般是不是没有给定树的性质
: 的限定，不必在乎这种一般的二叉树的删除问题？
|
K*********n
发帖数: 2852 | 5 还好啊，就while一下，顺着左边或者右边找到一个叶子，拿上来就行了。反正没有限定
。我主要觉得，想这样的问题是不是很蛋疼……
【在 p*****2 的大作中提到】
:
: 树最
: BST
: 随便找个叶子写起来也不是很简洁吧？
|
p*****2
发帖数: 21240 | 6
限定
把代码发上来看看。
【在 K*********n 的大作中提到】
: 还好啊，就while一下，顺着左边或者右边找到一个叶子，拿上来就行了。反正没有限定
: 。我主要觉得，想这样的问题是不是很蛋疼……
|
K*********n
发帖数: 2852 | 7 Node *del(Node *tree, int n){
Node *nodeFather = tree -> father;
if (tree -> val == n){
if (tree -> left == NULL && tree -> right == NULL){ // a leaf
if (nodeFather -> left == tree){
nodeFather -> left == NULL;
free(tree);
return nodeFather;
}else{
nodeFather -> right == NULL;
free(tree);
return nodeFather;
}
}else if (tree -> left == NULL){
// the node to delete has only one child - right
if (nodeFather -> left == NULL){
// tree is the right child of its father
nodeFather -> right = tree -> right;
free(tree);
return nodeFather;
}else{ // tree is the left child of its father
nodeFather -> left = tree -> right;
free(tree);
return nodeFather;
}
}else if (tree -> right == NULL){
// the node to delete has only one child - left
if (nodeFather -> left == NULL){
nodeFather -> right = tree -> left;
free(tree);
return nodeFather;
}else{
nodeFather -> left = tree -> left;
free(tree);
return nodeFather;
}
} else {
// the node to delete has two children
}
} else { // n not found, continue searching recursively
}
}
后两个else没写，问题就是出现在倒数第二个else，也就是待删节点有两个孩子的情况
，出现了问题，就上来问了。如果是随便找个叶子拿上来的话，那很容易。
【在 p*****2 的大作中提到】
:
: 限定
: 把代码发上来看看。
|
p*****2
发帖数: 21240 | 8
还有parent？你原贴里没说呀。
【在 K*********n 的大作中提到】
: Node *del(Node *tree, int n){
: Node *nodeFather = tree -> father;
: if (tree -> val == n){
: if (tree -> left == NULL && tree -> right == NULL){ // a leaf
: if (nodeFather -> left == tree){
: nodeFather -> left == NULL;
: free(tree);
: return nodeFather;
: }else{
: nodeFather -> right == NULL;
|
K*********n
发帖数: 2852 | 9 结点定义应该有father的吧：
typedef struct NODE(){
int val;
struct NODE *father;
struct NODE *left;
struct NODE *right;
}Node;
【在 p*****2 的大作中提到】
:
:
: 还有parent？你原贴里没说呀。
|
p*****2
发帖数: 21240 | 10
为什么应该有father呢？
【在 K*********n 的大作中提到】
: 结点定义应该有father的吧：
: typedef struct NODE(){
: int val;
: struct NODE *father;
: struct NODE *left;
: struct NODE *right;
: }Node;
|
|
|
p*****2
发帖数: 21240 | 11
你这个能删除root吗？
【在 K*********n 的大作中提到】
: Node *del(Node *tree, int n){
: Node *nodeFather = tree -> father;
: if (tree -> val == n){
: if (tree -> left == NULL && tree -> right == NULL){ // a leaf
: if (nodeFather -> left == tree){
: nodeFather -> left == NULL;
: free(tree);
: return nodeFather;
: }else{
: nodeFather -> right == NULL;
|
K*********n
发帖数: 2852 | 12 没有写root的问题，这个写得很糙，是只写了很一般的情况
【在 p*****2 的大作中提到】
:
: 你这个能删除root吗？
|
K*********n
发帖数: 2852 | 13 好吧，这个确实不是必须定义的。实现不用管，主要是说算法。
【在 p*****2 的大作中提到】
:
: 你这个能删除root吗？
|
p*****2
发帖数: 21240 | 14
所以想写简洁不容易呀。我看你代码行数已经超过30行了，而且有parent，还没有包括
所有情况。
你看能不能写一个不超过30行的，没有parent，的全部代码？
【在 K*********n 的大作中提到】
: 没有写root的问题，这个写得很糙，是只写了很一般的情况
|
K*********n
发帖数: 2852 | 15 嗯，没有parent就完全不一样了。如果要简洁的话，那些if的部分确实需要好好整整，
有些条件判断是重复的。
【在 p*****2 的大作中提到】
:
: 所以想写简洁不容易呀。我看你代码行数已经超过30行了，而且有parent，还没有包括
: 所有情况。
: 你看能不能写一个不超过30行的，没有parent，的全部代码？
|
K*********n
发帖数: 2852 | 16 谢谢指导，我打算直接写BST版本了，再贴
【在 p*****2 的大作中提到】
:
: 所以想写简洁不容易呀。我看你代码行数已经超过30行了，而且有parent，还没有包括
: 所有情况。
: 你看能不能写一个不超过30行的，没有parent，的全部代码？
|
p*****2
发帖数: 21240 | 17
我觉得不是BST的挺好。我今天有时间练练。
主要考虑的是时间复杂度，空间复杂度要最优。还要保持balanced
【在 K*********n 的大作中提到】
: 谢谢指导，我打算直接写BST版本了，再贴
|
K*********n
发帖数: 2852 | 18 复杂度我觉得还好，这么写，如果是recursion的话。迭代的不好写。要是搞balance的
话，那就又复杂多了，再拓展到多叉树……哇哈哈
【在 p*****2 的大作中提到】
:
: 我觉得不是BST的挺好。我今天有时间练练。
: 主要考虑的是时间复杂度，空间复杂度要最优。还要保持balanced
|
p*****2
发帖数: 21240 | 19 我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root |
K*********n
发帖数: 2852 | 20 我没有看出问题来，加一个merge确实是简洁了很多，不需要显式讨论被删结点有几个孩
子了！
【在 p*****2 的大作中提到】
: 我写了一个
: def merge(node1, node2):
: if node1==None or node2==None:
: return node1 if node2==None else node2
: node1.right=merge(node2,node1.right)
: return node1
: def delete(root, node):
: if root==None:
: return None
: elif root==node:
|
Z*****Z
发帖数: 723 | 21 膜拜
【在 p*****2 的大作中提到】
: 我写了一个
: def merge(node1, node2):
: if node1==None or node2==None:
: return node1 if node2==None else node2
: node1.right=merge(node2,node1.right)
: return node1
: def delete(root, node):
: if root==None:
: return None
: elif root==node:
|
