二叉查找树（binary search tree)上的基本操作

现在的位置: 首页 > 综合 > 正文

二叉查找树（binary search tree)上的基本操作

2019年03月20日 ⁄ 综合 ⁄ 共 3925字 ⁄ 字号小中大 ⁄ 评论关闭

二叉查找树：是这样一种树，它满足对对任意一个节点，其左儿子的值<该节点的值<其右儿子的值，因此按中序(inorder)遍历一个二叉查找树时，元素正好按升序排列。下面是关于二叉查找树的插入，删除，中序遍历等基本操作的实现。

1. BST.h

#ifndef BINARY_SEARCH_TREE #define BINARY_SEARCH_TREE typedef int treeEle;//integer binary tree typedef struct BinNode { treeEle data; BinNode *left; BinNode *right; } BinNode; typedef BinNode* BinNodePtr; typedef struct { BinNodePtr root; } BST; //allocate a new BinNode with data-val BinNodePtr newBinNode(treeEle val); //construct an empty BST BST* BST_init(void); //return 1 if BST is empty // 0 otherwise int empty(BST* ); //return 1 if item is in the BST // 0 other wise int search(BST *tree,treeEle item); //insert a new item in the BST and maintain BST property void insert(BST *tree,treeEle item); //traverse BST: inorder LNR void traverse_inorder(BST *tree); void traverse_inorder_aux(BinNodePtr node); //remove node in BST void remove(BST* tree,treeEle item); //locates node containing an item and its parent int search2(BST* tree,treeEle item,BinNodePtr *locPtr,BinNodePtr *parent); #endif //BINARY_SEARCH_TREE

2 .BST.cpp

//allocate a new BinNode with data = val BinNodePtr newBinNode(treeEle val) { BinNodePtr node = (BinNodePtr)malloc(sizeof(BinNode)); assert(node); node->data = val; node->left = NULL; node->right = NULL; return node; } //construct an empty BST BST* BST_init(void) { BST *tree =(BST *)malloc(sizeof(BST)); assert(tree); tree->root = NULL; return tree; } //return 1 if BST is empty,0 otherwise int empty(BST* tree) { assert(tree); return(NULL == tree->root); } //return 1 if value is in the BST, 0 otherwise int search(BST *tree,treeEle item) { assert(tree); BinNodePtr locPtr = tree->root; int found = 0; while(1) { if(found || (NULL == locPtr)) break; if(item < locPtr->data) locPtr = locPtr->left; else if(item > locPtr->data) locPtr = locPtr->right; else found = 1; } return found; } //insert a new item in the BST and maintain BST property void insert(BST *tree,treeEle item) { assert(tree); BinNodePtr locPtr = tree->root; BinNodePtr parent = NULL; int found = 0; while(1) { if(found || (NULL == locPtr)) break; parent = locPtr; if(item < locPtr->data) locPtr = locPtr->left; else if(item > locPtr->data) locPtr = locPtr->right; else found = 1; } if (found) printf("Item already in the tree/n"); else { locPtr = newBinNode((item)); if (NULL == parent) tree->root = locPtr; else if (item < parent->data) parent->left = locPtr; else parent->right = locPtr; } } //traverse BST inorder: LNR void traverse_inorder(BST *tree) { assert(tree); traverse_inorder_aux(tree->root); printf("/n"); } void traverse_inorder_aux(BinNodePtr node) { if(NULL == node) return; traverse_inorder_aux(node->left); printf("%d ",node->data); traverse_inorder_aux(node->right); } //remove node in BST void remove(BST *tree,treeEle item) { int found; BinNodePtr x,parent; found = search2(tree,item,&x,&parent); if(!found) { printf("Item is not in the BST/n"); return; } if ((NULL != x->left) && (NULL != x->right)) { //x has two children //find x's inorder successor and its parent BinNodePtr xsucc = x->right; parent = x; while( NULL != xsucc->left) { parent = xsucc; xsucc = xsucc->left; } //move content of xsucc to x and change x to //point to successor which will be deleted x->data = xsucc->data; x = xsucc; } //if x has two children //proceed with case where node x has 0/1 child BinNodePtr subtree = x->left; if(NULL == subtree) subtree = x->right; if (NULL == parent) tree->root = subtree; else if(x == parent->left) parent->left = subtree; else parent->right = subtree; free(x); } //locates node containing an item and its parent int search2(BST* tree,treeEle item,BinNodePtr *locPtr,BinNodePtr *parent) { assert(tree); *locPtr = tree->root; *parent = NULL; int found = 0; while(1) { if(found || (NULL == locPtr)) break; if(item < (*locPtr)->data ) { *parent = *locPtr; *locPtr = (*locPtr)->left; } else if(item > (*locPtr)->data ) { *parent = *locPtr; *locPtr = (*locPtr)->right; } else found = 1; } return found; }

3.main.cpp

#include <stdio.h> #include <tchar.h> #include <stdlib.h> #include <assert.h> #include "BST.h" int _tmain(int argc, _TCHAR* argv[]) { BST* tree = BST_init(); if (empty(tree)) { printf("Tree is empty/n"); } insert(tree,49); insert(tree,28); insert(tree,13); insert(tree,35); insert(tree,66); insert(tree,62); insert(tree,80); traverse_inorder(tree); if(search(tree,80)) printf("80 is in the tree/n"); if(!search(tree,12)) printf("12 is NOT in the tree/n"); remove(tree,66); traverse_inorder(tree); return 0; }

4.结果

BST