二叉排序树的定义及基本操作（构造、查找、插入、删除）递归及非递归算法 |
您所在的位置：网站首页 › 二叉排序树如何得到有序序列 › 二叉排序树的定义及基本操作（构造、查找、插入、删除）递归及非递归算法 |
二叉排序树的定义及基本操作（构造、查找、插入、删除）递归及非递归算法
|
文章目录
二叉排序树的定义二叉排序树的查找二叉排序树的插入二叉排序树的构造二叉排序树的删除完整代码及实例二叉排序树的查找效率
二叉排序树的定义
二叉排序树（Binary Sort Tree， BST），也称二叉查找树。 二叉排序树或者是一棵空树，或者是一棵具有下列特性的非空二叉树： 1） 若左子树非空，则左子树上所有结点关键字均小于根结点的关键字值； 2） 若右子树非空，则右子树上所有结点关键字均大于根结点的关键字值； 3） 左、右子树本身也分别是一棵二叉排序树。 由定义可知，二叉排序树是一个递归的数据结构，可以方便的使用递归算法对二叉排序树进行各种运算。 根据二叉树的定义，可得左子树结点值 ＜ 根结点值 ＜ 右子树结点值。 所以，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。 二叉排序树的结点定义： typedef struct BSTNode{ int data; struct BSTNode *left; struct BSTNode *right; }BSTNode;二叉树结点的创建： //二叉树结点创建 BSTNode *CreateTreeNode(int x){ BSTNode *p = (BSTNode *)malloc(sizeof(BSTNode)); p->data = x; p->left = NULL; p->right = NULL; return p; } 二叉排序树的查找二叉排序树的查找是从根结点开始的，沿某个分支逐层向下进行比较的过程。 其查找过程描述如下：若二叉排序树非空，则将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找；否则在根结点的右子树中查找。 实现代码： //查找的递归算法 BSTNode *Search(BSTNode *root, int x){ if(root->data == x){ return root; }else if(x data){ return Search(root->left, x); }else{ return Search(root->right, x); } } //查找的非递归算法 BSTNode *Search(BSTNode *root, int x){ BSTNode *p = root; while(p!=NULL && p->data!=x){ if(x data) p = p->left; else p = p->right; } return p; } 二叉排序树的插入二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入的。 由于二叉排序树是递归定义的，因此插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字＜根结点关键字，则插入左子树，若关键字＞根结点关键字，则插入右子树。 实现代码： //插入的递归算法 BSTNode *Insert(BSTNode *root, int x){ if(root == NULL){ root = CreateTreeNode(x); return root; } if(x data){ root->left = Insert(root->left, x); } if(x > root->data){ root->right = Insert(root->right, x); } return root; }
构造一棵二叉排序树就是依次输入数据元素，并将它们插入二叉排序树中适当位置上的过程。 构造二叉排序树的过程：每读入一个元素，就建立一个新结点，若二叉排序树为空，则将新结点作为二叉排序树的根结点；若二叉排序树非空，则将新结点的值与根结点的值比较，若小于根结点的值，则插入左子树，否则插入右子树。 实现代码： void Create(BSTNode *&root, int str[], int n){ root = NULL; for(int i=0; i //在二叉排序树中删除结点p, 并重新连接它的左右子树 BSTNode *q, *s; //1.p为叶子结点 if(p->left==NULL && p->right==NULL){ p = NULL; } //2.1 p左子树为空, 重接右子树 else if(p->left == NULL){ q = p; p = p->right; free(q); } //2.2 p右子树为空, 重接左子树 else if(p->right == NULL){ q = p; p = p->left; free(q); } //3. p左右子树均不为空 else{ q = p; s = p->right; //找到p的右子树的最左端（中序直接后继） while(s->left != NULL){ q = s; s = s->left; } p->data = s->data; if(q != p) //判断是否执行上述while循环 q->left = s->right; //执行上述while循环，重接*q的左子树 else q->right = s->right; //未执行上述while循环，重接*q的右子树，对于这个情况，可以参考代码后给出的示例图 free(s); } return true; } bool DeleteBST(BSTNode *root, int x){ if(root == NULL){ return false; }else{ if(x == root->data) return Delete(root); else if(x data) return DeleteBST(root->left, x); else return DeleteBST(root->right, x); } }对于未执行while循环的情况，如下图示例。 即未执行while循环的的情况为以被删除结点的右子树为根的树没有左子树只有右子树，也就是说，该右子树的最小值即为该根结点的值。 此外，在上面的代码中，在情况3中选择的是用被删除结点z的直接后继替代z，当然也可以用被删除结点z的直接前驱来替代，那么则需要修改为如下的代码即可。 //3. p左右子树均不为空 else{ q = p; s = p->left; //找到p的左子树的最右端（中序直接前驱） while(s->right != NULL){ q = s; s = s->right; } p->data = s->data; if(q != p) //判断是否执行上述while循环 q->right = s->left; //执行上述while循环，重接*q的右子树 else q->left = s->left; //未执行上述while循环，重接*q的左子树 free(s); } 完整代码及实例 #include using namespace std; typedef struct BSTNode{ int data; struct BSTNode *left; struct BSTNode *right; }BSTNode; #define N 100 //查找的递归算法 BSTNode *Search(BSTNode *root, int x){ if(root->data == x){ return root; }else if(x data){ return Search(root->left, x); }else{ return Search(root->right, x); } } //查找的非递归算法 BSTNode *Search1(BSTNode *root, int x){ BSTNode *p = root; while(p!=NULL && p->data!=x){ if(x data) p = p->left; else p = p->right; } return p; } //二叉树结点创建 BSTNode *CreateTreeNode(int x){ BSTNode *p = (BSTNode *)malloc(sizeof(BSTNode)); p->data = x; p->left = NULL; p->right = NULL; return p; } //插入的递归算法 BSTNode *Insert(BSTNode *root, int x){ if(root == NULL){ root = CreateTreeNode(x); return root; } if(x data){ root->left = Insert(root->left, x); } if(x > root->data){ root->right = Insert(root->right, x); } return root; } //插入的非递归算法 BSTNode *Insert1(BSTNode *root, int x){ BSTNode *parent = NULL; //记录当前结点的父结点 BSTNode *p = root; if(root == NULL){ root = CreateTreeNode(x); return root; } while(p != NULL){ parent = p; if(x data){ p = p->left; }else{ p = p->right; } } if(parent->data >x){ parent->left = CreateTreeNode(x); }else if(parent->data root = NULL; for(int i=0; i //在二叉排序树中删除结点p, 并重新连接它的左右子树 BSTNode *q, *s; //1.p为叶子结点 if(p->left==NULL && p->right==NULL){ p = NULL; } //2.1 p左子树为空, 重接右子树 else if(p->left == NULL){ q = p; p = p->right; free(q); } //2.2 p右子树为空, 重接左子树 else if(p->right == NULL){ q = p; p = p->left; free(q); } //3. p左右子树均不为空 else{ q = p; s = p->right; //找到p的右子树的最左端（中序直接后继） while(s->left != NULL){ q = s; s = s->left; } p->data = s->data; if(q != p) //判断是否执行上述while循环 q->left = s->right; //执行上述while循环，重接*q的左子树 else q->right = s->right; //未执行上述while循环，重接*q的右子树 free(s); } return true; } bool DeleteBST(BSTNode *root, int x){ if(root == NULL){ return false; }else{ if(x == root->data) return Delete(root); else if(x data) return DeleteBST(root->left, x); else return DeleteBST(root->right, x); } } void LevelOrder(BSTNode *root){ queue treenode; //队列存储结点 if(root != NULL) treenode.push(root); //根结点入队 while(!treenode.empty()){ BSTNode *p = treenode.front(); treenode.pop(); //根结点出队 cout treenode.push(p->right);//如果有右子树，则将右子树的根结点入队 } } } int main(){ BSTNode *root; int n; cin>>n; int str[n]; for(int i=0; i |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |