C语言数据结构树的实现

《C语言数据结构树的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、树树课程内容树的基本概念树的存储结构树的遍历二叉树的实现树的基本概念树是一类重要的非线性数据结构，是以分支关系定义的层次结构树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：–有且仅有一个特定的结点，称为树的根(root)–当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：–树中至少有一个结点----根–树中各子树是互不相交的集合树只有根结点的树A有子树的树根ABCDEFGHIJKLM子树树基本术语结点(node)-

2、---表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)----结点拥有的子树数叶子(leaf)----度为0的结点孩子(child)----结点子树的根称为该结点的孩子双亲(parents)----孩子结点的上层结点叫该结点的~兄弟(sibling)----同一双亲的孩子树的度----一棵树中最大的结点度数结点的层次(level)----从根结点算起，根为第一层，它的孩子为第二层¡¡深度(depth)----树中结点的最大层次数森林(forest)----m(m³0)棵互不相交的树的集合树中同一层各

3、结点从左至右看成是有序的（即不能互换），则称该树为有序树，否则称为无序树。树的基本概念结点A的度：3叶子：K，L，F，G，M，I，J结点B的度：2结点M的度：0结点I的双亲：D结点A的孩子：B，C，DA结点L的双亲：E结点B的孩子：E，F结点B，C，D为兄弟BCD树的度：3结点K，L为兄弟EFGHIJ树的深度：4KLM结点F，G为堂兄弟结点A的层次：1结点A是结点F，G的祖先结点M的层次：4二叉树–定义定义：二叉树是n(n³0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉

4、树构成树特点–每个结点至多有二棵子树(即不存在度大于2的结点)–二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态AAAABBBC只有根结点左、右子树空二叉树的二叉树右子树为空左子树为空均非空几种特殊形式的二叉树满二叉树定义：特点：每一层上的结点数都是最大结点数完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1完全二叉树树1

5、1满二叉树判断23234567458911111167完全二叉树判断123145672345689111二叉树的应用二叉树的一大好处就是子结点个数是可以确定的,就是只需二个指域即可.在实现时需要存储结构比较简单.广泛的应用软件实现中.二叉树应用实例–哈夫曼树/哈夫曼编码,JPEG中就应用了哈夫曼编码–电子商务中文件签署的日期的保护。数字时间戳服务（DTS）是网上安全服务项目，由专门的机构提供。时间戳(time-stamp)是一个经加密后形成的凭证文档,Bellcore创造的DTS采用如下的过程：加密时将摘要信息归并到二叉树

6、的数据结构；再将二叉树的根值发表在报纸上，这样更有效地为文件发表时间提供了佐证。树的存储结构树在存储结构的表示树相对链表更加复杂,可以用多种方法来表示树的存储结构双亲表示法–即每个结点只保存父结点的指针域,这意味着每个结点的指针域固定为一个–这种方法在找双亲容易，找孩子和兄弟难孩子表示法–每一个结点保存自已所有子结点的指针域树–一般需要多重链表来保存,这种方法比较接近树本身的表示,但数据处理复杂.孩子兄弟表示法(二叉树)–用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点双亲表示法

7、双亲表示法–实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置–特点：找双亲容易，找孩子难typedefstructnode{intparent;datatypedata;}JD;JDt[M];双亲表示法的顺序存储0号单元不用或datpareaant存结点个数009bc1a02b1def3c14d2ghi5e26f37g58h5如何找孩子结点9i5孩子表示法–多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D树结点不同构

8、：结点指针个数不等，为该结点的度ddatachild1child2……….childDdatadegreechild1child2……….childd–孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：typedefstructnode{intchild;//该