数据结构中二叉树的基本操作
作者: 来源: 时间: 2017-03-06 15:15:49
二叉树的基本操作,可能包括:
创建,遍历,转化,复制,删除等。
遍历:前中后三种顺序的遍历,已经是各数据结构与算法教程的最基础内容,在此不重复。
创建:大多数据结构教程当中的二叉树创建程序,都是采用的递归方式,递归方式创建的二叉树与遍历的过程相似,所创建的二叉树,也是采用左右子节点方式,后续进行遍历操作十分方便。
转化:直觉上,最简单的二叉树存储方式其实是如下图的数组:
*此图出自某高校数据结构ppt,但实在难以查证是哪个学校,无法直接感谢,请谅解。
首先,提供个满二叉树大小的数组,然后其中数值按完全二叉树存储。
显然,此种顺序存储方法:第i号(这里编号指对应的完全二叉树的位序)结点的左右孩子一定保存在第2i及2i+1号单元中。
故此,为兼顾存储的直观与遍历等操作的方便,从顺序数组向左右子节点存储方式的转化也就十分重要。
1-转化方法
分为几个步骤:
(1)准备原始数组
(2)分析数组中的有效值,对应二叉树节点非空;
(3)创建二叉树节点;
(4)计算除最后一层子节点外,构造节点间父子关系时的循环次数;
(5)构造二叉树节点间的父子关系;
(6)确实二叉树根节点;
主要代码:
(1)准备原始数组
1. //原始数组
2. int intBiTreeInit[ARR_COUNT];
3.
4.
5. //初始化原始数组至无效值
6. for(int i=0;i<=ARR_COUNT-1;i++)
7. intBiTreeInit[i]=NVALUE;
8.
9. //本if条件确保ARR_COUNT是否是的乘方-1
10. if(0==(ARR_COUNT & (ARR_COUNT+1)))
11. {
12. for(int i=0;i<=ARR_COUNT-1;i++)
13. intBiTreeInit[i]=2*(i+1);
14. }
15. else
16. return RET_ERR;
17.
18. //使最后两数为无效值
19. intBiTreeInit[ARR_COUNT-1]=NVALUE;
20. intBiTreeInit[ARR_COUNT-2]=NVALUE;
(2)分析数组中的有效值
1. //开始获得数组中有效值位置
2. int intRel=0;
3. int intArr=0;
4. for(intArr=0;intArr<=intCount-1;intArr++)
5. {
6. if(elemArr[intArr]!=elemNValue)
7. {
8. intRel++;
9. vecIntEffPos.push_back(intArr);
10. }
11. }
(3)创建二叉树节点
1. //数组中有效值对应创建节点
2. //同时初始化父子节点为NULL
3. for(intArr=0;intArr<=intRel-1;intArr++)
4. {
5. pBiTreeTemp=(PBiTreeNode)malloc(sizeof(BiTreeNode));;
6.
7. if(NULL==pBiTreeTemp) //判断是否有足够的内存空间
8. {
9. cout<<"Memory alloc failure"<
10. return RET_ERR;
11. }
12.
13. //将有效值赋予节点
14. pBiTreeTemp->BiTreeData=elemArr[vecIntEffPos[intArr]];
15.
16. //初始化左右子节点为null,便于后续的遍历
17. pBiTreeTemp->leftChild=NULL;
18. pBiTreeTemp->rightChild=NULL;
19.
20. //先存节点值
21. vecPBiTree.push_back(pBiTreeTemp);
(4)计算除最后一层子节点外,构造节点间父子关系时的循环次数
//生成父子关系时最后一层不必遍历,故理论循环上限可优化
1. int intSubLast=0;
2. intSubLast=intCount-(intCount+1)/2;
(5)构造二叉树节点间的父子关系
1. for(intArr=0;intArr<=intSubLast-1;intArr++)
2. {
3. //左右节点若存储有效值则同时创建父子关系
4. if(elemArr[intArr*2+1]!=elemNValue)
5. vecPBiTree[intArr]->leftChild=vecPBiTree[intArr*2+1];
6.
7. if(elemArr[intArr*2+2]!=elemNValue)
vecPBiTree[intArr]->rightChild=vecPBiTree[intArr*2+2];
(6)确实二叉树根节点
1. pBiTree=vecPBiTree[0];
转化为左右子节点方式存储后,则各种遍历操作按大多数教程的常规方式处理即可,如前序遍历函数:
1. int BiTreePreTrace(PBiTreeNode &pBiTree)
2. {
3. //条件为非空树
4. if(pBiTree)
5. {
6. cout<<"Node value="<<(pBiTree->BiTreeData)<
7.
8. BiTreePreTrace(pBiTree->leftChild); //遍历左子树
9. BiTreePreTrace(pBiTree->rightChild); //遍历右子树
10. }
11. return RET_OK;
12. }
中软卓越java培训地址:北京市海淀区科学院南路2号融科资讯中心C座北楼12层 联系电话:400-666-3775 邮箱账号:etc-marketing@chinasofti.com
©2008-2016 北京中软国际教育科技股份有限公司 京ICP备14058756号-2