数据结构学习(C++)——二叉树
happycock(原作)转自 CSDN
【1】
这些天参与了 CSDN 论坛的讨论,改变了我以前的一些看法。回头看我以前的东西,
我虽对这本书很不满,但我还是按照它的安排在一点点的写;这样就导致了,我过多的在
意书中的偏漏,我写的更多是说“这本书怎样”,而偏离了我写这些的初衷——给正在学习
数据结构的人一些帮助。正像我在前面所说的,虽然现有的教科书都不是很合理,但如果
仅仅是抱怨这点,那无异于泼妇骂街。虽然本人的水平连初级都够不上,但至少先从我做
一点尝试,以后这门课的教授方法必将一点点趋于合理。<?xml:namespace prefix = o ns =
"urn:schemas-microsoft-com:office:office" />
因此,后面不在按照书上的次序,将本着“实际应用(算法)决定数据结构”的思想来
讲解,常见教科书上有的,基本不再重点叙述(除了重点,例如 AVL 树的平衡旋转),—
—因此,在看本文的同时,一定要有一本教科书。这只是一个尝试,希望大家多提宝贵意
见。
树
因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等,而为了研
究这类问题,必须能够将树储存,而如何储存将取决于所需要的操作。这里有个问题,是
否允许存在空树。有些书认为树都是非空的,因为树表示的是一种现实结构,而 0 不是自
然数;我用过的教科书都是说可以有空树,当然是为了和二叉树统一。这个没有什么原则
上的差别,反正就是一种习惯。
二叉树
二叉树可以说是人们假想的一个模型,因此,允许有空的二叉树是无争议的。二叉树
是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为
人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,你将会清楚的看到。下
面只讲解链式结构。看各种讲数据结构的书,你会发现一个有趣的现象:在二叉树这里,
基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实
这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的
因此,只有在具体的应用中,才会有插入删除操作。
节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或者是资源紧张,
建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。
template <class T>
struct BTNode
{
BTNode(T data = T(), BTNode<T>* left = NULL, BTNode<T>* right = NULL,
BTNode<T>* parent = NULL)
: data(data), left(left), right(right), parent(parent) {}
BTNode<T> *left, *right, *parent;
评论0