二叉查找树某个结点的左子树的值都比它小，其右子树的值比它大。
要实现的主要操作
代码实现
#include <iostream> using namespace std;// BST的结点 typedef struct node{int key;struct node *lChild, *rChild,*parent;}Node, *BST;BST lvis=NULL;//用来保存父节点的地址void createBST(BST &p);void assignmentParent(BST p);//给所有的结点的父节点赋值。// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST bool BSTInsert(Node *&p, int element){if (p == NULL){p = new Node;p->key = element;p->lChild = p->rChild = NULL;}if (element == p->key){return false;}if (element < p->key){BSTInsert(p->lChild, element);}elseBSTInsert(p->rChild, element);return true;}void PrintBST(BST &p, int depth){BST &p1=p;int i;if (p1->rChild)PrintBST(p1->rChild, depth + 1);for (i = 1; i <= depth; i++)printf(" ");printf("%d\n", p1->key);if (p1->lChild)PrintBST(p1->lChild, depth + 1);}BST search(BST p, int key){if (p == NULL){printf("此树为空！\n");return NULL;}else if (key == p->key){printf("查找成功!,%d的地址是%p\n", key, p);return p;}else if (key < p->key)search(p->lChild, key);elsesearch(p->rChild, key);}void createBST(BST &p){int t;int depth = 0;p = NULL;printf("\n请输入关键字(以-123结束建立平衡二叉树):");scanf("%d", &t);while (t != -123){BSTInsert(p, t);printf("\n请输入关键字(以-123结束建立平衡二叉树):");scanf("%d", &t);}assignmentParent(p);//这个函数的目的是为了给所有节点的父节点赋值。printf("\n****************************************************\n");printf("*******************您创建的二叉树为*******************\n");if (p)PrintBST(p, depth);elseprintf("这是一棵空树!\n");printf("********************二叉树创建完成*********************\n");}void Maximum(BST p){BST p1=p;while(p1->rChild){p1=p1->rChild;}printf("Maximum=%d",p1->key);}void Minmum(BST p){BST p1=p;while(p1->lChild){p1=p1->lChild;}printf("Minimum=%d",p1->key);}bool Insert(BST &p,int element){if (p == NULL){p = new Node;p->key = element;p->lChild = p->rChild = NULL;}if (element == p->key){return false;}if (element < p->key){Insert(p->lChild, element);}elseInsert(p->rChild, element);return true;}void get_parent(BST &p){if (p){printf("%d->parent=%p",p->key,p->parent);get_parent(p->lChild);get_parent(p->rChild);}}void assignmentParent(BST p){if (p){p->parent=lvis;lvis=p;assignmentParent(p->lChild);lvis=p;assignmentParent(p->rChild);}}//先序遍历void preorderBST(BST p){if (p){cout << p->key << " ";preorderBST(p->lChild);preorderBST(p->rChild);}}//中序遍历（这个可以做为排序算法void inorderBST(BST p){if (p){inorderBST(p->lChild);cout << p->key << " ";inorderBST(p->rChild);}}//后序遍历void postrderBST(BST p){if (p){postrderBST(p->lChild);postrderBST(p->rChild);cout << p->key << " ";}}void Delete(BST p,int key){BST p1=p;//删除要分三种情况while(p1->key!=key){if(key>p1->key)p1=p1->rChild;elsep1=p1->lChild;}//第一种情况：如果z没有孩子结点，则只是简单的将它删除，并修改它的父节点。用NIL作为孩子来替换z（现在还没有考虑其为根节点）if(p1->lChild==NULL&&p1->rChild==NULL){if(p1->parent==NULL){printf("已经删除根节点！，此时树为空哦\n");p=NULL;return;}if(p1->key<p1->parent->key)p1->parent->lChild=NULL;elsep1->parent->rChild=NULL;}//第二种情况：如果只有一个孩子，则将这个孩子提升到树中z的位置上，并修改z的父节点，，用z的孩子来替换z{if(p1->lChild!=NULL&&p1->rChild==NULL){if(p1->key<p1->parent->key){p1->parent->lChild=p1->lChild;p1->lChild->parent=p1->parent;}else{p1->parent->rChild=p1->lChild;p1->lChild->parent=p1->parent;}}if(p1->rChild!=NULL&&p1->lChild==NULL){if(p1->key<p1->parent->key){p1->parent->lChild=p1->rChild;p1->rChild->parent=p1->parent;}else{p1->parent->rChild=p1->rChild;p1->rChild->parent=p1->parent;}}//第三种情况if(p1->lChild!=NULL&&p1->rChild!=NULL){Node *y=p1->rChild->lChild;while(y!=NULL)y=y->lChild;//先用y的右孩子替换yy->rChild->parent=y->parent;//用y替换zy->rChild=p1->rChild;p1->rChild->parent=y;y->lChild=p1->lChild;p1->lChild->parent=y;y->parent=p1->parent;if(p1->parent->key>p1->key)p1->parent->lChild=y;elsep1->parent->rChild=y;}}}int main(void){int ch;BST T;printf("请写入您要建立的BST树的所有结点值!\n");createBST(T);while (1){printf("\n***************************************\n");printf("*****按下列选项选择您要进行的操作******\n");printf("*****1前序输出.************************\n");printf("*****2.中序输出************************\n");printf("*****3.后序输出************************\n");printf("*****4.查找****************************\n");printf("*****5.求最大值************************\n");printf("*****6.求最小值************************\n");printf("*****7.插入数值************************\n");printf("*****8.获得父节点地址******************\n");printf("*****9.删除数值************************\n");printf("*****10.打印排序二叉树*****************\n");printf("*****11.退出***************************\n");printf("***************************************\n");scanf("%d", &ch);switch (ch){case 1:preorderBST(T); break;case 2:inorderBST(T); break;case 3:postrderBST(T);break;case 4:{int m;printf("您要查找的是多少:");scanf("%d", &m);search(T, m);}break;case 5:Maximum(T); break;case 6:Minmum(T);break;case 7:{printf("您要插入多少:");int key;scanf("%d",&key);Insert(T,key);}break;case 8:get_parent(T);break;case 9:{printf("您要删除多少:");int key;scanf("%d",&key);Delete(T,key);}break;case 10:PrintBST(T,0);break;case 11:return 0; break;default:break;}}return 0;}
删除操作详解
没有行李，没有背包，不带电脑更不要手机，
