网站设计下载,wordpress 5.0.4,西宁做网站公司哪家好,全景网站app二叉搜索树 III B#xff1a;在二叉搜索树II中加入delete指令#xff0c;创建程序对二叉搜索树T执行如下指令。
插入 k#xff1a;将key k 插入到 T 中。 find k#xff1a;报告T中是否存在key k。 delete k#xff1a;删除key为 k 的节点。 打印#xff1a;使用中序树遍…二叉搜索树 III B在二叉搜索树II中加入delete指令创建程序对二叉搜索树T执行如下指令。
插入 k将key k 插入到 T 中。 find k报告T中是否存在key k。 delete k删除key为 k 的节点。 打印使用中序树遍历和先序树遍历算法打印key值。 删除 k删除二叉搜索树 T 给定的键为 k 的节点 z更新父子链接指针同时根据考虑以下三种情况的算法保持二叉搜索树条件
如果 z 没有孩子则删除 z 的父母 p 的孩子即 z。 如果 z 只有一个孩子将 z 的父节点的子节点更改为 z 的子节点将 z 的子节点的父节点更改为 z 的父节点然后从树中删除 z。 如果 z 有两个孩子则将 z 的下一个节点 y 的key复制到 z 的key并删除 y。这里z的下一个节点是中间前向巡逻中z之后得到的节点。
输入 输入的第一行给出了指令数 m。在下一个 m 行以插入 k、查找 k、删除 k 或打印的形式在一行上给出指令。
输出 对于每个 find k 指令如果 T 包含 k 则输出 yes如果 T 不包含则输出 no。 进一步对于每条打印指令将中序遍历算法和先序遍历算法得到的key的排列输出到一行。在每个key之前打印一个空格。
约束 指令数不超过50万条。 打印指令数量不超过10条。 −2,000,000,000 ≤ key ≤ 2,000,000,000 如果按照上面的伪代码算法树的高度不会超过100。 二叉搜索树中的键没有重复。
数据结构 18 insert 8 insert 2 insert 3 insert 7 insert 22 insert 1 find 1 find 2 find 3 find 4 find 5 find 6 find 7 find 8 print delete 3 delete 7 print 输出样例 yes yes yes no no no yes yes 1 2 3 7 8 22 8 2 1 3 7 22 1 2 8 22 8 2 1 22 #include iostream
#include stack
#include vector
#include string
using namespace std;// 定义树的节点结构
struct Node {int key;Node* right;Node* left;Node* p;
};Node* creat(int a)
{Node* nnew Node();n-keya;n-leftnullptr;n-rightnullptr;n-pnullptr;return n;
}Node* insertt(Node* root,Node* z)
{Node* ynullptr;Node* xroot;while(x!nullptr){yx;if(z-keyx-key)xx-left;elsexx-right;}z-py;if(ynullptr)rootz;else if(z-keyy-key)y-leftz;elsey-rightz;return root;
}Node* findd(Node* root,int k)
{while(root!nullptrk!root-key){if(kroot-key)rootroot-left;elserootroot-right;}return root;
}Node* deletee(Node* root,Node* z)
{if(z-leftnullptrz-rightnullptr){if(z-pnullptr){delete z;return nullptr;}if(z-p-leftz)z-p-leftnullptr;elsez-p-rightnullptr;delete z;}else if(z-leftnullptr||z-rightnullptr){Node* child(z-left!nullptr)?z-left:z-right;if(z-pnullptr){delete z;return child;}if(z-p-leftz)z-p-leftchild;elsez-p-rightchild;child-pz-p;delete z;}else{Node* yz-right;while(y-left!nullptr){yy-left;}z-keyy-key;rootdeletee(root,y);}return root;
}void preorder(Node* a)
{if(anullptr) return;couta-key ;preorder(a-left);preorder(a-right);
}
void inorder(Node* a)
{if(anullptr) return;inorder(a-left);couta-key ;inorder(a-right);
}int main() {int n;Node* treenullptr;cinn;for (int i 0; i n; i) {string c;cinc;if(cinsert){int v;cinv;Node* newNodecreat(v);treeinsertt(tree,newNode);}if(cfind){int v;cinv;Node* afindd(tree,v);if(a)coutyesendl;elsecoutnoendl;}if(cdelete){int v;cinv;Node* afindd(tree,v);if(a)treedeletee(tree,a);}if(cprint){inorder(tree);coutendl;preorder(tree);coutendl;}}return 0;
}
