【数据结构】二叉搜索树（BST树）的定义、构建、插入、删除及查找操作 |
您所在的位置：网站首页 › tree的定义 › 【数据结构】二叉搜索树（BST树）的定义、构建、插入、删除及查找操作 |
【数据结构】二叉搜索树（BST树）的定义、构建、插入、删除及查找操作
|
一、概念 二叉搜索树(BST树)：又叫二叉排序树，二叉查找树。它或者是一棵空树；或者是具有以下性质的二叉树： 1.每个结点都有一个数据域，且所有节点的数据域互不相同； 2.若它的左子树不为空，则左子树上的所有结点的值都小于根节点的值； 3.若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值； 4.左子树和右子树都是二搜索树。 对二叉搜索树进行中序遍历的数据是有序的，因此二叉搜索树也成为二叉排序树。它能利用二分法查找实现快速查找。如下图所示，就是一棵二叉搜索树结构。
看到这个概念很容易联想到堆，二叉搜索树和堆的区别是：二叉搜索树的左子树的值小于根，右子树的值大于根；其中序遍历结果是有序的。而堆的根的值大于或者小于左右孩子，并且是一棵完全二叉树。 二、BST树结构的设计 我们将BST树每个节点的结构设计为4个部分，分别为左孩子节点、双亲节点、数据域和右孩子节点。其中父节点是为回溯设计的，如下图所示。
每个节点结构设计代码如下： struct BstNode { BstNode *leftchild;//右孩子 BstNode *parent;//双亲 BstNode *rightchild;//左孩子 KeyType key;//数据域 };除此之外，还设计了一个头节点，头节点的双亲指针指向根节点，左孩子指向树中最小值的节点，右孩子指向树中最大值的节点。根节点的双亲指针指向头节点。BST树的设计代码如下： typedef struct { BstNode *head;//头节点 int cursize;//当前节点个数 }BSTree;三、BST树的基本操作 1.购买结点和释放结点 //购买一个节点 BstNode* Buynode(BstNode *pa = NULL) { BstNode *s = NULL; s = (BstNode*)malloc(sizeof(BstNode)); if(NULL == s) { exit(1);//具体情况具体处理 } memset(s,0,sizeof(BstNode)); s->parent = pa; return s; } //释放节点 void Freenode(BstNode *p) { free(p); }2.初始化BST树 //初始化BST树 void InitBSTree(BSTree &myt) { myt.head = Buynode(); myt.cursize = 0; }3.循环查找给定值对应的节点，根据BST树的特性，利用二分查找 //循环查找给定值对应的节点 BstNode* FindValue(BSTree &myt,KeyType kx) { BstNode *p = myt.head->parent;//root while(p != NULL && p->key != kx) { p = kx < p->key ? p->leftchild : p->rightchild; } return p; }4.递归查找给定值对应的节点 BstNode* Search(BstNode *ptr,KeyType kx) { if(NULL == ptr || ptr->key == kx) { return ptr; } else if(kx < ptr->key) { return Search(ptr->leftchild,kx); } else { return Search(ptr->rightchild,kx); } } //递归查找给定值对应的节点 BstNode* SearchValue(BSTree &myt,KeyType kx) { return Search(myt.head->parent,kx); }5.对BST树进行递归中序遍历 void InOrder(BstNode* ptr) { if(ptr != NULL) { InOrder(ptr->leftchild); cout key rightchild); } } //递归中序遍历 void InOrderTree(BSTree& myt) { InOrder(myt.head->parent); cout leftchild) { ptr = ptr->leftchild; } return ptr; } //找到某节点的下一个节点 BstNode *Next(BSTree &myt,BstNode *ptr) { if(NULL == ptr || ptr == myt.head) { return NULL; } //如果给定节点的右节点不为空，则它的下一个节点是它的右节点的最左节点 if(ptr->rightchild != NULL) { return First(ptr->rightchild); } else { BstNode *pParent = ptr->parent; while(pParent != myt.head || pParent->leftchild != ptr) { ptr = pParent; pParent = pParent->parent; } if(pParent == myt.head) { return NULL; } return pParent; } } //非递归且不借助于栈进行中序遍历 void NiceInOrder(BSTree &myt) { for(BstNode *ptr = First(myt.head->parent); ptr != NULL ; ptr = Next(myt,ptr)) { cout key key != kx) { pParent = ptr; //依次向下遍历 ptr = (ptr->key > kx) ? ptr->leftchild : ptr->rightchild; } //如果数据已经存在不能重复插入 if(NULL != ptr && ptr->key == kx) { return false; } ptr = Buynode(pParent); ptr->key = kx; //处理空树的情况 if(pParent == myt.head) { myt.head->parent = ptr; myt.head->leftchild = ptr; myt.head->rightchild = ptr; } else { if(ptr->key < pParent->key) { pParent->leftchild = ptr; //维护头节点中的最小值 if(ptr->key < myt.head->leftchild->key) { myt.head->leftchild = ptr; } } else { pParent->rightchild = ptr; //维护头节点中的最大值 if(ptr->key > myt.head->rightchild->key) { myt.head->rightchild = ptr; } } } myt.cursize += 1; return true; }8.删除BST中给定元素对应的节点 //删除BST中给定元素对应的节点 //分5种情况：1.树空；2.没找到；3.待删除的是叶子节点；4.待删除的是单分支；5.待删除的是双分支 bool RemoveBST(BSTree &myt,KeyType kx) { BstNode *ptr = FindValue(myt,kx); //树空或没找到 if(NULL == ptr) { return false; } //删除双分支节点：偷梁换柱，将待删除的下一个节点的值赋值给待删除节点（一定为叶子节点），并删除待删除节点的下一个节点 if(ptr->leftchild != NULL && ptr->rightchild != NULL) { BstNode *s = Next(myt,ptr); ptr->key = s->key; ptr = s; } //删除叶子节点+单分支节点 BstNode *pParent = ptr->parent; BstNode *child = (ptr->leftchild != NULL) ? (ptr->leftchild) : (ptr->rightchild); if(child != NULL) { child->parent = pParent; } if(pParent == myt.head) { myt.head->parent = child; myt.head->leftchild = child; myt.head->rightchild = child; } else { if(ptr == pParent->leftchild) { pParent->leftchild = child; } else { pParent->rightchild = child; } } Freenode(ptr); myt.cursize -= 1; return true; }
|
【本文地址】