本文共 3250 字，大约阅读时间需要 10 分钟。
。。。这一部分真心让我懵逼，可能是我太笨的缘故吧。。。。
二叉搜索树的删除操作。。。具体方法要分情况，
1. 若删除的节点没有孩子的时候，直接删除此节点，然后将父节点NULL；
2.若删除的节点有一个孩子的时候，直接将父节点连接到其孩子节点，然后删除此节点。
3.若有两个节点的时候，这时候就要找个节点代替它了，因为二叉搜索树具有左子树比此节点的值都小，右子树比此节点的值大，所以（1）可以找左子树中节点最大的元素，也就是左子树中最右端的元素，（2）也可以找右子树中节点最小的元素，也就是右子树中最左端的节点。让此节点的值等于子树中选出的值，然后删除子树中的节点，因为被删除的节点不是在最右端就是在最左端，所以可知此节点只有一个孩子。。。。然后转到第二种情况。。。
可以看出，这三种情况都需要记住父节点的地址。。。。
然后看浙大数据结构视频这一节视频给出的代码让我好懵逼，好不容易才理解。。。
#include #include #include #include using namespace std;typedef struct tree{ int data; struct tree *left,*right;}tree,*Tree;//创建二叉搜索树;Tree Create(Tree t,int data){ if(t) { if(t->data>=data) t->left=Create (t->left,data); else t->right=Create (t->right,data); } else { t=(Tree)malloc(sizeof(tree)); t->data=data; t->left=t->right=NULL; } return t;}//先序遍历二叉搜索树;void Traverse (Tree t){ if(t) { printf("%d ",t->data); Traverse (t->left); Traverse (t->right); }}//找到子树中最小的节点的地址;Tree FindMin(Tree t){ if(t) while (t->left) { if(t->left) t=t->left; } return t;}Tree Delete (Tree t,int data){ //要被删除的节点 Tree temp=NULL; if(!t) printf("好像没有此元素呢\n"); else if(t->data>data) t->left=Delete (t->left,data); else if(t->data right=Delete (t->right,data); else { //有两个子节点时 if(t->left&&t->right) { temp=FindMin(t->right); t->data=temp->data; //下面一定是t->data;因为要找到最小元素并删除它... t->right=Delete (t->right,t->data); } else { //这里挺让人懵逼的，多想想就好了... temp=t; if(!t->left) t=t->right; else if(!t->right) t=t->left; free(temp); } } return t;}int main(){ Tree t=NULL; int n,temp; scanf("%d",&n); for (int i=0;i
例题为Leetcode的 Delete Node in a BST
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 5 / \ 4 6 / \2 7另一个正确答案是 [5,2,6,null,4,null,7]。 5 / \ 2 6 \ \ 4 7
这里用的是递归
Java代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root==null) return root; if(root.val key) root.left=deleteNode (root.left,key); else { if(root.left==null||root.right==null) { if(root.left==null) return root.right; else return root.left; } else { TreeNode t=root.left; while (t.right!=null) t=t.right; root.val=t.val; root.left=deleteNode (root.left,t.val); } } return root; }}
转载地址：http://jjaen.baihongyu.com/