数据结构中二叉树的基本操作

二叉树的基本操作，可能包括：

滨江网站建设公司成都创新互联,滨江网站设计制作，有大型网站制作公司丰富经验。已为滨江1000+提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱，请找那个售后服务好的滨江做网站的公司定做！

创建，遍历，转化，复制，删除等。

遍历：前中后三种顺序的遍历，已经是各数据结构与算法教程的最基础内容，在此不重复。

创建：大多数据结构教程当中的二叉树创建程序，都是采用的递归方式，递归方式创建的二叉树与遍历的过程相似，所创建的二叉树，也是采用左右子节点方式，后续进行遍历操作十分方便。

转化：直觉上，最简单的二叉树存储方式其实是如下图的数组：

*此图出自某高校数据结构ppt，但实在难以查证是哪个学校，无法直接感谢，请谅解。

首先，提供个满二叉树大小的数组，然后其中数值按完全二叉树存储。

显然，此种顺序存储方法：第i号（这里编号指对应的完全二叉树的位序）结点的左右孩子一定保存在第2i及2i+1号单元中。

故此，为兼顾存储的直观与遍历等操作的方便，从顺序数组向左右子节点存储方式的转化也就十分重要。

1-转化方法

分为几个步骤：

（1）准备原始数组

（2）分析数组中的有效值，对应二叉树节点非空；

（3）创建二叉树节点；

（4）计算除最后一层子节点外，构造节点间父子关系时的循环次数；

（5）构造二叉树节点间的父子关系；

（6）确实二叉树根节点；

主要代码：

（1）准备原始数组

 
 
 
 
    
  
  
  
  
  1. //原始数组
    2. 
  
  
  
  
  2.     int intBiTreeInit[ARR_COUNT];
    3. 
  
  
  
  
  3. 
  
  
  
  
  4.    
    5. 
  
  
  
  
  5.     //初始化原始数组至无效值
    6. 
  
  
  
  
  6.     for(int i=0;i<=ARR_COUNT-1;i++)
    7. 
  
  
  
  
  7.         intBiTreeInit[i]=NVALUE;
    8. 
  
  
  
  
  8. 
  
  
  
  
  9.     //本if条件确保ARR_COUNT是否是的乘方-1
    10. 
  
  
  
  
  10.     if(0==(ARR_COUNT & (ARR_COUNT+1)))
    11. 
  
  
  
  
  11.     {
    12. 
  
  
  
  
  12.         for(int i=0;i<=ARR_COUNT-1;i++)
    13. 
  
  
  
  
  13.             intBiTreeInit[i]=2*(i+1);
    14. 
  
  
  
  
  14.     }
    15. 
  
  
  
  
  15.     else
    16. 
  
  
  
  
  16.         return RET_ERR;
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.     //使最后两数为无效值
    19. 
  
  
  
  
  19.     intBiTreeInit[ARR_COUNT-1]=NVALUE;
    20. 
  
  
  
  
  20.     intBiTreeInit[ARR_COUNT-2]=NVALUE;
    21.

（2）分析数组中的有效值

 
 
 
 
    
  
  
  
  
  1. //开始获得数组中有效值位置
    2. 
  
  
  
  
  2.    int intRel=0;
    3. 
  
  
  
  
  3.    int intArr=0;
    4. 
  
  
  
  
  4.    for(intArr=0;intArr<=intCount-1;intArr++)
    5. 
  
  
  
  
  5.    {
    6. 
  
  
  
  
  6.        if(elemArr[intArr]!=elemNValue)
    7. 
  
  
  
  
  7.        {
    8. 
  
  
  
  
  8.            intRel++;
    9. 
  
  
  
  
  9.            vecIntEffPos.push_back(intArr);
    10. 
  
  
  
  
  10.        }
    11. 
  
  
  
  
  11.        }
    12.

（3）创建二叉树节点

  
 
 
 
    
   
  
  
  
  1. //数组中有效值对应创建节点
    2. 
   
  
  
  
  2. //同时初始化父子节点为NULL
    3. 
   
  
  
  
  3. for(intArr=0;intArr<=intRel-1;intArr++)
    4. 
   
  
  
  
  4. {
    5. 
   
  
  
  
  5.     pBiTreeTemp=(PBiTreeNode)malloc(sizeof(BiTreeNode));;
    6. 
   
  
  
  
  6.     
    7. 
   
  
  
  
  7.     if(NULL==pBiTreeTemp)                                //判断是否有足够的内存空间
    8. 
   
  
  
  
  8.     {
    9. 
   
  
  
  
  9.         cout<<"Memory alloc failure"<
   
  
  
  
  10.         return RET_ERR;
    11. 
   
  
  
  
  11.     }
    12. 
   
  
  
  
  12. 
   
  
  
  
  13.     //将有效值赋予节点
    14. 
   
  
  
  
  14.     pBiTreeTemp->BiTreeData=elemArr[vecIntEffPos[intArr]];
    15. 
   
  
  
  
  15.     
    16. 
   
  
  
  
  16.     //初始化左右子节点为null,便于后续的遍历
    17. 
   
  
  
  
  17.     pBiTreeTemp->leftChild=NULL;
    18. 
   
  
  
  
  18.     pBiTreeTemp->rightChild=NULL;
    19. 
   
  
  
  
  19. 
   
  
  
  
  20.     //先存节点值
    21. 
   
  
  
  
  21.     vecPBiTree.push_back(pBiTreeTemp);
    22.

（4）计算除最后一层子节点外，构造节点间父子关系时的循环次数

    //生成父子关系时最后一层不必遍历,故理论循环上限可优化

 
 
 
 
    
  
  
  
  
  1. int intSubLast=0;
    2. 
  
  
  
  
  2.    intSubLast=intCount-(intCount+1)/2;
    3.

（5）构造二叉树节点间的父子关系

 
 
 
 
    
  
  
  
  
  1. for(intArr=0;intArr<=intSubLast-1;intArr++)
    2. 
  
  
  
  
  2. {
    3. 
  
  
  
  
  3.     //左右节点若存储有效值则同时创建父子关系
    4. 
  
  
  
  
  4.     if(elemArr[intArr*2+1]!=elemNValue)
    5. 
  
  
  
  
  5.         vecPBiTree[intArr]->leftChild=vecPBiTree[intArr*2+1];
    6. 
  
  
  
  
  6.         
    7. 
  
  
  
  
  7.     if(elemArr[intArr*2+2]!=elemNValue)
    8. 
  
  
  
  
  8.         vecPBiTree[intArr]->rightChild=vecPBiTree[intArr*2+2];
    9.

（6）确实二叉树根节点

  
 
 
 
    
   
  
  
  
  1. pBiTree=vecPBiTree[0];
    2.

转化为左右子节点方式存储后，则各种遍历操作按大多数教程的常规方式处理即可，如前序遍历函数：

 
 
 
 
    
  
  
  
  
  1. int BiTreePreTrace(PBiTreeNode &pBiTree)
    2. 
  
  
  
  
  2. {
    3. 
  
  
  
  
  3.     //条件为非空树
    4. 
  
  
  
  
  4.     if(pBiTree)
    5. 
  
  
  
  
  5.     {
    6. 
  
  
  
  
  6.         cout<<"Node value="<<(pBiTree->BiTreeData)<
  
  
  
  
  7.         
    8. 
  
  
  
  
  8.         BiTreePreTrace(pBiTree->leftChild);    //遍历左子树
    9. 
  
  
  
  
  9.         BiTreePreTrace(pBiTree->rightChild);    //遍历右子树
    10. 
  
  
  
  
  10.     }
    11. 
  
  
  
  
  11.     return RET_OK;
    12. 
  
  
  
  
  12. }
    13.

完整程序，请见附件文件。

 http://files.cnblogs.com/vbspine/cnsDSExec.rar

*上述程序在Windows7x64，VS2008环境编译运行通过

网站题目：数据结构中二叉树的基本操作
分享地址：http://www.shufengxianlan.com/qtweb/news27/504427.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站收录知识

各行业网站

重庆网站建设网络公司　　 　手机APP开发　　 　泸州网站建设　　 　旅游网站建设方案　　 　班戈纳美网站　　 　广安做网站　　 　犀浦封阳台　　 　成都网站推广　　 　成都网站推广　　 　绵阳服务器托管　　 　云主机　　 　专业网站设计　　 　云服务器香港　　 　都江堰网站建设　　 　成都定制网站建设　　 　达州做网站　　 　高端网站策划　　 　网站建设公司　　 　资阳做网站　　 　机柜租用