-
concept
Binary Sort Tree (Binary Sort Tree), also called Binary search Tree. It could be an empty tree. Or a binary tree with the following properties; If its left subtree is not empty, the values of all nodes in the left subtree are less than the values of its root structure; If its right subtree is not empty, then the value of all nodes in the right subtree is greater than the value of its root; Its left and right subtrees are also binary sorting trees;
-
Binary sort tree lookup operations
- Implementation idea from the root node start comparison, if greater than the root node (according to the concept of binary sort tree) directly from the root node of the right subtree to continue to find, if less than from the current node of the left subtree to continue to find.
- The implementation code
//1. Binary sort tree -- find /* recurse to find whether there is a key in binary sort tree T; The pointer f to the parent of T is NULL; If the search is successful, the pointer p points to the node of the data element and returns TRUE. Return FALSE if p points to the last node visited on the lookup path; */ Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){// Return an error if both root nodes are nullif(! T){// return the parent node *p =f;return FALSE; } if(T->data == key){// return root node (*p) = T;return TRUE; }else if(key > T->data){(key > T->data){(key > T->data)return SearchBST(T->rchild, key, T, p); }else{// If the element is less than the root node (according to the properties of binary sort tree), the search will continue in the left tree and pass in the parent nodereturn SearchBST(T->lchild, key, T, p); } return FALSE; } Copy the code -
Insertion of binary sort trees
- Implementation approach First find the value of the element to be inserted is already exists in the binary sort tree if there is no insert, if not in accordance with the above method returns the search path to access the last node, start is inserted into the element value and the last node, the size of the larger insert and inserted into the left right node
- The implementation code
//2. Binary sort tree - insert /* If there is no data element in binary sort tree T with key equal to key, insert key and return TRUE, Otherwise return FALSE */ Status InsertBST(BiTree *T, int key) {BiTree p;if(SearchBST(*T, key, NULL, &p)){// Insert failed if the element already existsreturn FALSE; }else{ BiTree s = (BiNode *)malloc(sizeof(BiNode)); if(! s)return FALSE; s->data = key; s->lchild = s->rchild = NULL; if(p == NULL){// the tree is empty *T = s; }else{// Start judging the current value and the size of the last node in the tree, large to the right, small to the leftif(p->data > key){ p->lchild = s; }else{ p->rchild = s; }}returnTRUE; }}Copy the code -
Binary sort tree delete operation
-
The realization of the train of thought is mainly divided into three cases
-
The deleted node is the leaf node; That’s a good case to deal with as long as you find the corresponding node and delete it
-
The node to be deleted is not a leaf node but contains only left or right nodes. In this case, you just assign the right node or the left node of the node that you want to delete and the left node or the right node to the node that you want to delete and you delete 58
-
The deleted node contains both left node and right node. This situation is to find the left node to node is to be deleted, and then all the way down to find nodes right left, and then continue to nodes right right, find down until the right node to null node, is to find the node to replace to delete nodes, or find the right node to node is to be deleted, and then to find the right node node on the left, You go down to the left node until you find the null left node and then you replace the node that you want to delete with that node, and in order traversal these are the nodes before and after the node that you want to delete, If you replace the node to be deleted with these two nodes, the change in logarithm will be minimal, as shown in figure 47. If you delete this node, you can find nodes 37 and 48 by following the steps above. You can replace the node to be deleted with either of these two nodes
-
-
The implementation code
//3. Delete node p from the binary sort tree and rejoin its left or right subtree; //f Status Delete(BiTree *p){if((*p)->lchild && (*p)->rchild){if ((*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){ // Find the last node in the left subtree, BiTree Temp; // Find the last node in the left subtree. BiTree s = NULL; temp = (*p)->lchild;while(temp->rchild) { s = temp; temp = temp->rchild; } // Start assignment (*p)->data = temp->data;if(s){ s->rchild = temp->lchild; } free(temp); }else if((*p)->lchild){ BiTree temp; temp = *p; *p = (*p)->lchild; free(temp); }else if((*p)->rchild){ BiTree temp; temp = *p; *p = (*p)->rchild; free(temp); }else{ *p = NULL; free(*p); } returnTRUE; } //4. Find the node and delete it in binary sort; /* if there is a data element whose key is equal to key in the binary sort tree T, delete the data element node, */ /* and return TRUE; Otherwise return FALSE. */ Status DeleteBST(BiTree *T,int key){// There is no data element whose key is equal to keyif(! *T)return FALSE; else{// Find the data element whose key is equal to keyif (key==(*T)->data) return Delete(T); else if(key<(*T)->data) (key<(*T)->data)return DeleteBST(&(*T)->lchild,key); else// If key is greater than the current node, narrow the search scope to its right subtree;returnDeleteBST(&(*T)->rchild,key); }}Copy the code -
-
The complete code
// // main.c // Binary sorting tree // // Created by XZKJ on 2020/6/3. // Copyright © 2020 tudou. All Rights reserved#include <stdio.h>
#include "stdlib.h"
#define FALSE 0
#define TRUE 1typedef int Status; typedef struct BiNode{ int data; // Struct BiNode * lChild,* rChild; // Left child and right child}BiNode,*BiTree; //1. Binary sort tree -- find /* recurse to find whether there is a key in binary sort tree T; The pointer f to the parent of T is NULL; If the search is successful, the pointer p points to the node of the data element and returns TRUE. Return FALSE if p points to the last node visited on the lookup path; */ Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){// Return an error if both root nodes are nullif(! T){// return the parent node *p =f;return FALSE;
}
if(T->data == key){// return root node (*p) = T;return TRUE;
}else if(key > T->data){(key > T->data){(key > T->data)return SearchBST(T->rchild, key, T, p);
}else{// If the element is less than the root node (according to the properties of binary sort tree), the search will continue in the left tree and pass in the parent nodereturn SearchBST(T->lchild, key, T, p);
}
returnFALSE; } //2. Binary sort tree - insert /* If there is no data element in binary sort tree T, */ /* Insert key and return TRUE, Otherwise return FALSE */ Status InsertBST(BiTree *T, int key) {BiTree p;if(SearchBST(*T, key, NULL, &p)){// Insert failed if the element already existsreturn FALSE;
}else{
BiTree s = (BiNode *)malloc(sizeof(BiNode));
if(! s)return FALSE;
s->data = key;
s->lchild = s->rchild = NULL;
if(p == NULL){// the tree is empty *T = s; }else{// Start judging the current value and the size of the last node in the tree, large to the right, small to the leftif(p->data > key){
p->lchild = s;
}else{ p->rchild = s; }}returnTRUE; }} //3. Delete node p from binary sort tree and rejoin its left or right subtree; //f Status Delete(BiTree *p){if((*p)->lchild && (*p)->rchild){if ((*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){if (*p)->lchild && (*p)->rchild){ // Find the last node in the left subtree, BiTree Temp; // Find the last node in the left subtree. BiTree s = NULL; temp = (*p)->lchild;while(temp->rchild) { s = temp; temp = temp->rchild; } // Start assignment (*p)->data = temp->data;if(s){
s->rchild = temp->lchild;
}
free(temp);
}else if((*p)->lchild){
BiTree temp;
temp = *p;
*p = (*p)->lchild;
free(temp);
}else if((*p)->rchild){
BiTree temp;
temp = *p;
*p = (*p)->rchild;
free(temp);
}else{
*p = NULL;
free(*p);
}
returnTRUE; } //4. Find the node and delete it in binary sort; /* if there is a data element whose key is equal to key in the binary sort tree T, delete the data element node, */ /* and return TRUE; Otherwise return FALSE. */ Status DeleteBST(BiTree *T,int key){// There is no data element whose key is equal to keyif(! *T)return FALSE;
else{// Find the data element whose key is equal to keyif (key==(*T)->data)
return Delete(T);
else if(key<(*T)->data) (key<(*T)->data)return DeleteBST(&(*T)->lchild,key);
else// If key is greater than the current node, narrow the search scope to its right subtree;return DeleteBST(&(*T)->rchild,key);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World! \n"); int i; 62,88,58,47,35,73,51,99,37,93 int a [10] = {}; BiTree T=NULL;for(i=0; i<10; i++) { InsertBST(&T, a[i]); } BiTree p; int statusValue = SearchBST(T, 99, NULL, &p);printf(%d (1->YES/0->NO)\n",p->data,statusValue);
statusValue = DeleteBST(&T,93);
printf(%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,47);
printf("Binary sort tree delete 47 successfully :%d (1->YES/0->NO)\n",statusValue);
statusValue = DeleteBST(&T,12);
printf(%d (1->YES/0->NO)\n",statusValue);
statusValue = SearchBST(T, 93, NULL, &p);
printf(%d (1->YES/0->NO)\n",93,statusValue);
//
statusValue = SearchBST(T, 47, NULL, &p);
printf(%d (1->YES/0->NO)\n",47,statusValue);
statusValue = SearchBST(T, 99, NULL, &p);
printf(%d (1->YES/0->NO)\n",99,statusValue);
printf("\n");
return 0;
}
Copy the code