二叉排序树的构造及其基本操作

您所在的位置：网站首页 › 二叉树排序树的算法 › 二叉排序树的构造及其基本操作

二叉排序树的构造及其基本操作

2024-07-16 00:17:17| 来源: 网络整理| 查看: 265

二叉排序树的定义对于一棵空的二叉树或者具有如下性质的二叉树： 1.若其左子树不为空，则左子树所有结点的值均小于根结点的值。 2.若其右子树不为空，则右子树所有结点的值均大于根结点的值。 3.其左右子树也是二叉排序树。如：在这里插入图片描述相关图片来源《数据结构——从概念到C++实现（第三版）》

在这里插入图片描述二叉排序树中对值的查找给定一个值p,当前结点为bt,若bt->data==p,查找成功。若pdata,则在pt左子树查找。若p>bt->data,则在pt右子树查找。

BiNode* BiSortTree::SearchBST(BiNode* bt, datatype x) { if (bt == NULL) return NULL; if (bt->data == x)return bt; else if (bt->data > x)return SearchBST(bt->lchild, x); else return SearchBST(bt->rchild, x); }

插入当root为空时直接插入。若root不为空，模拟查找的过程找到其该插入的位置，然后插入。在这里插入图片描述

BiNode* BiSortTree::InsertBST(BiNode* bt, datatype x) { if (bt == NULL) { BiNode* s = new BiNode; s->data = x; s->lchild = s->rchild = NULL; bt = s; return bt; } else if (bt->data > x) { if (bt->lchild == NULL)bt->lchild = InsertBST(bt->lchild, x); else InsertBST(bt->lchild, x); } else { if (bt->rchild == NULL)bt->rchild = InsertBST(bt->rchild, x); else InsertBST(bt->rchild, x); } }

二叉排序树的创建其实就是一个不断插入的过程。

BiSortTree::BiSortTree(int a[], int n) { root = NULL; for (int i = 0;i fa = NULL; BiNode* cur = root; while (cur != NULL && cur->data != key) { fa = cur; if (key > cur->data)cur = cur->rchild; else cur = cur->lchild; } if (cur == NULL)return NULL; return cur; }

并且对于所删除的结点是不是根结点的情况（此时father为NULL）需要特判一下，具体见代码。

void BiSortTree::DeleteBST(datatype x) { BiNode* p = find(x); if ((p->lchild == NULL) && (p->rchild == NULL)) { if (fa == NULL); else if (fa->lchild == p)fa->lchild = NULL; else if (fa->rchild == p)fa->rchild = NULL; delete p;return; } if (p->rchild == NULL) { if (fa == NULL) { root = p->lchild; delete p;return; } else { if (fa->lchild == p)fa->lchild = p->lchild; else if (fa->rchild == p)fa->rchild = p->lchild; delete p;return; } } if (p->lchild == NULL) { if (fa == NULL) { root = p->rchild; delete p;return; } else { if (fa->lchild == p)fa->lchild = p->rchild; else if (fa->rchild == p)fa->rchild = p->rchild; delete p;return; } } BiNode* par = p, * s = p->lchild; while (s->rchild != NULL) { par = s; s = s->rchild; } if (par->lchild == s)par->lchild = NULL; if (par->rchild == s)par->rchild = NULL; p->data = s->data; if (par == p)par->lchild = s->lchild; else par->rchild = s->lchild; delete s; }

以下的操作对于二叉树同样适用二叉排序树的前中后序的递归遍历其实就是输出根结点的位置为前中后。

void BiSortTree::PreOrder(BiNode* bt) { if (bt == NULL)return; else { cout PreOrder(bt->lchild); cout PreOrder(bt->lchild); PreOrder(bt->rchild); cout BiNode* p = stack[top]; cout lchild != NULL)stack[++top] = p->lchild; } }

二叉排序树的层序遍历需要用到一个队列，先将根结点入队。然后将队列中的队首元素（这时就是根结点）出队、输出，再把当前出队结点的左右子节点压入队列（如果左右结点不为空的话），循环直到队列为空。

void BiSortTree::LevelOrder() { BiNode* Q[Max], * q = NULL; int front = -1, rear = -1; if (root == NULL) return; Q[++rear] = root; while (front != rear) { q = Q[++front]; cout rchild != NULL)Q[++rear] = q->rchild; } }

求二叉排序树的高度 DFS，先一直往左走直到尽头，再跳回往右，把所有路径遍历一遍比较得出最大的高度。

int h=0,ht=0; void BiSortTree::get_high(BiNode* bt) { ht++; if (bt == NULL)return; if (bt->lchild == NULL && bt->rchild == NULL) { h = max(h, ht); return; } get_high(bt->lchild); ht--; get_high(bt->rchild); ht--; }

求二叉排序树度为0、度为1、度为2的结点的个数 DFS将二叉树遍历一遍，看其左右结点是否为空逐一记录各度的结点数。

void BiSortTree::get_node(BiNode* bt) { if (bt->lchild != NULL && bt->rchild != NULL) { d2++; get_node(bt->lchild); get_node(bt->rchild); } else if (bt->lchild!=NULL) { d1++; get_node(bt->lchild); } else if (bt->rchild != NULL) { d1++; get_node(bt->rchild); } else { d0++; return; } }

Code

#include #include #include #include #include #include #include #define pii pair #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; typedef char datatype; const int Max = 1e3 + 5; int h=0,ht=0, d1=0, d2=0, d0=0; class BiSortTree { public: BiSortTree(int a[], int n); //~BiSortTree() { Release(root); } BiNode* InsertBST(datatype x) { return InsertBST(root, x); } void DeleteBST(datatype x); BiNode* SearchBST(datatype x) { return SearchBST(root, x); } BiNode* find(const datatype key) { return find(root, key); } void PreOrder() { PreOrder(root); } void InOrder() { InOrder(root); } void PostOrder() { PostOrder(root); } void LevelOrder(); void get_high() { h = 0;get_high(root); } void get_node() { d0 = d1 = d2 = 0;get_node(root); } void get_width(); private: BiNode* InsertBST(BiNode* bt, datatype x); BiNode* SearchBST(BiNode* bt, datatype x); BiNode* find(BiNode* root, const datatype key); void get_high(BiNode* bt); void get_node(BiNode* bt); void Release(BiNode* bt); void PreOrder(BiNode* bt); void InOrder(BiNode* bt); void PostOrder(BiNode* bt); BiNode* root; }; BiNode* BiSortTree::SearchBST(BiNode* bt, datatype x) { if (bt == NULL) return NULL; if (bt->data == x)return bt; else if (bt->data > x)return SearchBST(bt->lchild, x); else return SearchBST(bt->rchild, x); } BiNode* BiSortTree::InsertBST(BiNode* bt, datatype x) { if (bt == NULL) { BiNode* s = new BiNode; s->data = x; s->lchild = s->rchild = NULL; bt = s; return bt; } else if (bt->data > x) { if (bt->lchild == NULL)bt->lchild = InsertBST(bt->lchild, x); else InsertBST(bt->lchild, x); } else { if (bt->rchild == NULL)bt->rchild = InsertBST(bt->rchild, x); else InsertBST(bt->rchild, x); } } BiSortTree::BiSortTree(int a[], int n) { root = NULL; for (int i = 0;i fa = NULL; BiNode* cur = root; while (cur != NULL && cur->data != key) { fa = cur; if (key > cur->data)cur = cur->rchild; else cur = cur->lchild; } if (cur == NULL)return NULL; return cur; } void BiSortTree::DeleteBST(datatype x) { BiNode* p = find(x); if ((p->lchild == NULL) && (p->rchild == NULL)) { if (fa == NULL); else if (fa->lchild == p)fa->lchild = NULL; else if (fa->rchild == p)fa->rchild = NULL; delete p;return; } if (p->rchild == NULL) { if (fa == NULL) { root = p->lchild; delete p;return; } else { if (fa->lchild == p)fa->lchild = p->lchild; else if (fa->rchild == p)fa->rchild = p->lchild; delete p;return; } } if (p->lchild == NULL) { if (fa == NULL) { root = p->rchild; delete p;return; } else { if (fa->lchild == p)fa->lchild = p->rchild; else if (fa->rchild == p)fa->rchild = p->rchild; delete p;return; } } BiNode* par = p, * s = p->lchild; while (s->rchild != NULL) { par = s; s = s->rchild; } if (par->lchild == s)par->lchild = NULL; if (par->rchild == s)par->rchild = NULL; p->data = s->data; if (par == p)par->lchild = s->lchild; else par->rchild = s->lchild; delete s; } void BiSortTree::get_node(BiNode* bt) { if (bt->lchild != NULL && bt->rchild != NULL) { d2++; get_node(bt->lchild); get_node(bt->rchild); } else if (bt->lchild != NULL) { d1++; get_node(bt->lchild); } else if (bt->rchild != NULL) { d1++; get_node(bt->rchild); } else { d0++; return; } } void BiSortTree::get_high(BiNode* bt) { ht++; if (bt == NULL)return; if (bt->lchild == NULL && bt->rchild == NULL) { h = max(h, ht); return; } get_high(bt->lchild); ht--; get_high(bt->rchild); ht--; } void BiSortTree::PreOrder(BiNode* bt) { if (bt == NULL)return; else { cout PreOrder(bt->lchild); cout PreOrder(bt->lchild); PreOrder(bt->rchild); cout q = Q[++front]; cout rchild != NULL)Q[++rear] = q->rchild; } }

码字不易给个赞吧QAQ~

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

二叉排序树的构造及其基本操作

二叉排序树的构造及其基本操作

今日新闻

点击排行

推荐新闻

图片新闻

专题文章