Chinaunix首页 | 论坛 | 博客

hnney的ChinaUnix博客hnney.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

hnney

  • 博客访问： 138301
  • 博文数量： 25
  • 博客积分： 588
  • 博客等级： 中士
  • 技术积分： 292
  • 用 户 组： 普通用户
  • 注册时间： 2011-01-10 18:18
文章分类

全部博文（25）

文章存档

2012年（7）

2011年（18）

我的朋友
最近访客
推荐博文
相关博文
二叉查找树

分类： C/C++

2012-02-13 17:16:51

  1. #include <iostream>

  3. using namespace std;

  5. typedef struct Node_ {
  6.     int key;
  7.     struct Node_* left, *right, *parent;
  8. }Node, *BST;

  10. Node *BSTsearch(BST T, int key) {
  11.     if (T == NULL) {
  12.         return NULL;
  13.     }
  14.     else if(key == T->key) {
  15.         return T;
  16.     }
  17.     else {
  18.         if (key < T->key) {
  19.             return BSTsearch(T->left, key);
  20.         }
  21.         else {
  22.             return BSTsearch(T->right, key);
  23.         }
  24.     }
  25. }

  27. Node *BSTsuccessor(BST T) {
  28.     if (T->right == NULL ) {
  29.         return T->parent;
  30.     }
  31.     else {
  32.         Node *p = T->right;
  33.         while (p->left != NULL) {
  34.             p = p->left;
  35.         }
  36.         return p;
  37.     }
  38. }

  40. Node *BSTinsert(BST &T, int key) {
  41.     Node *p = T;
  42.     Node *q = T;
  43.     while (q != NULL) {
  44.         p = q;
  45.         if (key <= p->key) {
  46.             q = p->left;
  47.         }
  48.         else {
  49.             q = p->right;
  50.         }
  51.     }
  52.     Node *tmp = new Node;
  53.     tmp->left = tmp->right = tmp->parent = NULL;
  54.     tmp->key = key;
  55.     if (p == NULL) {
  56.         T = tmp;
  57.     }
  58.     else {
  59.         tmp->parent = p;
  60.         if (key <= p->key) {
  61.             p->left = tmp;
  62.         }
  63.         else {
  64.             p->right = tmp;
  65.         }
  66.     }
  67.     return T;
  68. }

  70. int BSTdelete(BST &T, int key) {
  71.     Node *q = BSTsearch(T, key);
  72.     if (q == NULL) {
  73.         cout<<key<<" is not found"<<endl;
  74.         return false;
  75.     }
  76.     Node *y = NULL;
  77.     Node *x = NULL;
  78.     if (q->left == NULL || q->right == NULL) {
  79.         y = q;
  80.     }
  81.     else {
  82.         y = BSTsuccessor(q);
  83.     }
  84.     if (y->left != NULL) {
  85.         x = y->left;
  86.     }
  87.     else {
  88.         x = y->right;
  89.     }
  90.     if (x != NULL) {
  91.         x->parent = y->parent;
  92.     }
  93.     if (y->parent == NULL) {
  94.         T = x;
  95.     }
  96.     else if (y == y->parent->left) {
  97.         y->parent->left = x;
  98.     }
  99.     else {
  100.         y->parent->right = x;
  101.     }
  102.     if (y != q) {
  103.         q->key = y->key;
  104.     }
  105.     delete y;
  106.     return true;
  107. }

  109. void inorder(BST T) {
  110.     if (T != NULL) {
  111.         inorder(T->left);
  112.         cout<<T->key<<" ";
  113.         inorder(T->right);
  114.     }
  115. }

  117. int main(int argc, char **argv) {

  119.     BST T = NULL;
  120.     int n = 2;
  121.     while (n != 0) {
  122.         BSTinsert(T, n);
  123.         cout<<“中序遍历： ”;
  124.         inorder(T);
  125.         cout<<endl;
  126.         cin>>n;
  127.     }
  128.     n = 2;
  129.     cout<<endl;
  130.     inorder(T);
  131.     cout<<endl;
  132.     cout<<endl;
  133.     while (n != 0) {
  134.         BSTdelete(T, n);
  135.         cout<<"删除节点 "<;
  136.         inorder(T);
  137.         cout<<endl;
  138.         cin>>n;
  139.     }

  141.     return 0;
  142. }
阅读(1340) | 评论(0) | 转发(0) |
0

上一篇：flash 性能相关

下一篇：libevent中的小根堆

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6