开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
BTree2.C
资源名称：btree2.zip　[点击查看]
上传用户：zjanan02
上传日期：2007-01-07
资源大小：1k
文件大小：2k
源码类别：

数值算法/人工智能

开发平台：

C/C++

BTree2.C：源码内容
  1. #include "BTree.h"
  2. #include <stdlib.h>
  6. BTree::BTree()
  7. {
  8.   root=NULL;
  9. }
  11. BTree::~BTree()
  12. {
  13.   DestructTree(root);
  14. }
  16. void BTree::DestructTree(node* r)
  17. {
  18.   if (r!=NULL)
  19.     {
  20.       DestructTree(r->left); DestructTree(r->right);
  21.       delete r;
  22.     }
  23. }
  25. void BTree::Insert(int elem)
  26. {
  27.   InsertInTree(elem, root);
  28. }
  30. void BTree::InsertInTree(int x, node *&p)
  31. {
  33.   if (p==NULL) // leaf, create new node
  34.     {
  35.       p=new node; 
  36.       p->val=x; p->left=NULL; p->right=NULL; 
  37.     }
  38.   else if (p->val>x)
  39.     {
  40.       InsertInTree(x, p->left);
  41.     }
  42.   else if (p->val<x)
  43.     {
  44.       InsertInTree(x, p->right);  
  45.     }
  46.   else
  47.     {
  48.     // element already in tree, do nothing
  49.     }
  50. }
  52. void BTree::Delete(int elem)
  53. {
  54.   DeleteFromTree(elem, root);
  55. }
  61. void BTree::Del(node *&r, node *&q)
  62. {
  63.   if (r->right!=NULL)
  64.     {
  65.       Del(r->right, q);
  66.     }
  67.   else
  68.     {
  69.       q->val=r->val; q=r; r=r->left; 
  70.     }
  71. }
  73. void BTree::DeleteFromTree(int x, node *&p)
  74. {
  75.   node *q;
  76.   
  77.   if (p==NULL) {} // key not found!
  78.   else if (p->val>x)
  79.     {
  80.       DeleteFromTree(x, p->left);
  81.     }
  82.   else if (p->val<x)
  83.     {
  84.       DeleteFromTree(x, p->right);
  86.     }
  87.   else  //p->val==x; remove
  88.     {
  89.       q=p;
  90.       if (q->right==NULL)
  91. {
  92.   p=q->left; 
  93. }
  94.       else if (q->left==NULL)
  95. {
  96.   p=q->right; 
  97. }
  98.       else
  99. {
  100.   Del(q->left, q);
  101. }
  102.       delete q;
  103.     }
  104. }
  105. bool BTree::Find(int z)
  106. {
  107.   return FindInTree(z, root);
  108. }
  110. bool BTree::FindInTree(int z, node *&p)
  111. {
  112.   while (p != NULL)
  113.       if (z < p->val)
  114.   p = p->left;
  115.       else
  116. if (z > p->val)
  117.     p = p->right;
  118.       else
  119. return true;
  120.       
  121.   return false;
  122. }
  124. int BTree::Max(const int a, const int b)
  125. {
  126.   if(a < b)
  127.     return b;
  128.   else
  129.     return a;
  130. }
  132. int BTree::Height()
  133. {
  134.   HeightInTree(root);
  135. }
  137. int BTree::HeightInTree(const node *T)
  138. {
  139.   if (T == NULL)
  140.     return -1;
  141.   else 
  142.     return 1 + Max(HeightInTree(T->left), HeightInTree(T->right));
  143. }
  144.       
  145. int BTree::Size(const node*T)
  146. {
  147.   if (T == NULL)
  148.     return 0;
  149.   else 
  150.     return 1 + Size(T->left) + Size(T->right);
  151. }
  153. int BTree::Leaves(const node *T)
  154. {
  155.   if (T == NULL)
  156.     return 1;
  157.   else
  158.     return Leaves(T->left) + Leaves(T->right);
  159. }
  160.       
  161. double BTree::AvDepth()
  162. {
  163.   return Size(root)/Leaves(root);
  164. }
  167. void BTree::PrintInTree(node *&T)
  168. {
  169.   if (T != NULL)
  170.     {
  171.       cout << T->val<< endl;
  172.       PrintInTree(T->left);
  173.       PrintInTree(T->right);
  174.     }
  175. }
  177. void BTree::Print()
  178. {
  179.   PrintInTree(root);
  180. }