分享
 
 
 

C++数据结构学习:二叉树(1)

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

这些天参与了CSDN论坛的讨论,改变了我以前的一些看法。回头看我以前的东西,我虽对这本书很不满,但我还是按照它的安排在一点点的写;这样就导致了,我过多的在意书中的偏漏,我写的更多是说“这本书怎样”,而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。

正像我在前面所说的,虽然现有的教科书都不是很合理,但假如仅仅是抱怨这点,那无异于泼妇骂街。虽然本人的水平连初级都够不上,但至少先从我做一点尝试,以后这门课的教授方法必将一点点趋于合理。

因此,后面不在按照书上的次序,将本着“实际应用(算法)决定数据结构”的思想来讲解,常见教科书上有的,基本不再重点叙述(除了重点,例如AVL树的平衡旋转),——因此,在看本文的同时,一定要有一本教科书。这只是一个尝试,希望大家多提宝贵意见。

因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等,而为了研究这类问题,必须能够将树储存,而如何储存将取决于所需要的操作。这里有个问题,是否答应存在空树。有些书认为树都是非空的,因为树表示的是一种现实结构,而0不是自然数;我用过的教科书都是说可以有空树,当然是为了和二叉树统一。这个没有什么原则上的差别,反正就是一种习惯。

二叉树

二叉树可以说是人们假想的一个模型,因此,答应有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书,你会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

节点结构

数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或者是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。

template

strUCtBTNode

{

BTNode(Tdata=T(),BTNode*left=NULL,BTNode*right=NULL,BTNode*parent=NULL)

:data(data),left(left),right(right),parent(parent){}

BTNode*left,*right,*parent;

Tdata;

};

基本的二叉树类

template

classBTree

{

public:

BTree(BTNode*root=NULL):root(root){}

~BTree(){MakeEmpty();}

voidMakeEmpty(){destroy(root);root=NULL;}

PRotected:

BTNode*root;

private:

voiddestroy(BTNode*p)

{

if(p)

{

destroy(p-left);

destroy(p-right);

deletep;

}

}

}

二叉树的遍历

基本上有4种遍历方法,先、中、后根,逐层。当初我对这个很迷惑,搞这么多干什么?到了后面才明白,这是不同的应用需要的。例如,判定两个二叉树是否相等,只要子树根节点不同,那么就不等,显然这时要用先序遍历;而删除二叉树,必须先删除左右子树,然后才能删除根节点,这时就要用后序遍历。

实际上,搞这么多遍历方法,根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树,这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性,这些遍历方法能很清楚的表达。

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

1.前序遍历

public:

voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}

private:

voidPreOrder(BTNode*p,void(*visit)(T&data))

{

if(p){visit(p-data);PreOrder(p-left,visit);PreOrder(p-right,visit);}

}

2.中序遍历

public:

voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}

private:

voidInOrder(BTNode*p,void(*visit)(T&data))

{

if(p){InOrder(p-left,visit);visit(p-data);InOrder(p-right,visit);}

}

3.后序遍历

public:

voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}

private:

voidPostOrder(BTNode*p,void(*visit)(T&data))

{

if(p){PostOrder(p-left,visit);PostOrder(p-right,visit);visit(p-data);}

}

4.层次遍历

voidLevelOrder(void(*visit)(T&data)=print)

{

queue*a;BTNode*p=root;//记得#include

while(p)

{

visit(p-data);

if(p-left)a.push(p-left);if(p-right)a.push(p-right);

if(a.empty())break;p=a.front();a.pop();

}

}

附注:缺省的visit函数print如下

private:

staticvoidprint(T&data){cout

5.不用栈的非递归中序遍历

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

当有parent指针时,可以不用栈实现非递归的中序遍历,书上提到了有这种方法,但没给出例程。

public:

BTNode*next()

{

if(!current)returnNULL;

if(current-right){current=current-right;while(current-left)current=current-left;}

else

{

BTNode*y=current-parent;

while(y&¤t==y-right){current=y;y=y-parent;}

current=y;

}

returncurrent;

}

private:

BTNode*current;

上面的函数能使current指针向前移动一个位置,假如要遍历整棵二叉树,需要使current指向中序序列的第一个节点,例如下面的成员函数:

public:

voidfirst(){current=root;while(current-left)current=current-left;}

更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有