常见树的存储结构，及如何求以孩子兄弟法存储的森林的叶子结点数 |
您所在的位置：网站首页 › 编程求以孩子兄弟表示法存储的森林的叶子结点数 › 常见树的存储结构，及如何求以孩子兄弟法存储的森林的叶子结点数 |
|
树的存储方式有很多种，既可以采用顺序存储结构，也可以采用链式存储结构，只要能唯一地反映树中的各结点之间的逻辑关系就可以 首先介绍第一种，双亲表示法 双亲表示法：用一片连续空间（数组）来存储每个结点，同时在每个结点中增设一个伪指针（指明其双亲结点在数组中的位置）。因为根结点没有双亲，所以他的伪指针域规定为－1。 #define MAX_TREE_SIZE 100 //树中结点数 typedef struct { ElemType data; int parent; //双亲在数组中的位置域 }PTNode; //结点 typedef struct { PTNode nodes[MAX_TREE_SIZE]; //双亲 int n; //结点数 }PTree; //树该存储结构利用了除根结点外每个结点只有唯一双亲的性质，可以利用数组的随机访存性质快速找到双亲，但是如果要求结点的孩子就很麻烦了，需要遍历整张表。 孩子表示法：将每个结点的孩子结点都用单链表横向链接起来，纵向可以用一个线性结构存储每个结点的头指针，n个结点就需要n个孩子链表 特点：寻找孩子结点比较方便，只需要纵向找到待求结点，横向遍历链表找到目标结点即可，但是寻找双亲则需要O(nE)的时间复杂度，几乎把整张庞大的表都遍历了。 孩子兄弟表示法：这种方法不错，又称为二叉树表示法 typedef struct CSNode { EmemType data; struct CSNode *first_child, *next_bro; }CSNode, *CSTree;这种存储方法比较的灵活，最大的优点是可以很方便地将树转换成二叉树，易于查找结点的孩子，缺点是从当前结点查找双亲结点比较麻烦。解决方法：刚刚ADT里加一个指针，指向parent。 关键点：如何从树转换到二叉树 规则：左孩子右兄弟，每个结点左指针指向第一个孩子，右指针指向它在树中相邻的右兄弟。 Tips：假设n0个叶子结点，则有n0 + 1个右指针为空的二叉树结点（因为包含一个根结点没有右兄弟，或者包含最右边的树的根结点没有右兄弟） 如何求以孩子兄弟表示法存储的森林的叶子结点数？ 算法思想：叶子结点等价于左指针为空（即没有孩子了），此算法相当于求二叉树中无左孩子的结点数 算法实现： typedef struct node { ElemType data; struct node *firstChild, *nextBro; }*Tree; int getLeavesNum(Tree T) { if(T == NULL) { return 0; } if(T->firstChild == NULL) { //没有左孩子了，则该结点一定是叶子结点 return 1+getLeavesNum(T->nextBro); //递归调用，数量累加，看看兄弟还有没有叶子结点 } else { return getLeavesNum(T->firshChild) + getLeavesNum(T->nextBro); //孩子子树和兄弟子树叶子树之和 } } |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |