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