C++算法之二叉树线索化

概述C++算法之二叉树线索化

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

前面我们谈到了排序二叉树，还没有熟悉的同学可以看一下这个，二叉树基本 *** 作、二叉树插入、二叉树删除1、删除2、删除3。但是排序二叉树也不是没有缺 点，比如说，如果我们想在排序二叉树中删除一段数据的节点怎么办呢？按照现在的结构，我们只能一个一个数据查找验证，首先看看在不在排序二叉树中，如果在 那么删除；如果没有这个数据，那么继续查找。那么有没有方法，可以保存当前节点的下一个节点是什么呢？这样就不再需要进行无谓的查找了。其实这样的方法是 存在的，那就是在排序二叉树中添加向前向后双向节点。  现在数据结构定义如下：

typedef struct _TREE_NODE  {      int data;      struct _TREE_NODE* prev;      struct _TREE_NODE* next;      struct _TREE_NODE* left;      struct _TREE_NODE* right;  }TREE_NODE;  

    拿节点的添加来说，我们可能需要添加prev、next的处理步骤。

voID set_link_for_insert(TREE_NODE* pParent,TREE_NODE* pNode)  {      if(NulL == pParent || NulL == pNode)          return;        if(pNode = pParent->left){          pNode->prev = pParent->prev;          if(pParent->prev)              pParent->prev->next = pNode;          pNode->next = pParent;          pParent->prev = pNode;      }else{          pNode->next = pParent->next;          if(pParent->next)              pParent->next->prev = pNode;          pNode->prev = pParent;          pParent->next = pNode;      }        return;  }    STATUS add_node_into_tree(TREE_NODE** ppTreeNode,int data)  {      TREE_NODE* phead;      TREE_NODE* pNode;        if(NulL == ppTreeNode)          return FALSE;        if(NulL == *ppTreeNode){          *ppTreeNode = create_new_node(data);          return TRUE;      }        if(NulL != find_data_in_tree(*ppTreeNode,data))          return FALSE;        phead = *ppTreeNode;      while(1){          if(data < phead->data){              if(phead->left){                  phead = phead->left;              }else{                  pNode = create_new_node(data);                  phead->left = pNode;                  break;              }          }else{              if(phead->right){                  phead = phead->right;              }else{                  pNode = create_new_node(data);                  phead->right = pNode;                  break;              }          }      }        set_link_for_insert(phead,pNode);      return TRUE;  }  

    添加节点如此，删除节点的工作也不能马虎。

voID set_link_for_delete(TREE_NODE* pNode)  {      if(pNode->prev){          if(pNode->next){              pNode->prev->next = pNode->next;              pNode->next->prev = pNode->prev;          }else              pNode->prev->next = NulL;      }else{          if(pNode->next)              pNode->next->prev = NulL;      }  }    TREE_NODE* _delete_node_from_tree(TREE_NODE* root,TREE_NODE* pNode)  {      TREE_NODE* pleftMax;      TREE_NODE* pleftMaxParent;      TREE_NODE* pParent = get_parent_of_one(root,pNode);        if(NulL == pNode->left && NulL == pNode->right){          if(pNode == pParent->left)              pParent->left = NulL;          else              pParent->right = NulL;      }else if(NulL != pNode->left && NulL == pNode->right){          if (pNode == pParent->left)              pParent->left = pNode->left;          else              pParent->right = pNode->left;      }else if(NulL == pNode->left && NulL != pNode->right){          if(pNode == pParent->left)              pParent->left = pNode->right;          else              pParent->right = pNode->right;      }else{          pleftMax = get_max_node_of_one(pNode->left);          if(pleftMax == pNode->left){              pNode->left->right = pNode->right;              if(pNode == pParent->left)                  pParent->left = pNode->left;              else                  pParent->right = pNode->left;          }else{              pleftMaxParent = get_parent_of_one(root,pleftMax);              pNode->data = pleftMax->data;              pleftMaxParent->right = NulL;              pNode = pleftMax;          }      }        return pNode;  }    STATUS delete_node_from_tree(TREE_NODE** ppTreeNode,int data)  {      TREE_NODE* pNode;      TREE_NODE* pleftMax;      TREE_NODE* pleftMaxParent;        if(NulL == ppTreeNode || NulL == *ppTreeNode)          return FALSE;        if(NulL == (pNode = find_data_in_tree(*ppTreeNode,data)))          return FALSE;        if(pNode == *ppTreeNode){          if(NulL == pNode->left && NulL == pNode->right)              *ppTreeNode = NulL;          else if(NulL != pNode->left && NulL == pNode->right)              *ppTreeNode = pNode->left;          else if(NulL == pNode->left && NulL != pNode->right)              *ppTreeNode = pNode->right;          else {              pleftMax =  get_max_node_of_one(pNode->left);              if(pNode->left == pleftMax){                  pNode->left->right = pNode->right;                  *ppTreeNode = pNode->left;              }else{                  pleftMaxParent = get_parent_of_one(*ppTreeNode,pleftMax);                  pNode->data = pleftMax->data;                  pleftMaxParent->right = NulL;                  pNode = pleftMax;              }          }            goto final;      }        pNode = _delete_node_from_tree(*ppTreeNode,pNode);    final:      set_link_for_delete(pNode);        free(pNode);      return TRUE;  }  

    其中，寻找最大值节点和寻找父节点的代码如下所示：

TREE_NODE* get_max_node_of_one(TREE_NODE* pNode)  {      if(NulL == pNode)          return NulL;        while(pNode->right)          pNode = pNode->right;        return pNode;  }    TREE_NODE* get_parent_of_one(TREE_NODE* root,TREE_NODE* pNode)  {      if(NulL == root || NulL == pNode)          return NulL;        while(root){          if(pNode == root->left || pNode == root->right)              return root;          else if(pNode->data < root->data)              root = root->left;          else              root = root->right;      }        return NulL;  }  

总结：
    （1）排序二叉树的序列化关键就是在二叉树节点添加前向指针和后继指针
    （2）排序二叉树是空间换时间的典型案例
    （3）排序二叉树是很多结构的基础，写多少遍都不为多，有机会朋友们应该多加练习
    （4）测试用例的编写是代码编写的关键，编写程序的目的就是为了消除BUG，特别是低级BUG

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C++算法之二叉树线索化全部内容，希望文章能够帮你解决C++算法之二叉树线索化所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。