이전 글 'B - 트 리 및 B + 트 리' 에 대한 bug
if(ap->son[0]!=NULL) ap->son[0]->parent=ap;
……
if(ap->son[i-s]!=NULL) ap->son[i-s]->parent=ap;
버그 복 구 를 위해 자신 이 추가 한 코드 입 니 다.
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define M 4 //B- ， 4
#define false 0
#define true 1
typedef struct BTNode
{
//n ，n+1 :（n,P0,K1,P1,K2,P2,…,Kn,Pn）
int keynum; // ，
struct BTNode *parent; //
int key[M+1]; // ，0 ,key[1...M] 1 M
struct BTNode *son[M+1]; //
}BTNode, *BTree; //B- B-
typedef struct
{
BTNode *pt; //
int pos; //1...M,
int tag; //1: ，0:
}Result; //B-
//
void init_BTree(BTree &root)
{
root=NULL;
}
// key
int search(BTree &p,int key)
{
int j=0;
for(j=1; j<=p->keynum; j++)
{
if(p->key[j] > key)
break;
}
return j-1; //
}
Result searchBtree(BTree &root, int key)
{
/*
m B root key， (pt,i,tag).
， tag=1， pt i key；
， tag=0, key , pt i i+1
*/
int found=false;
int i=0;
BTree p=root,father=NULL; // p ，father p
Result result; //SearchBTree
while(p && !found)// ,
{
i=search(p,key); //p->node[i].key≤K<p->node[i+1].key.
if(i>0 && p->key[i]==key)
{
found=true; //
}
else
{
father=p;
p=p->son[i];// father son[i]
}
}
result.pos=i+1; //pos , 1
if(found) //
{
result.pt=p;
result.tag=1;
}
else // ， key i
{
result.pt=father;
result.tag=0;
}
return result;
}//SearchBTree
//
void split(BTree &q, int s, BTree &ap)
{
// q ， ， ap
int i=0;
cout<<"split!"<<" "<<q->key[s]<<endl;
ap=(BTree)malloc(sizeof(BTNode)); // ap
ap->son[0] = q->son[s]; // 0
if(ap->son[0]!=NULL)
ap->son[0]->parent=ap;
for(i=s+1;i<=M;i++) // ap
{
ap->key[i-s]=q->key[i];
ap->son[i-s]=q->son[i];
if(ap->son[i-s]!=NULL)
ap->son[i-s]->parent=ap;
}//for
ap->keynum=M-s;
ap->parent=q->parent;
q->keynum=s-1; //q ， keynum
}//split
void NewRoot(BTree &root, int x, BTree &ap) //
{
// (root,r,ap) *root， root ap
BTree p;
p=(BTree)malloc(sizeof(BTNode));
if(root) //
root->parent=p; //
p->son[0]=root; //
root=p; //root
root->parent=NULL; //
root->keynum=1;
root->key[1]=x; //
root->son[1]=ap; //
if(ap) //
ap->parent=root; //
}//NewRoot
//
void insert(BTree &q, int i, int key, BTree &ap)
{
int j=0;
for(j=q->keynum; j>=i; j--)
{
q->key[j+1]=q->key[j];//
}
q->key[i]=key;
for(j=q->keynum; j>=i; j--)
{
q->son[j+1]=q->son[j];
}
q->son[i]=ap;
q->keynum++;
}//insert
void insertBtree(BTree &root, int key, BTree &q, int i)
{
// B- root q key[i] key[i+1] key
// ， ， root M B-
BTree ap=NULL;
int x=key;
int finished = false;
int s=0;
while(q && !finished)
{
insert(q, i, x, ap); // key ap q->key[i+1] q->son[i+1]
if(q->keynum<M)
finished = true; //
else
{ // *q
s=ceil(M/2);
x=q->key[s];
split(q, s, ap); // q->key[s+1...M],q->son[s...M] *ap
q=q->parent;
if(q)
i=search(q,x)+1; // *q x , 1， search()
}//else
}//while
if(!finished) //root ( q NULL) *q *ap
NewRoot(root, x, ap); // (root,x,ap) *root， root ap
}//insertBtree
void SearchInsertBTree(BTree &root,int key)//
{
// m B *t *q key[i],key[i+1] key
// ， ， *t m B
Result rs;
rs = searchBtree(root,key);
if(!rs.tag) //tag=0 ，
{
cout<<"not exist the key word,insert the node!"<<endl;
insertBtree(root, key, rs.pt, rs.pos); // B- T re.pt key[i] key[i+1] key
}
else
{
cout<<"already exist the key word!"<<endl;
}
}//InserBTree
void DestroyBTree(BTree &root)
{
int i=0;
if(root) //
{
for(i=0; i<=root->keynum; i++)
if(root->son[i])
DestroyBTree(root->son[i]);
free(root);
root=NULL;
cout<<endl<<"destroy success"<<endl;
}//if
}
//
void UserSearch(BTree &root,int key)
{
Result s;
s=searchBtree(root,key);
if(s.tag)
cout<<"find the key word!"<<endl;
else
cout<<"don't find the key word!"<<endl;
}//UserSearch
void print(BTree &p,int i) // TraverseBTree()
{
cout<<p->key[i]<<" ";
}//print
void TraverseBTree(BTree &root) // B_
{
int i=0;
if(root) //
{
if(root->son[0]) // 0
{
TraverseBTree(root->son[0]);
}
for(i=1; i<=root->keynum; i++)
{
print(root,i);
if(root->son[i]) // i
{
TraverseBTree(root->son[i]);
}
}//for
}//if
}//TraverseBTree
int main()
{
BTree Root;
init_BTree(Root); //
//
int key;
/*cout<<" ， 0 :"<<endl;
cin>>key;
while(key)
{
SearchInsertBTree(Root,key);
cin>>key;
}*/
/* SearchInsertBTree(Root,45);*/
SearchInsertBTree(Root,24);
SearchInsertBTree(Root,53);
SearchInsertBTree(Root,90);
SearchInsertBTree(Root,3);
SearchInsertBTree(Root,37);
SearchInsertBTree(Root,50);
SearchInsertBTree(Root,61);
SearchInsertBTree(Root,70);
SearchInsertBTree(Root,1);
SearchInsertBTree(Root,2);
SearchInsertBTree(Root,3);
SearchInsertBTree(Root,4);
SearchInsertBTree(Root,5);
SearchInsertBTree(Root,6);
SearchInsertBTree(Root,7);
SearchInsertBTree(Root,8);
SearchInsertBTree(Root,9);
SearchInsertBTree(Root,10);
SearchInsertBTree(Root,11);
SearchInsertBTree(Root,12);
SearchInsertBTree(Root,13);
SearchInsertBTree(Root,999);
SearchInsertBTree(Root,76);
SearchInsertBTree(Root,15);
SearchInsertBTree(Root,37);
SearchInsertBTree(Root,45);
SearchInsertBTree(Root,31);
SearchInsertBTree(Root,0);
SearchInsertBTree(Root,21);
//
cout<<endl<<"B-Tree order by key word:"<<endl;
TraverseBTree(Root);
//
cout<<endl<<"please input the value of node which you will query.zero can end the input:"<<endl;
cin>>key;
while(key)
{
UserSearch(Root,key);
cin>>key;
}
//
DestroyBTree(Root);// B-
return 0;
}/*End of main()*/이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
