数据结构——二叉树(c)

《数据结构——二叉树(c)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构——二叉树（c++）【摘要】现实社会中的树——书籍的目录、任务大纲、家族族谱之类等等。人们要研究就必须能过将树正确的储存，如何存储又关系到实际的操作。树是否为空，在本学期学习的数据结构的教材中允许树为空【1】。因为树表现形式的是一种现实的结构，而0不是自然数。从直观上看树是分支关系定义的层次结构，其中树和二叉树是最常见的【1】。【关键词】数据结构；树；二叉树；遍历；探讨空间；1、二叉树1.1二叉树T是有限的结点的集合（允许为空），或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交

2、的二叉树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的有序树也不同。在有序树中，虽然一个结点的孩子之间是有左右次序的，但若该结点只

3、有一个孩子时，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。图1.2a（不同的两颗二叉树）图1.2b（普通的一棵树）由图可见：(a)和(b)是两棵不同的二叉树。虽然它们与普通的一棵树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。所以二叉树和树尽管有很多相似，但是二叉树不是树的特殊情形。所以，二叉树是一种人们假设的一种现象，所以允许为空是无争议的。二叉树是一种有序的树，左边是孩子、右边是兄弟。其实可以看作不同的两棵树

4、。做这个规定，正式因为人们要赋予给孩子兄弟不同的意义。通过这学期的学习发现了一个现象，就是树并没有插入删除操作。对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。2、特殊形态的二叉树2.1满二叉树【1】：一棵高度为h≥0且有2h+1-1个结点的二叉树称为满二叉树。（如图3.1）图3.1（满二叉树）2.2完全二叉树【1】：若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为完全二叉

5、树。（如图3.2）图3.2（完全二叉树）3、二叉树的遍历以及实现（c++）3.1二叉树基本上有先序遍历、中序遍历、后序遍历，最开始并不明白为什么有这么多，到了后面才明白，这是不同的应用需要的。例如，删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历，而判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；3.1.1前序遍历　public:　　voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,v

6、isit);}　　private:　　voidPreOrder(BTNode*p,void(*visit)(T&data))　　{　　if(p){visit(p->data);PreOrder(p->left,visit);PreOrder(p->right,visit);}　　}3.1.2中序遍历　　public:　　voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}　　private:　　voidInOrder(BTNo

7、de*p,void(*visit)(T&data))　　{　if(p){InOrder(p->left,visit);visit(p->data);InOrder(p->right,visit);}　　}3.1.3后序遍历public:voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}private:voidPostOrder(BTNode*p,void(*visit)(T&data)){if(p){PostOrde

8、r(p->left,visit);PostOrder(p->right,visit);visit(p->data);}}4、二叉树的顺序存储结构4.1在一棵具有n个结点的近似满二叉树中，我们从树根起，自上到下，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列。所以，顺序存储结构是二叉树的一种特点，按照一定的顺序存储在特定的连续单元中。（如图4.1）图4.1（完全二叉树的结点编号）我们将数组下标作为结点编号，就可将二叉树中所有结点的标号存储在一维数组中。（如图4.2）图4.