二叉排序树（Binary Sort Tree，二叉查找树，二叉搜索树） - JAVA

x == y->right) { x = y; y = x->parent; } return y; } int DeleteNode(PNode &root,ElemType key) { PNode q; //查找到要删除的结点 PNode p = Search(root, key); //没查到此关键字 if(p == NULL) return 0; //一共有四种情况，该节点是叶子节点、只有左孩子、只有右孩子、左右孩子都有 //叶子结点 if(p->left == NULL && p->right == NULL) { //只有根节点 if(p->parent == NULL) { free(p); root = NULL; } else { //删除的结点是左孩子 if(p->parent->left == p) p->parent->left = NULL; else p->parent->right = NULL; free(p); } } //左孩子 else if(p->left != NULL && p->right == NULL) { p->left->parent = p->parent; //如果删除是根结点 if(p->parent == NULL) root = p->left; //父节点的左孩子 else if(p->parent->left == p) p->parent->left = p->left; else p->parent->right = p->left; free(p); } //右孩子 else if(p->right != NULL && p->left == NULL) { p->right->parent = p->parent; //如果删除是根结点 if(p->parent == NULL) root = p->right; //是父节点的左孩子 else if(p->parent->left == p) p->parent->left=p->right; else p->parent->right=p->right; free(p); } //左右孩子都有 //该结点的后继结点肯定无左子树 //删掉后继结点,后继结点的值代替该结点 else { //找到要删除结点的后继 q = SearchSuccessor(p); ElemType temp = q->key; //暂存后继结点的值 //删除后继结点 DeleteNode(root, q->key); p->key = temp; } return 1; } //创建树 void Create(PNode& root, ElemType *keyArray, int length) { for(int i = 0; i < length; i++) Insert(root, keyArray[i]); //插入 } int main() { PNode root = NULL; ElemType nodeArray[11] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9}; //二叉数 Create(root, nodeArray, 11); //创建二叉搜索数 cout<<"该节点的值"<

key< right->right)->key< left->right->right)->key< key< left)->key< left->right->left)->key< o(∩_∩)o

二叉排序树（Binary Sort Tree，二叉查找树，二叉搜索树）(二)