我有一个带有插入、高度、查找和打印方法的 Order 5 Btree。我很难理解如何先打印深度 AZ？我有一个打印功能将显示每个节点和其中的元素，但想了解如何按顺序打印。为了方便起见，我更喜欢 AVL 树。
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
const int MAX = 4 ; //maximum # of keys
const int MIN = 2 ; //minimum # of keys
struct btnode
{
int count ;
string value[MAX + 1] ; //number of elements + 1;
btnode *child[MAX + 1] ;
} ;
class btree
{
private :
btnode *root ;
public :
btree( ) ;
void insert ( string val ) ;
int setValue ( string val, btnode *n, string *p, btnode **c ) ;
static int searchNode ( string val, btnode *n, int *pos ) ;
void fillNode ( string val, btnode *c, btnode *n, int k ) ;
void split ( string val, btnode *c, btnode *n, int k, string *y, btnode **newnode ) ;
void show( ) ;
//void search(string key);
int searchPos(string key,string *key_arr,int n); //sub-function for search
static void display ( btnode *root) ;
// void height(string key);
} ;
btree :: btree( )
{
root = NULL ;
}
int btree :: searchNode ( string val, btnode *n, int *pos ) //searches for string in node
{
if ( val < n -> value[1] )
{
*pos = 0 ;
return 0 ;
}
else
{
*pos = n -> count ;
while ( ( val < n -> value[*pos] ) && *pos > 1 )
( *pos )-- ;
if ( val == n -> value[*pos] ) //if value exists in the node returns
{
for(int j =0; j <= n->count; j++)
{
//cout<<"Test in searchmode function"<<endl;
cout<<n->value[j]<<endl;
}
return 1 ;
}
else
return 0 ;
}
}
void btree :: insert ( string val ) //inputting a string
{
string in ;
btnode *c, *n ;
int flag ;
flag = setValue ( val, root, &in, &c ); //in flag has value
if ( flag )
{
n = new btnode ; //create a new btnode
n -> count = 1 ; //initiates the count to 1
n -> value[1] = in ; //value of our node is set to the String passed in
n -> child[0] = root ; //setting pointer of child[0] to root
n -> child[1] = c ;
root = n ;
}
}
int btree :: setValue ( string val, btnode *n, string *p, btnode **ch ) //returns 1 or 0 to set flag
{
int key ;
if ( n == NULL )
{
*p = val ;
*ch = NULL ;
return 1 ; //if root is NULL 1 is returned to flag and node is created
}
else
{
if ( searchNode ( val, n, &key ) ) //checks if the value has already been entered
cout << endl << "Key value already exists." << endl ;
if ( setValue ( val, n -> child[key], p, ch ) )
{
if ( n -> count < MAX ) //if the node is less than MAX order the node is filled
{
fillNode ( *p, *ch, n, key ) ;
return 0 ; //value is returned as 0 to flag
}
else //if the MAX for node is met split
{
split ( *p, *ch, n, key, p, ch ) ;
return 1 ; //after split 1 is returned to flag to set node value
}
}
return 0 ;
}
}
void btree :: fillNode ( string val, btnode *c, btnode *n, int k ) //function to fill the node
{
int i ;
for ( i = n -> count ; i > k ; i-- ) //first node count is = to 1, k=0
{
n -> value[i + 1] = n -> value[i] ;
n -> child[i + 1] = n -> child[i] ;
}
n -> value[k + 1] = val ; //assigns string to location in node
n -> child[k + 1] = c ; //assigns pointer to child
n -> count++ ; //increments node count by one
}
void btree :: split ( string val, btnode *c, btnode *n,
int k, string *y, btnode **newnode )
{
int i, mid ;
cout<<"In split function k is :"<<k;
if ( k <= MIN )
mid = MIN ; //Min is defined as 2, the minimum number in a node
else
mid = MIN + 1 ; //k passing as 3 or 4 will make the midpoint 3
*newnode = new btnode ;
for ( i = mid + 1 ; i <= MAX ; i++ )
{
( *newnode ) -> value[i - mid] = n -> value[i] ; //new node value is placed at i - mid point setting it as first position in split node
( *newnode ) -> child[i - mid] = n -> child[i] ;
}
( *newnode ) -> count = MAX - mid ;
n -> count = mid ;
if ( k <= MIN )
fillNode ( val, c, n, k ) ;
else
fillNode ( val, c, *newnode, k - mid ) ; //fillNode is called and *newnode
*y = n -> value[n -> count] ; //mid point moves up to root node
( *newnode ) -> child[0] = n -> child[n -> count] ;
n -> count-- ;
}
void btree :: show( )
{
display ( root ) ;
}
void btree :: display ( btnode *root)
{
int i=0;
if ( root != NULL )
{
for ( i = 0 ; i < root -> count ; i++ )
{
cout<< root->value[i] ;
display ( root -> child[i] ) ;
}
display ( root-> child[i] ) ;
//cout<< root->value[i] ;
}
}
int main( )
{
btree b ;
int choice;
string key;
string t = "temp"; //to run through height function.
do{
cout<<"\n\n\tSELECT YOUR CHOICE\n\n1. insert\n2. search\n3. display\n4. height\n\n5. EXIT\n\n\n=";
cin>>choice;
switch(choice)
{
case 1:cout<<"\n\nEnter the string to be inserted:";
cin>>key;
b.insert(key);
break;
case 2:cout<<"\n\nEnter search:";
cin>>key;
// b.search(key);
break;
case 3:
cout<<"could not get to print A-Z?!." <<endl;
b.show();
cout<<"\n";
break;
case 4:
//b.height(t);
cout<<"\n";
break;
case 5:break;
default:cout<<"\nINVALID ENTRY";
break;};
}while(choice!=5);
return 0;
}