1、数据结构与算法树与二叉树赵颖 中南大学，赵颖 中南大学 n 在本章前面的内容中，我们首先讲解了树的定义，然后就过渡到对二叉树的讲解，包括二叉树的定义、存储结构、基本操作（遍历）等等问题。n 其实，二叉树是树的特例，对于树，也会有存储和基本操作。n 下面我们就来讲解树的相关问题，包括：树的存储结构、树的基本操作（遍历）、树与二叉树的转化赵颖 中南大学目录n 树的存储结构n 树、森林与二叉树的转化n 树的遍历n 应用举例：哈夫曼树赵颖 中南大学树的存储结构n 双亲表示法 在树中， 每个结点的双亲是唯一的 ，利用这个性质，可以在存储节点信息同时，为每个结点设置一个指向其双亲的指针，这样就能唯
2、一的表示一棵树了。 数据结点表示：数据元素域，双亲结点指针域 物理存储方式：顺序表或者链表n （下面用顺序表为例，使用一组连续的存储单元来存放树中的结点） 注意：双亲表示法（以及后面讲的孩子表示法、双亲孩子表示法）是对树这种结构的一种 逻辑表示法 ，对应于具体的物理存储方式可以使用顺序表也可以使用链表，要注意区分逻辑表示和物理存储的差别。赵颖 中南大学树的存储结构n 双亲表示法 const MAX_TREE_SIZE = 100; typedef struct / 结点结构ElemType data;int parent; / 双亲位置域 PTNode; typedef struct / 树
3、结构PTNode nodesMAX_TREE_SIZE;int r, n; / 根的位置和结点数 PTree;赵颖 中南大学树的存储结构n 双亲表示法 好处：有利用于 “向上 ”查找 (利用结点双亲的唯一性 )。 不利： “向下 ”查找需遍历全部存储结点。AB DCE F GH I JR=0, n=10赵颖 中南大学树的存储结构n 孩子表示法 孩子表示法主要描述的是 结点的孩子关系 。 由于每个结点的孩子个数不定，所以在每个结点上设置多个指向孩子的指针域（称作 多重孩子域 ）的方式是不合适的。这种方法不但不能确定要设置多少个指针域，而且会浪费空间。如何表示孩子更好呢？data child1
4、 child2 child3 childd赵颖 中南大学树的存储结构n 孩子表示法 为树中所有结点建立一个线性表，用一个地址连续的存储空间来存储，数组中每个元素 2个域，一个数据域（存放结点的数据），一个指针域（指向该结点的所有孩子组成的单链表的表头） 为每个结点的所有孩子结点都建立一个线性表，且以单链表作它的存储结构，单链表中每个元素 2个域，一个数据域（存放该孩子在结点数组中的下标），一个指针域（指向下一个孩子结点）。赵颖 中南大学树的存储结构n 孩子表示法 typedef struct CTNode / 孩子结点 int child;struct CTNode *next; *ChildPtr; typedef struct ElemType data; / 结点的数据元素ChildPtr firstchild; / 孩子链表头指针 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE;int n, r; / 结点数和根结点的位置 CTree;赵颖 中南大学树的存储结构n 孩子表示法 优点：寻找某个结点的孩子比较容易 缺点：寻找双亲比较麻烦
