if (stacks->count == 0)emptyMessage(\
e = stacks->top->data; p = stacks->top;
//printf(\
stacks->top = stacks->top->next; free(p);
stacks->count--; }
bool empty_stack(linkstack *stacks) { if (stacks->count == 0)return 1; else return 0; }
/////////////////////////
BTNode *init_BSTree(Btree tree) { Btree root = tree; return root; }
bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) { //if(tree != NULL){
child = tree; while (child) {
if (value == child->data) { return 1; }
else if (value < child->data) { parents = child;
child = child->lchild; }
else {
parents = child;
child = child->rchild; }
}
return 0; // } }
bool insert_BSTree(Btree &tree, keytype value) { Btree parents, child;
if (!Search_BSTree(tree, value, parents, child)) { Btree S = (BTNode*)malloc(sizeof(BTNode));
26 / 31
S->data = value; S->lchild = NULL; S->rchild = NULL; if (!tree) tree = S;
else if (value < parents->data) { parents->lchild = S; }
else {
parents->rchild = S; } }
return 1;
// return tree; // menu(tree); }
Btree BSTree_fund() {
struct int_linklist *lists = NULL; Btree tree = NULL; int n;
lists = init();
srand((unsigned)time(NULL));
printf(\ scanf_s(\
for (int i = 0; i < n; i++) { add(lists, rand()); }
struct linklist *p; // Btree tree = NULL;
tree = init_BSTree(tree); p = lists->head->next; while (p != NULL) {
insert_BSTree(tree, p->element); p = p->next; }
return tree; }
bool Delete_BSTree(Btree &tree, keytype value) { if (!tree)return 0; else {
if (value == tree->data) { delete_value(tree); return 1; }
else if (value < tree->data) {
27 / 31
return Delete_BSTree(tree->lchild, value); }
else {
return Delete_BSTree(tree->rchild, value); }
}
printf(\ }
void delete_value(Btree &p) { Btree q = NULL, s = NULL;
if (p->lchild && p->rchild) { q = p; s = p->lchild; while (s->rchild) {
q = s; s = s->rchild; }
p->data = s->data;
if (q != p) q->rchild = s->lchild; else q->lchild = s->lchild;
//printf(\ free(s); }
else {
if (!p->rchild) {
q = p; p = p->lchild; free(q); }
else {
q = p; p = p->rchild; free(q); }
//printf(\
}
}
void inoder_rec(Btree T) {
linkstack S ; initstack( &S); Selem e; Btree p = T;
while (p || !(S.count == 0)) {
28 / 31
while(p) {
push_stacks(&S, p); p = p->lchild; }
if(!empty_stack(&S)) {
e = Get_top(S, e);
printf(\ pop_stacks(&S, p); p = p->rchild; }
}
/*if (T) {
inoder_rec(T->lchild); printf(\ inoder_rec(T->rchild); }*/
//menu(tree); }
void PrintTree(Btree bt, int nlayer) // {
/*if(bt==NULL) {
exit(1); }*/ if(bt){
PrintTree(bt->rchild, nlayer + 10); for (int i = 0; i printf(\ } printf(\ PrintTree(bt->lchild, nlayer + 10); } } ////////////////////////////////////// void menu(Btree tree) { int i; while (1) { printf(\ printf(\ 29 / 31 } } printf(\ printf(\ //printf(\printf(\scanf_s(\ if (i == 4)exit(0); switch (i) { case 1: keytype value; printf(\ scanf_s(\ if (insert_BSTree(tree, value)) printf(\ else printf(\ // menu(tree); break; case 2: keytype key; //printf(\ printf(\ scanf_s(\ if (Delete_BSTree(tree, key)) printf(\ else printf(\ //PrintTree(tree ,1); // menu(tree); break; case 3: inoder_rec(tree); printf(\ //PrintTree(tree, 5); break; case 5 :PrintTree(tree, 5); break; case 6:tree = BSTree_fund(); if (tree)printf(\ else printf(\ break; } menu(tree); 30 / 31 31 / 31