二叉树二叉树能够说是人们假想的一个模型,因此,允许有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,您将会清楚的看到。下面只讲解链式结构。看各种讲
数据结构的书,您会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种
遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。
节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“
空间换时间”的时代。