二叉排序树的创建，插入和删除（C++完整代码）

您所在的位置：网站首页 › 二叉排序树的关键字 › 二叉排序树的创建，插入和删除（C++完整代码）

二叉排序树的创建，插入和删除（C++完整代码）

2024-01-02 11:33| 来源: 网络整理| 查看: 265

一、二叉排序树（二叉查找树）的概念

（1）若左子树非空，则左子树上所有结点的值均小于根节点的值

（2）若右子树非空，则右子树上所有结点的值均大于根节点的值

（3）左右子树分别也是一棵二叉排序树

tip：可以是一棵空树

二、二叉排序树的判别

（1）因为二叉排序树的中序遍历是一个有序递增序列，可以对已经建立的二叉树进行中序遍历，如果满足则判断是

三、二叉排序树的创建（creat、insert）

树结点的结构体：

struct tree{ int data; struct tree* lchild; struct tree* rchild; };

//递归创建结点 void Creat(int a,tree* &T){ if(T==NULL){ T=new tree; T->data=a; T->lchild=NULL; T->rchild=NULL; } else if(a>T->data){ Creat(a,T->rchild); } else{ Creat(a,T->lchild); } } //传入数组，一次性插入 void Insert(tree* &T,int A[],int len){ for(int i=0;idata){ if(a>K->data){ pre=K; K=K->rchild; }else{ pre=K; K=K->lchild; } } if(K==NULL){ tree* P; //工作指针 P=new tree; P->data=a; if(P->data>pre->data){ pre->rchild=P; P->lchild=NULL; P->rchild=NULL; } else{ pre->lchild=P; P->lchild=NULL; P->rchild=NULL; } coutlchild; }else{ Pre->rchild=P->rchild; } } if(P->datadata){ if(P->lchild!=NULL){ Pre->lchild=P->lchild; }else{ Pre->lchild=P->rchild; } } coutdata=Q->data; if(P!=Pre2){ Pre2->rchild=Q->lchild; }else{ Pre2->lchild=Q->lchild; } delete(Q); coutdata=Q->data; if(P!=Pre2){ Pre2->lchild=Q->rchild; }else{ Pre2->rchild=Q->rchild; } delete(Q); }

六、完整代码（可以运行，两种方法都有） #include using namespace std; struct tree{ int data; struct tree* lchild; struct tree* rchild; }; //建立创建，传入一个完整的数组 void Creat(int a,tree* &T){ if(T==NULL){ T=new tree; T->data=a; T->lchild=NULL; T->rchild=NULL; } else if(a>T->data){ Creat(a,T->rchild); } else{ Creat(a,T->lchild); } } //传入数组，一次性插入 void Insert(tree* &T,int A[],int len){ for(int i=0;ilchild); coutK->data){ pre=K; K=K->rchild; }else{ pre=K; K=K->lchild; } } if(K==NULL){ tree* P; //工作指针 P=new tree; P->data=a; if(P->data>pre->data){ pre->rchild=P; P->lchild=NULL; P->rchild=NULL; } else{ pre->lchild=P; P->lchild=NULL; P->rchild=NULL; } coutlchild; }else{ Pre->rchild=P->rchild; } } if(P->datadata){ if(P->lchild!=NULL){ Pre->lchild=P->lchild; }else{ Pre->lchild=P->rchild; } } coutdata=Q->data; // if(P!=Pre2){ // Pre2->rchild=Q->lchild; // }else{ // Pre2->lchild=Q->lchild; // } // delete(Q); // coutdata=Q->data; if(P!=Pre2){ Pre2->lchild=Q->rchild; }else{ Pre2->rchild=Q->rchild; } delete(Q); cout

【本文地址】

二叉排序树的创建，插入和删除（C++完整代码）

二叉排序树的创建，插入和删除（C++完整代码）

今日新闻

推荐新闻