ENGLISH 意见建议 网站地图 网站帮助
广泛智力汇聚   高效成果传播   先进机制培育
联盟首页  |  协同开发  |  开放源码库  |  安全告警  |  开源导航  |  文档中心  |  服务支持  |  共创论坛  |  关于联盟


注册会员 网站帮助
    您的位置 »
    今天是: 2010年11月22日    
项目搜索

完全匹配   
开源软件
软件分类表
新发布软件
其它网站镜像
代码片断
协同开发
文档
论坛
寻求协助
热点项目
站点状态
编译工厂

联系我们
关于联盟
代码片段库:
查看代码片段

浏览 | 提交新的代码片段 | 创建代码包

通用二叉平衡排序树的实现类

类型:
Class		 类别:
Other
许可证:
GNU General Public License		 语言:
C++
 
描述:
该类实现了一个通用二叉树,并实现在树的节点在插入和删除的过程中对树的平衡

该代码片段的版本系列:

片段ID 下载版本 提交时间 提交人 删除
48630.22006-02-20 01:29damageboy
Changes since last version:
改正了remove的一个重新平衡二叉树的bug.以及另外两个小错误。
15V0.12002-01-31 14:06huiyugan

点击"下载版本"来下载该代码片段.

最新版本的代码片段: 0.2


file treeline.h

#ifndef TREELINE_H__
#define TREELINE_H__

//
////////////////////////////////////////////////////////////////////////////////
// Bin Tree and order Link <> Tool
// Copy Right , Written By Gan Huaxin, 2001-07-19
// Created in 2001-07-19
// modeified in 2001-07-21
// Thanks for PanXF and YuHang @ FNST
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// modified by Shanghai, damageboy, 2006.02.1x
// thanks Gan Huaxin. 
////////////////////////////////////////////////////////////////////////////////
///
/*
#ifndef DEBUG_TREE
#define DEBUG_TREE
#endif
*/

#define TL_SUCCESS            1
#define TL_FREE_DATA_ERROR    -1
#define TL_COMPARE_ERROR      -2
#define TL_SEARCH_ERROR       -3
#define TL_UNCOMMON_POINTER   -4
#define TL_NULL_POINTER       -5
#define TL_NO_MEM             -6

#define COMPARE_BIG           1
#define COMPARE_EQUAL         0
#define COMPARE_LESS          -1

#ifndef TRUE
#define TRUE                  1
#endif

#ifndef FALSE
#define FALSE                 0
#endif

#ifndef NULL
#define NULL                  0
#endif

struct TTreeLineNode;
class TBinTreeLink;

typedef int (*CompareFunc) (const void* data_a, const void* data_b);
// typedef int (*SearchFunc) (const void* data);
typedef void (*FreeDataFunc) (void* data);

typedef int BOOL;

//
// function return code
//

struct TTreeLineNode {
  void* data;           // user data pointer
  
  int balance;          // Height (left) - Height (right)
  
  // order link
  TTreeLineNode *next;
  TTreeLineNode *prev;
  
  // bin tree
  TTreeLineNode *left;
  TTreeLineNode *right;
  TTreeLineNode *parent;
};

class TBinTreeLink {
  private :
  
    TTreeLineNode *root;    // bin tree root  
    
    TTreeLineNode *head;    // link head
    TTreeLineNode *tail;    // link tail
    
    CompareFunc compare_data;   // compare data function pointer
    // SearchFunc search_data;     // serrch data function pointer
    FreeDataFunc free_data;// node->data 's free function
    
    bool m_b_func_set;
  
  private :
    TTreeLineNode* node_new (void* data);
    int node_add (TTreeLineNode** node, 
                  TTreeLineNode** head,
                  TTreeLineNode** tail,
                  void* data, BOOL *inserted,
                  TTreeLineNode** addnode);
    int node_destroy (TTreeLineNode* &);
    BOOL search (TTreeLineNode* node, void *data, 
                 TTreeLineNode* parent, TTreeLineNode **p);
  
    int release_all ();
    
    // BOOL node_balance (TTreeLineNode*);
    BOOL node_balance (TTreeLineNode *a, bool b_add_node);

    int node_height (TTreeLineNode* node);
    void node_pre_order (TTreeLineNode* node);
    
  public :
    TBinTreeLink (); // add 2001-08-27
    TBinTreeLink (CompareFunc, 
                  // SearchFunc, 
                  FreeDataFunc);
    ~TBinTreeLink ();
  public :
    // add 2001-08-27----------------
    void set_compare_func (CompareFunc);
    void set_freedata_func (FreeDataFunc);
    // end add 2001-08-27----------------
    TTreeLineNode* add (void*);         // add element to tree link
    int remove (TTreeLineNode*);        // remove node from tree link
    // TTreeLineNode* search (void*);      // find special node
    int height ();                      // return the tree height
    // int nnodes ();                      // return the nodes count
    void pre_order ();
    TTreeLineNode* get_root ();
    TTreeLineNode* get_head ();
    TTreeLineNode* get_tail ();
    TTreeLineNode* find (void* data);
    BOOL search (void* data, TTreeLineNode **p);
    void report ();
    void clear ();  // empty this tree!!!
};


#endif


file treeline.cc
//
////////////////////////////////////////////////////////////////////////////////
// Bin Tree and order Link <> Tool
// Copy Right , Written By Gan Huaxin , 2001-07-19
// 
////////////////////////////////////////////////////////////////////////////////
//

#include "treeline.h"
#include "stdio.h"

TBinTreeLink::TBinTreeLink ()
: root(NULL), head(NULL), tail(NULL),
  compare_data (NULL),
  free_data (NULL)
{
}

TBinTreeLink::TBinTreeLink (CompareFunc cmp_func, 
//    SearchFunc srh_func,
    FreeDataFunc free_func)
: root(NULL), head (NULL), tail (NULL),
//  search_data (srh_func), 
  compare_data (cmp_func),
  free_data (free_func)
{
  if (!cmp_func /* || !srh_func*/ )
    m_b_func_set = false;
  else
    m_b_func_set = true;
  
  #ifdef DEBUG_TREE
    printf ("TBinTreeLink::TBinTreeLink, Created
");
  #endif
}

TBinTreeLink::~TBinTreeLink ()
{
  release_all();
  
  #ifdef DEBUG_TREE
    printf ("TBinTreeLink destructor
");
  #endif
}

int TBinTreeLink::release_all ()
{
  TTreeLineNode *p;
  int rc;
  
  while (head) {
    p = head;
    head = head->next;
    rc = node_destroy (p);
    
    if (rc != TL_SUCCESS) {
      printf ("Error on Release_All
");
      return rc;
    }
  }
  head = NULL;
  tail = NULL;
  root = NULL;
  return TL_SUCCESS;
}

int TBinTreeLink::node_destroy (TTreeLineNode*& node)
{
  if (!node) return TL_NULL_POINTER;
  // free node->data use user define free function
  if (free_data) {
    try {
      (*free_data) (node->data);
    }
    catch (...) {
      return TL_FREE_DATA_ERROR;
    }
  }
  // free node memory
  try {
    delete node;
    node = NULL;
  }
  catch (...) {
    return TL_UNCOMMON_POINTER;
  }
  return TL_SUCCESS;
}

TTreeLineNode* TBinTreeLink::node_new (void* data)
{
  TTreeLineNode *node;
  
  if (!data) return NULL;
  try {
    node = new TTreeLineNode;
  }
  catch (...) {
    return NULL; // memory not enough
  }
  
  node->data = data;
  node->prev = NULL;
  node->next = NULL;
  node->left = NULL;
  node->right = NULL;
  node->parent = NULL;
  node->balance = 0;
  
  return node;
}

BOOL TBinTreeLink::search (TTreeLineNode* node, void *data, 
    TTreeLineNode* parent, TTreeLineNode **p)
{
  if (!node || !data) {
    *p = parent;
    return FALSE;
  }
  
  switch ((*compare_data) (data, node->data)) {
    case COMPARE_EQUAL :  // ==
      *p = node;
      return TRUE;
      
    case COMPARE_BIG :    // >
      return search (node->right, data, node, p);
      
    case COMPARE_LESS :   // <
      return search (node->left, data, node, p);
  }
}

TTreeLineNode* TBinTreeLink::find (void* data)
{
  TTreeLineNode *p;
  if (!compare_data) return NULL;
  if (search (root, data, NULL, &p))
    return p;
  else
    return NULL;
}

BOOL TBinTreeLink::search (void* data, TTreeLineNode **p)
{
  if (!compare_data) return FALSE;
//---->> Modified BendCam,Shanghai,Yan Hua Jie, 2/6/2006
  //return (search (root, data, NULL, p));
  if(!(search (root, data, NULL, p)))
  {
	  *p = NULL;
	  return FALSE;
  }
  return TRUE;
//<<---- Modified BendCam,Shanghai,Yan Hua Jie, 2/6/2006
}

int TBinTreeLink::node_add (TTreeLineNode** node, 
    TTreeLineNode** head,
    TTreeLineNode** tail,
    void* data, BOOL *inserted,
    TTreeLineNode **addnode)
{
  TTreeLineNode *p;
  TTreeLineNode *a;
  int rtc;
  
  *addnode = NULL;
  
  if (!data)
    return TL_NULL_POINTER;
  
  if (!search (*node, data, NULL, &p)) { // not find this node!
    TTreeLineNode* s;
    s = node_new (data);
    if (!s) {
      return TL_NO_MEM;
    }
    
    *addnode = s;
    
    if (!(p)) {  // the tree is empty, so, this is the first node
      *head = *tail = *node = s;
      return TL_SUCCESS;
    }
    
    switch ((*compare_data) (data, p->data)) {
      case COMPARE_BIG :
        p->right = s; // s > p, so s is p's right child
        if (p == *tail) {
          *tail = s;
          s->next = NULL;
          p->next = s;
          s->prev = p;
        }
        else {
          s->prev = p;
          s->next = p->next;
          p->next->prev = s;
          p->next = s;
        }

        s->parent = p;
        // if (p == *tail) *tail = s;
        // node_balance (s);
        // p->balance -= 1;
        rtc = TL_SUCCESS;
        goto last;
        
      case COMPARE_EQUAL : // not equal, if equal, search return TRUE
      case COMPARE_LESS : // s < p
        p->left = s;
        s->parent = p;
        
        if (*head == p) {
          *head = s;
          s->prev = NULL;
          p->prev = s;
          s->next = p;
        }
        else {
          s->next = p;
          s->prev = p->prev;
          p->prev->next = s;
          p->prev = s;
        }
        // p->balance += 1;
        // node_balance (s);
        rtc = TL_SUCCESS;
        goto last;
    }
  }
  else {
    // this node exist!
    *addnode = p;
    return TL_SUCCESS;  
  }

last :
  a = p;
  while (a && a->balance == 0 && a->parent) {
    if ((*compare_data) (data, a->data) == COMPARE_BIG) {
      a->balance -= 1;
    }
    else {
      a->balance += 1;
    }
    a = a->parent;
  }
  
  if ((*compare_data) (data, a->data) == COMPARE_BIG) {
      a->balance -= 1;
  }
  else {
      a->balance += 1;
  }
  node_balance (a, true);
  return rtc;  
}

void TBinTreeLink::set_compare_func (CompareFunc func)
{
  compare_data = func;
}

void TBinTreeLink::set_freedata_func (FreeDataFunc func)
{
  free_data = func;
}

TTreeLineNode* TBinTreeLink::add (void* data)
{
  BOOL inserted = FALSE;
  TTreeLineNode *node;
  
  if (!compare_data) return NULL;
  
  node_add (&root, &head, &tail, data, &inserted, &node);
  
  return node;
}

void TBinTreeLink::report (void)
{
  TTreeLineNode *p = head;

  printf ("----------- from link head-------------
");
  while (p) {
    printf("  -- P. data equal %d
", p->data);
    p = p->next;
  }

  printf ("----------- from link head-------------
");
  p = tail;
  while (p) {
    printf("  -- P. data equal %d
", p->data);
    p = p->prev;

  }

  printf ("+++++++++++ from tree ++++++++++++++
");
  pre_order();
  printf ("
------------ Height is : %d -------
", height ());
}

int TBinTreeLink::node_height (TTreeLineNode* node)
{
  int left_height = 0;
  int right_height = 0;
  
  if (node) {
    if (node->left)
      left_height = node_height (node->left);
    if (node->right)
      right_height = node_height (node->right);
    return right_height>left_height ? right_height + 1 : left_height + 1;
  }
  return 0;
}

int TBinTreeLink::height ()
{ 
  return node_height (root);
}

int TBinTreeLink::remove (TTreeLineNode *node)
{ 
  TTreeLineNode *node_parent;

  if (!node) return FALSE;
  
  node_parent = node->parent;

  // modify link
  if (node == head) {
    head = node->next;
    if (head) {
      head->prev = NULL;
    }
    else {
      head = tail = NULL;
    }
  }
  else if (node == tail) {
    tail = node->prev;
    tail->next = NULL;
  }
  else {
    node->prev->next = node->next;
    node->next->prev = node->prev;
  }

  // when node is a leaf
  if (!node->right && !node->left) {
    if (node->parent) {
      if (node->parent->right == node) {
        node->parent->right = NULL;
        node->parent->balance += 1;
      }
      else {
        node->parent->left = NULL;
        node->parent->balance -= 1;
      }
    }
    else {
      root = NULL;
    }
  }
  // only have one child
  else if ((node->left && !node->right) || (!node->left && node->right)){
    if (node->parent) {
      TTreeLineNode *used_node = NULL;
      
      used_node = node->left ? node->left : node->right;
      used_node->parent = node->parent;
      
      if (node->parent->left == node) { // node is left child
        node->parent->left = used_node;
        node->parent->balance -= 1;
      }
      else { // node is right child
        node->parent->right = used_node;
        node->parent->balance += 1;
      }
    }
    else {
      root = (node->left ? node->left : node->right);
      
      root->parent = NULL;
    }
  }
  // have two children
  else {
    TTreeLineNode *prev_node;
    // not thinking balance value
    // prev_node in left child tree
    prev_node = node->prev; // prev_node is the largest node in left child tree
    prev_node->balance = node->balance;

// Shanghai, damageboy, 20060217 {
//    node_parent = prev_node; //
    
//    if (node_parent)
//      node_parent->balance += 1;
	if(prev_node->parent == node)
	{
		node_parent = prev_node;
		node_parent->balance -= 1;
	}
	else
	{
		node_parent = prev_node->parent;
		node_parent->balance += 1;
	}
// } Shanghai, damageboy

    if (prev_node->parent == node) {
      prev_node->right = node->right;
      node->right->parent = prev_node; // 
      if (node->parent == NULL) {// node is root!!
        root = prev_node;
        root->parent = NULL;
      }
      else {    // node is not root
        (node->parent->left == node) ? 
          (node->parent->left = prev_node) : (node->parent->right = prev_node);
        prev_node->parent = node->parent;
      }
    }
    else {
      prev_node->parent->right = prev_node->left;
      if (prev_node->left) {
        prev_node->left->parent = prev_node->parent; //
      }
      prev_node->left = node->left;
      node->left->parent = prev_node; //

      prev_node->right = node->right;
      node->right->parent = prev_node; //
      
      if (node->parent == NULL) {
        root = prev_node;        
        prev_node->parent = NULL;
      }
      else {
        (node->parent->left == node) ? 
          (node->parent->left = prev_node) : (node->parent->right = prev_node);
        prev_node->parent = node->parent;
      }
    }
  }
  
  delete node;
// Shanghai, damageboy, 20060217 {
  //node_balance (node_parent, false);
  if(node_parent)
  {
	  node_balance (node_parent, false);
  }
// } Shanghai, damageboy
  return TL_SUCCESS;
}

void TBinTreeLink::node_pre_order (TTreeLineNode* node)
{
  if (node) {
    if (node->parent) 
      printf ("[P. %d]--", node->parent->data);
    else
      printf ("[ && ]--");
    printf ("%d ", node->data);
  }
  else
    printf ("## ");
  if (node) {
    node_pre_order (node->left);
    node_pre_order (node->right);
  }
}

//
// 要调整的树 a 是已经调整过其平衡值了
//
//
BOOL TBinTreeLink::node_balance (TTreeLineNode *a, bool b_add_node)
{
  TTreeLineNode *b = NULL;
  bool b_height_change;

  if (!b_add_node) {
    if (a->balance == 0) {
      if (a->parent) {
        if (a->parent->left == a) {
          a->parent->balance -= 1;
        }
        else {
          a->parent->balance += 1;
        }
        return node_balance (a->parent, b_add_node);
      }
    }
  }

  if (a->balance<=1 && a->balance>=-1) return FALSE;

  b_height_change = false;
  if (a->balance == 2) {
    b = a->left;   
    if ((b->balance == 1) || // 添加和删除节点都有可能性
        (b->balance == 0) )  // 只有在删除节点时才有可能!
    { // b's left -- LL
      a->left = b->right;
      if (b->right) 
        b->right->parent = a;
      
      b->right = a;
      b->parent = a->parent;
      a->parent = b;

      if (b->balance == 1) {
        a->balance = 0;
        b->balance = 0;
        if (!b_add_node)
          b_height_change = true;
        else
          b_height_change = false;
      }
      else {
        a->balance = 1;
        b->balance = -1;
        b_height_change = false;
      }
      // b became the new tree's root!!
    }
    else if (b->balance == -1){ // b's right --- LR
      TTreeLineNode *c;
      
      c = b->right;
      a->left = c->right;
      if (c->right)
        c->right->parent = a;
      b->right = c->left;
      if (c->left)
        c->left->parent = b;
      c->right = a;
      c->parent = a->parent;
      
      a->parent = c;
      c->left = b;
      b->parent = c;
      
      if (c->balance == 1) {
        a->balance = -1;
        b->balance = 0;
      }
      else if (c->balance == -1) {
        a->balance = 0;
        b->balance = 1;
      } 
      else {
        a->balance = 0;
        b->balance = 0;
      }
      
      // now c become the new tree's root!!
      
      b = c; // so b is root

      c->balance = 0;

      if (!b_add_node)
        b_height_change = true; // 如果是删除节点的话, 树的高度发生变化!
      else
        b_height_change = false;
    }
  }
  else { // 表明 s 在右树中!
    b = a->right;
    if (b->balance == 1) { // b's left -- RL
      TTreeLineNode *c;
      
      c = b->left;
      a->right = c->left;
      if (c->left)
        c->left->parent = a;
      b->left = c->right;
      if (c->right)
        c->right->parent = b;
      
      c->left = a;
      c->parent = a->parent;
      a->parent = c;
      
      c->right = b;
      b->parent = c;
      
      if (c->balance == 1) {
        a->balance = 0;
        b->balance = -1;
      }
      else if (c->balance == -1) {
        a->balance = 1;
        b->balance = 0;
      }
      else {
        a->balance = 0;
        b->balance = 0;
      }
      
      b = c;
      c->balance = 0;

      if (!b_add_node) 
        b_height_change = true;
      else
        b_height_change = false;
    }
    else { // b's right -- RR 
           // b->balance == -1  可能添加或者删除!
           // b->balance == 0 此时一定时删除节点
      a->right = b->left;
      if (b->left)
        b->left->parent = a;
      
      b->left = a;
      b->parent = a->parent;
      a->parent = b;
      
      if (b->balance == -1) { // maybe add or remove
        a->balance = 0;
        b->balance = 0;
        if (!b_add_node)
          b_height_change = true;
        else
          b_height_change = false;
      }
      else { // remove node
        a->balance = -1;
        b->balance = 1;
        b_height_change = false;
      }
    }
  }

  // 由于新树的根已经改变, 但是没有修改根树的对应的咳子指针值
  // if (!balanced) {
  if (b->parent) {
    if (b->parent->left == a) {
      b->parent->left = b;
    }
    else {
      b->parent->right = b;
    }
  }
  else {
    root = b;
    root->parent = NULL;
  }
  
  // 现在 树已经平衡好, 如果该树的深度发生了变化, 应该调整其父!
  if (b_height_change) {
    if (b->parent) {
      if (b->parent->left == b) { // b 是左孩子
        b->parent->balance -= 1;
        node_balance (b->parent, b_add_node); // in fact, the b_add_node equal false
      }
      else { // b 是右孩子
        b->parent->balance += 1;
        node_balance (b->parent, b_add_node);
      }
    }
  }

  return TRUE;
}

void TBinTreeLink::pre_order()
{
  if (root)
    printf (" ++++++++ root is %d ++++++++
", root->data);
  node_pre_order (root);
  printf ("
Pre Order end +++++++++
");
}

TTreeLineNode* TBinTreeLink::get_root()
{
  return root;
}

TTreeLineNode* TBinTreeLink::get_head ()
{
  return head;
}

TTreeLineNode* TBinTreeLink::get_tail ()
{
  return tail;
}

void TBinTreeLink::clear ()
{
  release_all ();
}

提交新版本

如果您修改了一个代码片段并且觉得很应该让别人共享,您可以把这作为这个代码片段的最新版本提交上来.


联盟团体会员
合作伙伴
© 共创软件联盟 版权所有
联盟服务条款 | 联盟隐私权规则 | 联系我们
电话: (8610)68313388-5949 | 传真: (8610)88377936
京ICP备05056057号