对于二叉搜索树,我们如果要删除一个节点,需要我们比较左右节点大小来找到这个节点,然后再有三种情况,无孩子,一个孩子,两个孩子。
但是,如果针对任意的二叉树(非二叉搜索树),那么如果要删除任意数据,应该怎么C代码实现呢?
我自己写了一个,不知可不可行,大神来给意见呐!
以下是删除功能的代码
struct Node *Find(struct Node *root) { while (root -> left != NULL) root = root -> left; return root; } struct Node *Delete(struct Node *root, int data) { if (root == NULL) return root; if (root -> data != data) { root -> left = Delete(root -> left, data); root -> right = Delete(root -> right, data); } //wohoo....i found you,get ready to delete! else { //case 1 : no child if (root -> left == NULL && root -> right == NULL) { free(root);//C++ --> delete root; root = NULL; } //case 2 : one child else if (root -> left == NULL) { struct Node *temp = root; root = root -> right; free(temp);//C++ --> delete root; } else if (root -> right == NULL) { struct Node *temp = root; root = root -> left; free(temp);//C++ --> delete root; } else//case 3 : two children { struct Node *temp = Find(root);//find a data to replace this deleted data root -> data = temp -> data; root -> left = Delete(root -> left, temp -> data);//Delete the data I found on the left } } return root; }