博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
二叉搜索树
阅读量:6824 次
发布时间:2019-06-26

本文共 3321 字,大约阅读时间需要 11 分钟。

#include
#include
#include
#include
using namespace std;struct TreeNode{ TreeNode* p; TreeNode* l; TreeNode* r; int key; TreeNode() { p = 0; l = 0; r = 0; key = -1; }};const int RANDMOD = 300;const int MAX = 10;TreeNode* root = new TreeNode;int tIndex = 0;int a[MAX];int getRandom(){ return rand() % RANDMOD;}/** * 中序遍历 */void inOrder(TreeNode* root){ if(root == NULL) return; inOrder(root->l); cout << root->key << " "; inOrder(root->r);}/** * 插入一个结点,等于在左子树 */void insertNode(int key){ if(root->key == -1) { root->key = key; return; } TreeNode* p = root; TreeNode* pc = 0; while (p != NULL) { pc = p; if(key <= p->key) p = p->l; else p = p->r; } TreeNode* newNode = new TreeNode; newNode->key = key; newNode->p = pc; if(key <= pc->key) pc->l = newNode; else pc->r = newNode;}/** * 查找root->key=key的结点 */TreeNode* findNode(TreeNode* root, int key){ if(root->key == key) return root; if(key <= root->key) return findNode(root->l, key); else return findNode(root->r, key); return 0;}/** * 查找以该结点为根的最小key的结点 */TreeNode* minNode(TreeNode* node){ while (node->l != NULL) node = node->l; return node;}/** * 查找以该结点为根的最大key的结点 */TreeNode* maxNode(TreeNode* node){ while (node->r != NULL) node = node->r; return node;}/** * z结点的后继结点 y * y.key > z.key && y2.key>y.key */TreeNode* afterNode(TreeNode* zNode){ if(zNode->r != NULL) return minNode(zNode->r); TreeNode* y = zNode->p; while (y != NULL && zNode == y->r) { zNode = y; y = y->p; } //不存在返回NULL return y;}/** *用v为根的结点替换u为根的子树 */void transplant(TreeNode* u, TreeNode* v){ //树根 if(u->p == NULL) root = v; else if(u == u->p->l) { u->p->l = v; } else u->p->r = v; if(v != NULL) v->p = u->p;}void deleteNode(TreeNode* zNode){ if(zNode->l == NULL) transplant(zNode, zNode->r); else if(zNode->r == NULL) transplant(zNode, zNode->l); else { TreeNode* y = minNode(zNode->r); if(y->p != zNode) { transplant(y, y->r); y->r = zNode->r; y->r->p = y; } transplant(zNode, y); y->l = zNode->l; y->l->p = y; }}int main(){ /** * 二叉搜索树,左子树的所有结点小于等于根结点,右子树的所有结点大于根节点 */ for(int i = 0; i < MAX; i++) { int k = getRandom(); a[i] = k; insertNode(k); } for(int i = 0; i < MAX; i++) cout << a[i] << " "; cout << endl; inOrder(root); cout << endl; cout << "最大值" << maxNode(root)->key << endl; cout << "最小值" << minNode(root)->key << endl; TreeNode* zNode = findNode(root, a[tIndex]); TreeNode* aNode = afterNode(zNode); if(aNode != NULL) cout << a[tIndex] << "的后继结点" << aNode->key << endl; else cout << a[tIndex] << "没有后继结点" << endl; //TODO删除一个结点 cout << "删除结点" << a[tIndex] << endl; deleteNode(zNode); inOrder(root); return 0;}

 

posted on
2017-06-02 22:26 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/6935406.html

你可能感兴趣的文章
[原] Jenkins Android 自动打包配置(转)
查看>>
[Redux] Passing the Store Down with <Provider> from React Redux
查看>>
javascript笔记7-事件
查看>>
大数据处理分析的六大最好工具
查看>>
【转】俞军给淘宝产品经理的分享
查看>>
Thrift使用实例
查看>>
Nand flash uboot 命令详解【转】
查看>>
产品前端重构(TypeScript、MVC框架设计)
查看>>
曲线的奇点
查看>>
英语词汇(2)fall down,fall off和fall over
查看>>
Android开发经验之获取画在画布上的字符串长度、宽度(所占像素宽度)
查看>>
linux下使用tar命令
查看>>
【Linux】了解服务器的情况
查看>>
解决Spring配置文件不显示design和source, namespace 问题
查看>>
Efficiently traversing InnoDB B+Trees with the page directory--slot
查看>>
算法笔记_191:历届试题 大臣的旅费(Java)
查看>>
乐为物联网平台初步体验(1)
查看>>
利用ArcGIS水文分析工具提取河网
查看>>
看58同城9月招聘季 大数据显示蓝领薪酬更高
查看>>
具体分析死锁产生的条件与原因
查看>>