数据结构例程——以孩子兄弟链存储的树的高度

简介: 本文是数据结构基础系列(6):树和二叉树中第5课时树的存储结构的例程。例: 以孩子-兄弟链作为存储结构,求树的高度 源程序:【说明——函数TreeCreate仅创建了如上图所示的图,不具有通用性。】#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef s

本文是数据结构基础系列(6):树和二叉树第5课时树的存储结构的例程。

例: 以孩子-兄弟链作为存储结构,求树的高度
这里写图片描述

源程序:【说明——函数TreeCreate仅创建了如上图所示的图,不具有通用性。】

#include <stdio.h>
#include <malloc.h>

typedef char ElemType;
typedef struct tnode
{
    ElemType data;  //节点的值
    struct tnode *hp;   //指向兄弟
    struct tnode *vp;   //指向孩子节点
} TSBNode;
int TreeHeight(TSBNode *t);
void TreeCreate(TSBNode *&t);
void TreeDisp(TSBNode *t);

int TreeHeight(TSBNode *t)
{
    TSBNode *p;
    int m, max = 0;
    if(t==NULL)
        return(0);
    else if(t->vp==NULL)
        return(1);
    else
    {
        //求t的子树的最大高度max
        p=t->vp;
        while(p!=NULL)
        {
            m=TreeHeight(p);
            if(max<m)
                max=m;
            p=p->hp;
        }
        return(max+1);
    }
}

int main()
{
    TSBNode *tree;
    TreeCreate(tree);
    printf("Height: %d\n", TreeHeight(tree));
    TreeDisp(tree);
    return 0;
}

void TreeCreate(TSBNode *&t)
{
    //本例仅建造说明中特定的树,以支持演示
    TSBNode *a, *b, *c, *d, *e, *f, *g;
    a = (TSBNode *)malloc(sizeof(TSBNode));
    b = (TSBNode *)malloc(sizeof(TSBNode));
    c = (TSBNode *)malloc(sizeof(TSBNode));
    d = (TSBNode *)malloc(sizeof(TSBNode));
    e = (TSBNode *)malloc(sizeof(TSBNode));
    f = (TSBNode *)malloc(sizeof(TSBNode));
    g = (TSBNode *)malloc(sizeof(TSBNode));
    a->data = 'a';
    b->data = 'b';
    c->data = 'c';
    d->data = 'd';
    e->data = 'e';
    f->data = 'f';
    g->data = 'g';
    a->vp = b;
    a->hp = NULL;
    b->vp = d;
    b->hp = c;
    c->vp = NULL;
    c->hp = NULL;
    d->vp = NULL;
    d->hp = e;
    e->vp = g;
    e->hp = f;
    f->vp = NULL;
    f->hp = NULL;
    g->vp = NULL;
    g->hp = NULL;
    t=a;  //a作为根
    return;
}

void TreeDisp(TSBNode *t)
{
    if(t!=NULL)
    {
        printf("node value: %c\n", t->data);
        printf("%c\'s first child --> ", t->data);
        TreeDisp(t->hp);
        printf("%c\'s brother(its father\'s another child) --> ", t->data);
        TreeDisp(t->vp);
    }
    else
    {
        printf("NULL\n");
    }
}
目录
相关文章
|
4天前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
27 3
 算法系列之数据结构-Huffman树
|
4月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
83 0
|
2月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
72 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
61 12
|
2月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
60 10
|
2月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
59 10
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
60 2
|
5月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
165 64
|
4月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
107 5
|
4月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
173 16