天天爱消除宠物满级表:一步一步写算法（之排序二叉树的保存和加载）

来源：百度文库 编辑：中财网 时间：2024/04/29 02:47:45
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】


排序二叉树是我们开发中经常使用到的一种数据结构，它具有较好的插入、删除、查找特性。但是由于二叉树的指针较多，所以相比较其他的数据结构而言，二叉树来得比较麻烦些。但是也不是没有办法，下面介绍一下我个人常用的方法。
我们知道，如果一个二叉树是一个满树的话，那么二叉树的节点应该是按照1、2、3、4依次排开的。但是现实情况是这样的，由于排序二叉树自身的特性，某个分支节点常常可能左半边有分支，右半边没有分支；或者是右半边有分支，左半边没有分支。那么在数据中节点的顺序很可能是不连贯的了。
但是，对于某一个节点来说，它的左分支节点、右分支节点和父节点之间还是存在着某种联系的。比如说，如果父节点的顺序是n，那么它的左节点只能是n*2，右边节点只能是2*n+1。那么，我们能不能利用父节点和子节点之间的关系来进行数据的保存呢？答案当然是肯定的。

首先，我们需要对数据结构重新定义一下，其中number记录序列号：

view plaincopy to clipboardprint?

  1. typedef struct _TREE_NODE
  2. {
  3. int data;
  4. int number;
  5. struct _TREE_NODE* left_child;
  6. struct _TREE_NODE* right_child;
  7. }TREE_NODE;
那么原来添加数据的函数也要做出修改？
view plaincopy to clipboardprint?
  1. STATUS _insert_node_into_tree(TREE_NODE* pTreeNode, int data)
  2. {
  3. TREE_NODE* pNode;
  5. while(1){
  6. if(data < pTreeNode->data){
  7. if(NULL == pTreeNode->left_child){
  8. pNode = create_tree_node(data);
  9. assert(NULL != pNode);
  10. pNode->number = pTreeNode->number << 1;
  11. pTreeNode->left_child = pNode;
  12. break;
  13. }else
  14. pTreeNode = pTreeNode->left_child;
  15. }else{
  16. if(NULL == pTreeNode->right_child){
  17. pNode = create_tree_node(data);
  18. assert(NULL != pNode);
  19. pNode->number = pTreeNode->number << 1 + 1;
  20. pTreeNode->right_child = pNode;
  21. break;
  22. }else
  23. pTreeNode = pTreeNode->right_child;
  24. }
  25. }
  27. return TRUE;
  28. }
  30. STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
  31. {
  32. if(NULL == ppTreeNode)
  33. return FALSE;
  35. if(NULL == *ppTreeNode){
  36. *ppTreeNode = (TREE_NODE*)create_tree_node(data);
  37. assert(NULL != *ppTreeNode);
  38. (*ppTreeNode)->number = 1;
  39. return TRUE;
  40. }
  42. return _insert_node_into_tree(*ppTreeNode, data);
  43. }
那么，此时保存的时候放在硬盘里面的数据应该有哪些呢？我们在遍历每一个节点的时候，只需要把对应的数据和序列号依次放到硬盘即可。

view plaincopy to clipboardprint?

  1. typedef struct _DATA
  2. {
  3. int data;
  4. int number;
  5. }DATA;

保存的数据总要再次启用吧？怎么加载呢？很简单，四个步骤：
1）根据记录的节点总数分配n*sizeof（TREE_NODE）空间；
2）依次从硬盘中取出DATA数据，把它们复制给TREE_NODE，暂时left_side和right_side指针为空；
3）对于对于每一个节点n，寻找它的父节点n>>1，填充left_side或者是right_side，并且根据（n%2）是否为1判断当前节点是左节点还是右节点；
4）获取n=1的节点，那么这个节点就是我们需要寻找的根节点，至此数据就加载完毕。



平衡二叉树的各种算法实现 二叉树的层次遍历算法 写一个算法来计算给定二叉树的叶结点数 关于排序和查找的算法 排序二叉树和二叉查找树有什么区别么? 用PASCAL解决这个关于排序二叉树的问题 C#进行二叉树排序的代码是什么？ 求教由二叉树的前序遍历序列建立二叉树的非递归算法 二叉树采用链接方法存储,编写一个计算一个二叉树的高度的算法 求二叉树遍历算法C语言实现的 急急急！！！！二叉树遍历的算法怎么算呀 求java实现二叉树启遍历的算法 以二叉树表作存储结构，试编写求二叉树高度的算法？ 完全二叉树和满二叉树的区别 完全二叉树和满二叉树的区别 二叉树遍历的程序怎么写？ 谁会写二叉树的遍历操作？？？？ 谈谈排序算法的概念和实际应用中的要求 用C语言写一个排序算法。 整数排序算法的问题？ 堆排序的具体算法 快速排序的循环算法 求几种排序法的算法 全排序的算法(PASCAL)