数据构造学习（C++）之二叉树[VC/C++编程]

树

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

二叉树

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

节点构造

数据域、左指针、右指针必定是必须的.除非很罕用到节点的双亲,大概是资源慌张,倡议附加一个双亲指针,这将会给很多算法带来便利,特别是在这个“空间换时间”的时代.

基本的二叉树类