1 / 6 数据结构——二叉树（c++）【摘要】现实社会中的树—— 书籍的目录、任务大纲、家族族谱之类等等。人们要研究就必须能过将树正确的储存，如何存储又关系到实际的操作。树是否为空， 在本学期学习的数据结构的教材中允许树为空【1】。因为树表现形式的是一种现实的结构，而 0 不是自然数。 从直观上看树是分支关系定义的层次结构，其中树和二叉树是最常见的【1】。【关键词】数据结构；树；二叉树；遍历；探讨空间；1、二叉树1.1 二叉树 T 是有限的结点的集合（允许为空） ，或者由一个根结点u 以及分别称为左子树和右子树的两棵互不相交的二叉树u(1) 和 u(2) 组成。若用n,n1 和 n2 分别表示T，u(1)和 u(2) 的结点数，则有n=1+n1+n2 。u(1) 和 u(2) 有时分别称为T 的第一和第二子树。在二叉树中，每个结点至多有两个孩子，并且有左、右之分。因此任一结点的孩子不外4 种情况： 没有孩子； 只有一个左孩子； 只有一个右孩子； 有一个左孩子并且有一个右孩子。（如图 1.1）图 1.1 五种基本形态（其中□表示空）1.2 二叉树与度数不超过2 的树不同，与度数不超过2 的有序树也不同。在有序树中，虽然一个结点的孩子之间是有左右次序的，但若该结点只有一个孩子时，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。图 1.2a （不同的两颗二叉树）图 1.2b（普通的一棵树）由图可见： (a)和 (b)是两棵不同的二叉树。虽然它们与普通的一棵树(作为无序树或有序树)2 / 6 很相似， 但它们却不能等同于这棵普通的树。若将这 3 棵树均看作是有序树，则它们就是相同的了。所以二叉树和树尽管有很多相似，但是二叉树不是树的特殊情形。所以，二叉树是一种人们假设的一种现象，所以允许为空是无争议的。二叉树是一种有序的树，左边是孩子、右边是兄弟。其实可以看作不同的两棵树。做这个规定，正式因为人们要赋予给孩子兄弟不同的意义。通过这学期的学习发现了一个现象，就是树并没有插入删除操作。 对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。 因此，只有在具体的应用中，才会有插入删除操作。2、特殊形态的二叉树2.1 满二叉树【1】：一棵高度为h≥ 0 且有 2h+1-1 个结点的二叉树称为满二叉树。（如图 3.1）图 3.1 （满二叉树）2.2 完全二叉树【1】：若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则...
