网站建设 内容缺乏,网络运营可以自学吗,海门建网站公司,怎么做有个捐款的网站二叉排序树
若它的左子树不空#xff0c;则左子树上所有结点的值均小于它根结点的值。若它的右子树不空#xff0c;则右子树上所有结点的值均大于它根结点的值。它的左、右树又分为⼆叉排序树
二叉排序树也叫二叉查找树、二叉搜索树
二叉排序树的创建、插入、查找和删除
…二叉排序树
若它的左子树不空则左子树上所有结点的值均小于它根结点的值。若它的右子树不空则右子树上所有结点的值均大于它根结点的值。它的左、右树又分为⼆叉排序树
二叉排序树也叫二叉查找树、二叉搜索树
二叉排序树的创建、插入、查找和删除
创建和插入
题目描述 给出一个数据序列建立二叉排序树并实现插入功能。 在建立和插入操作后都输出二叉树的先序遍历结果i
输入 第1行输入n表示序列包含n个数据 第2行输入n个数据都是自然数且互不相同数据之间用空格隔开 第3行输入m表示要插入m个数据 输入m行每行一个要插入的数据都是自然数且和前面的数据不等
输出 第一行输出一开始构建的二叉排序树的先序遍历结果 从第二行起输出m行每行输出插入一个数据到二叉排序树后的先序遍历结果 每行输出的遍历结果中每个数据后面都带一个空格最后一个数据也带。
输入样例1 6 22 33 55 66 11 44 3 77 50 10
输出样例1 22 11 33 55 44 66 22 11 33 55 44 66 77 22 11 33 55 44 50 66 77 22 11 10 33 55 44 50 66 77
输入样例2 6 33 55 22 66 11 44 3 25 88 50
输出样例2 33 22 11 55 44 66 33 22 11 25 55 44 66 33 22 11 25 55 44 66 88 33 22 11 25 55 44 50 66 88
#includebits/stdc.h
using namespace std;
//树节点
struct tree
{int value0;tree* leftNULL;tree* rightNULL;
};
//插入操作
tree* insert(tree* t,int a)
{tree* roott;while(1){if(t-value0) {t-valuea;break;}if(at-value) {if(!t-left) t-leftnew tree;tt-left;}else {if(!t-right) t-rightnew tree;tt-right; }}return root;
}
//先序遍历
void prior(tree* t)
{if(tNULL) return ;coutt-value ;prior(t-left);prior(t-right);
}
int main()
{int n;cinn;tree* rootnew tree;for(int i0;in;i){int x;cinx;rootinsert(root,x);}prior(root);coutendl;int m;cinm;for(int i0;im;i) {int x;cinx;//插入rootinsert(root,x);prior(root);coutendl;}return 0;
}查找
题目描述 给出一个数据序列建立二叉排序树并实现查找功能
输入 第1行输入n表示首个序列包含n个数据 第2行输入n个数据都是自然数且互不相同数据之间用空格隔开 第3行输入m表示要查找m个数据 接着输入m行每行一个要查找的数据都是自然数 以此类推输入下一个示例
输出 第一行输出有序的数据序列对二叉排序树进行中序遍历可以得到 从第二行起输出查找结果如果查找成功输出查找次数如果查找失败输出-1
输入样例1 6 22 33 55 66 11 44 7 11 22 33 44 55 66 77
输出样例1 11 22 33 44 55 66 2 1 2 4 3 4 -1
输入样例2 6 33 22 55 11 66 44 4 88 11 44 66
输出样例2 11 22 33 44 55 66 -1 3 3 3
#includebits/stdc.h
using namespace std;
//树节点
struct tree
{int value0;tree* leftNULL;tree* rightNULL;
};
//插入
tree* insert(tree* t,int a)
{tree* roott;while(1){if(t-value0) {t-valuea;break;}if(at-value) {if(!t-left) t-leftnew tree;tt-left;}else {if(!t-right) t-rightnew tree;tt-right; }}return root;
}
//中序遍历
void middle(tree* t)
{if(tNULL) return ;middle(t-left);coutt-value ;middle(t-right);
}
//查找
int find(tree* t,int a,int time)
{while(1){time;if(t-value0){time-1;break;}if(t-valuea) break;if(at-value){if(!t-left) t-leftnew tree;tt-left;}else{if(!t-right) t-rightnew tree;tt-right;}}return time;
}
int main()
{int n;cinn;tree* rootnew tree;for(int i0;in;i){int x;cinx;rootinsert(root,x);}middle(root);coutendl;int m;cinm;for(int i0;im;i){int x;cinx;coutfind(root,x,0)endl;}return 0;
}删除
题目描述 给出一个数据序列建立二叉排序树并实现删除功能 对二叉排序树进行中序遍历可以得到有序的数据序列
输入 第一行输入t表示有t个数据序列 第二行输入n表示首个序列包含n个数据 第三行输入n个数据都是自然数且互不相同数据之间用空格隔开 第四行输入m表示要删除m个数据 从第五行起输入m行每行一个要删除的数据都是自然数 以此类推输入下一个示例
输出 第一行输出有序的数据序列对二叉排序树进行中序遍历可以得到 从第二行起输出删除第m个数据后的有序序列输出m行 以此类推输出下一个示例的结果
输入样例1 1 6 22 33 55 66 11 44 3 66 22 77
输出样例1 11 22 33 44 55 66 11 22 33 44 55 11 33 44 55 11 33 44 55
提示 当删除数据不在序列中那么删除操作等于不执行所以输出序列不变化
被删除的节点是叶子节点将双亲节点中相应的指针域的值改为空被删除的节点只有左子树或右子树将要删除的节点的双亲节点相应指针域的值指向被删除节点的左子树或者右子树被删除节点既有左子树又有右子树将左子树中的最大值或者右子树中的最小值代替该节点
#includebits/stdc.h
using namespace std;
//树节点
struct tree
{int value0;tree* leftNULL;tree* rightNULL;
};
//插入
tree* insert(tree* t,int a)
{tree* roott;while(1){if(t-value0) {t-valuea;break;}if(at-value) {if(!t-left) t-leftnew tree;tt-left;}else {if(!t-right) t-rightnew tree;tt-right; }}return root;
}
//中序遍历
void middle(tree* t)
{if(tNULL||t-value0) return ;middle(t-left);coutt-value ;middle(t-right);
}
//删除
void del(tree* t,int a)
{//记录父节点tree* pNULL;while(1){if(t-value0) break;if(t-valuea){//叶子结点直接删除if(!t-left!t-right){if(p-leftt) p-leftNULL;else p-rightNULL;break;}//只有左子树或只有右子树if(!t-left||!t-right){//左子树不空if(t-left){if(p-leftt) p-leftt-left;else p-rightt-left;break;}//右子树不空if(t-right){if(p-leftt) p-leftt-right;else p-rightt-right;break;}}//左右子树都不空//本做法是用左子树最大值代替该节点值tree* nowt-left;tree* part;while(now-right) {parnow;nownow-right;}//左子树最大值int valuenow-value;//更新值t-valuevalue;//这里注意if(!now-left!now-right) {//直接删除左子树的根节点if(part) par-leftNULL;//删除的不是左子树的根节点else par-rightNULL;}//有子节点肯定是左子节点else par-rightnow-left;break;}if(at-value){if(!t-left) t-leftnew tree;pt;tt-left;}else{if(!t-right) t-rightnew tree;pt;tt-right;}}
}
int main()
{int t;cint;for(int i0;it;i){int n;cinn;tree* rootnew tree;for(int i0;in;i){int x;cinx;rootinsert(root,x);}middle(root);coutendl;int m;cinm;for(int i0;im;i) {int x;cinx;del(root,x);middle(root);coutendl;}}return 0;
}
