树和森林练习
|
|
数据结构

1230 字
|
14 分钟

非算法题

1、设F为一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有___个

森林转化为二叉树，二叉树结点右指针为空的代表该结点无兄弟。

森林最后一棵树的根结点的右指针为空 + 每个非终端结点，其所有孩子结点在转换后，最后一个孩子的右指针为空。

即： 森林中有 n个非终端结点，那对应的二叉树中有 1 + n 个右指针为空的结点。

2、已知一棵有2011个结点的树，其叶子结点个数为116，该树对应的二叉树中无右孩子的结点个数为____

和 第一题 类似，树转换为二叉树，树的每个分支结点的所有子结点的最右结点无右兄弟 + 根结点无右兄弟。

即：对应的二叉树中无右孩子的结点个数 = 分支结点数 + 1 = 2011 – 116 + 1 = 1896

阿Q得出的结论：

森林或树中有n个分支结点，则对应的二叉树中有 n + 1个右指针为空的结点

3、将森林F 转换为对应的二叉树T，F中的叶子结点个数等于

  • T中叶结点的个数
  • T中度为1的结点个数
  • T中左孩子指针为空的结点个数
  • T中右孩子指针为空的结点个数

森林转化为二叉树，结点的左指针指向第一个孩子。

森林中的叶子结点 说明 该结点无孩子（无法得知该结点是否有右兄弟），对应转化而来的结点左指针为空。

因此：森林的叶子结点个数等于对应二叉树左孩子指针为空的结点个数。

算法题

孩子兄弟链表 （二叉树表示法）

1、编程求以孩子兄弟表示法存储的森林的叶结点数

分析：森林对应的二叉树中，若某结点左指针为空，则说明该结点无孩子，即对应的森林的叶子结点。

那么可以采用递归来快速解决此问题。（总叶结点树 = 孩子子树上的叶结点树 + 兄弟子树上的叶结点数）

二叉树表示法 存储类型表示 
typedef int ElemType;

typedef struct CSNode
{
    /* data */
    ElemType data;
    
    // 指向第一个孩子 
    struct CSNode *firstchild;

    // 指向兄弟
    struct CSNode *nextsibling;

    CSNode(ElemType x = 0): data(x), firstchild(nullptr), nextsibling(nullptr){}

}CSNode, *CSTree;
int LeafNode(CSTree T){
    // 空二叉树
    if(!T) return 0;
    
    // 某结点左指针为空，则说明该结点无孩子
    if(!T->firstchild) return 1 + LeafNode(T->nextsibling);

    return LeafNode(T->firstchild) + LeafNode(T->nextsibling);
}
测试代码 
int main(){
    CSTree T1 = new CSNode;
    T1->firstchild = new CSNode;
    T1->firstchild->nextsibling = new CSNode;
    T1->firstchild->nextsibling->nextsibling = new CSNode;

    CSTree T2 = new CSNode;
    T2->firstchild = new CSNode;

    T1->nextsibling = T2;

    CSTree T3 = new CSNode;
    T3->firstchild = new CSNode;
    T3->firstchild->nextsibling = new CSNode;

    T2->nextsibling = T3;

    int leaf = LeafNode(T1);
    std::cout << leaf;
    
    return 0;
}
/*
输出结果：
6
*/

2、以孩子兄弟链表为存储结构，设计递归算法求树的深度

此题递归过程相对简单（写起来简单，理解其实不那么容易的），只需比较左支高度和右支高度即可。

若 左支高度 > 右支高度，返回 左支高度 + 1（返回到上一层递归）

否则 返回 右支高度 + 1。

int Height(CSTree T){
    /*
    递归过程：
        左高度 > 右高度，记录左高度 + 1
        左高度 < 右高度，记录右高度 + 1
    */

    // 空树高度为0
    if(!T) return 0;

    // 记录左右高度
    int lheight, rheight;

    lheight = Height(T->firstchild);

    rheight = Height(T->nextsibling);

    // 若左高度 > 右高度，则记录左高度 + 1 (返回上一层递归)
    if(lheight > rheight) return lheight + 1;
    else return rheight + 1;
}

3、已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表（有难度）

此题难点在于：如何获取数组下标为n所对应结点的指针

阿Q借鉴了王道课本的解法，辅助数组先将结点创建出来，能轻松获取下标为n所对应结点的指针。

如图：

void CreateCSTree(CSTree &T, ElemType LevelNode[], int degree[], int n) 
{ 
    // 此题难以解决点：怎么获取 数组下标为n 对应结点的指针呢？ 
    // 阿Q看了 王道课本的解法，先把这些结点创建出来，用辅助数组存着
    CSTree Node[n]; 
    for(int i = 0; i < n; i++) 
        Node[i] = new CSNode(LevelNode[i]); 
    
    int cursor = 0; 

    // 记录待创建的结点下标 (根结点已创建)
    int node_cursor = 1; // 从 1 开始，因为 0 是根节点 
 
    // 遍历每个节点 
    while(cursor < n) 
    { 
        // 创建该结点的孩子结点 - 二叉树的第一个孩子 + 右支 
        for(int i = 0; i < degree[cursor]; i++) 
        { 
            if (node_cursor >= n) break; // 防止越界 
 
            // 第一个孩子 - 左支 
            if(i == 0) Node[cursor]->firstchild = Node[node_cursor]; 
            else Node[node_cursor - 1]->nextsibling = Node[node_cursor]; 
 
            node_cursor++; 
        } 
        cursor++; 
    } 
    // 赋根指针 
    T = Node[0];
    
    // 此处辅助数组静态分配，无须手动释放
}
完整代码 
// 已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表

// 假设层次遍历为 [A, B, C, D, E, F, G]
// 结点度为 [3, 2, 0, 1, 0, 0, 0]
// 构造出 该树对应的二叉树
#include<iostream>
typedef char ElemType;

typedef struct CSNode
{
    /* data */
    ElemType data;
    
    // 指向第一个孩子 
    struct CSNode *firstchild;

    // 指向兄弟
    struct CSNode *nextsibling;

    CSNode(ElemType x): data(x),firstchild(nullptr), nextsibling(nullptr){}

}CSNode, *CSTree;

void CreateCSTree(CSTree &T, ElemType LevelNode[], int degree[], int n) 
{ 
    // 此题难以解决点：怎么获取 数组下标为n 对应结点的指针呢？ 
    // 阿Q看了 王道课本的解法，先把这些结点创建出来，用辅助数组存着
    CSTree Node[n]; 
    for(int i = 0; i < n; i++) 
        Node[i] = new CSNode(LevelNode[i]); 
    
    int cursor = 0; 

    // 记录待创建的结点下标 (根结点已创建)
    int node_cursor = 1; // 从 1 开始，因为 0 是根节点 
 
    // 遍历每个节点 
    while(cursor < n) 
    { 
        // 创建该结点的孩子结点 - 二叉树的第一个孩子 + 右支 
        for(int i = 0; i < degree[cursor]; i++) 
        { 
            if (node_cursor >= n) break; // 防止越界 
 
            // 第一个孩子 - 左支 
            if(i == 0) Node[cursor]->firstchild = Node[node_cursor]; 
            else Node[node_cursor - 1]->nextsibling = Node[node_cursor]; 
 
            node_cursor++; 
        } 
        cursor++; 
    } 
    // 赋根指针 
    T = Node[0]; 
    
    // 此处辅助数组静态分配，无须手动释放
} 


int main(){
    int n = 7;
    ElemType levelNode[n] = {'A','B','C','D','E','F','G'};
    int degree[7] = {3, 2, 0, 1, 0, 0, 0};

    CSTree T;
    CreateCSTree(T, levelNode, degree, n);    
    
    std::cout << T->firstchild->firstchild->nextsibling->data << std::endl;

    // 此处由于每个结点动态分配，地址应该不连续
    std::cout << (void*)T << std::endl;
    std::cout << (void*)T->firstchild << std::endl;
    std::cout << (void*)T->firstchild->nextsibling << std::endl;
    std::cout << (void*)T->firstchild->nextsibling->nextsibling << std::endl;
    std::cout << (void*)T->firstchild->firstchild << std::endl;

    return 0;
}
/*
输出结果：
F
0x254bb3739e0
0x254bb3739a0
0x254bb3737e0
0x254bb373780
0x254bb373a00
*/

阿Q觉得王道课本中的代码存在问题

void CreateCSTree(CSTree &T, ElemType LevelNode[], int degree[], int n) 
{
    CSNode *Node = new CSNode[n];
    for(int i = 0; i < n; i++)
        Node[i]->data = LevelNode[i];  // 错误
    ...
    delete[] Node;      // 错误
}

王道课本中为直接动态分配若干个结点，那么Node[i] 不为指针，而为结点，因此Node[i]->data错误。

此外最后将动态分配的结点给注销掉是什么意思，那么这棵树还会存在嘛？

课本思想正确，但阿Q觉得25版的代码问题不小。

树森林
暂无评论

发送评论 编辑评论 
















































































































上一篇
下一篇