您现在的位置是:首页 > 正文

广义表之树的兄弟孩子表示法

2024-01-30 20:30:59阅读 0

title: 广义表之树的兄弟孩子表示法
date: 2020-11-17 15:55:55
tags:

  • 兄弟孩子广义表
  • 二叉树
    categories: 数据结构

用兄弟孩子广义表来表示二叉树

对比

二叉树转化来的兄弟孩子广义表和普通的兄弟孩子广义表并不相同

  • 二叉树转换成的兄弟孩子广义表没有明确的一块内存结构来直接表示它是叶子节点还是双亲结点,而是通过 指针 tp 来隐式地表示,tp 指向空,表示它没有孩子节点,否则,有孩子结点

  • 普通的兄弟孩子广义表则是通过 tag = 0 或 1 来表示它是否还有孩子结点

  • 普通的广义表如果转换成树,那么转换成的是只有在叶子结点中存数据的树,根结点,和树中间的双亲节点可以理解成一级一级的括号。

  • 如果还要说不同的话,那就是二叉树中一个双亲结点最多有2 个孩子结点, 而普通的广义表则不同

  • 在求深度的时候,刚开始要设一个 max = 0来表示下一层的深度的最大值, 树转换来的兄弟孩子广义表,下一层只要有结点,那么下一层的深度必为 1 ,直接return max + 1即可,但是普通的广义表,下一层有结点的时候并不能代表下一层的深度就是 1, 因为如果下一层都是 tag为 0 的结点,那么下一层的深度就都是 0 ,不可return max + 1, 需要return maxreturn max + 1return max 的情况需要 分开讨论

  • 关于两种不同的兄弟孩子广义表求深度时候具体细节的不同,我会在下一期中具体分析

总结

总结一下不同的树 转换成表

  • 二叉树 转换成兄弟孩子广义表 (特殊的表,这种表没有tag 的 0 或 1 来表示它是原子结点还是表结点)
  • 普通树 转换成兄弟孩子广义表(特殊的表, 特殊同上)
  • 每一个双亲结点最多有两个孩子结点的兄弟孩子广义表 转换成树(特殊的二叉树, 只有叶子结点存数据)
  • 一个双亲结点可有任意个孩子结点的兄弟孩子广义表 转换成树(特殊的树,只有叶子结点存数据)

代码功能

  • 根据输入的一串字符(字符按树的每一层的结点内容输入),自动建立用兄弟孩子广义表表示的二叉树
  • 先序打印树
  • 转换成兄弟孩子广义表后,在兄弟孩子广义表的基础上求树的深度

代码附上

// 求树的深度

// 兄弟孩子存储结构的树的深度 其实和广义表的兄弟孩子存储结构求深度没有什么区别
// 只不过标识符不一样了, 广义表的标识符是 tag , 而现在 标识符通过指向左孩子的指针来
// 隐式表示 , 若指针为空,那么表示这个是一个 叶子节点(即广义表中的原子) 若不为空,则它还有孩子结点

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100

typedef char Elemtype;
typedef struct node
{
    Elemtype data;
    // 指向本结点左孩子结点的指针,和指向本结点下一个兄弟的指针
    struct node *hp, *tp;
} Node, *Tree;

// 初始化二叉树
void Init(Tree *);

// 通过输入一串字符来初始化二叉树
void Creat(Tree, char *, int);
void Creat2(Tree, char *, int);
// 输入一串字符并返回
char *Input();

// 遍历二叉树
void PrintTree(Tree);

// 求深度
int GetDepth(Tree);

int main(void)
{
    Tree tree;
    Init(&tree);
    char *str = Input();
    Creat(tree, str, 0);
    PrintTree(tree->hp);
    printf("\n");
    int depth = GetDepth(tree->hp);
    printf("%d\n",depth);
    return 0;
}
// 初始化一个带头结点的二叉树
void Init(Tree *pTree)
{
    *pTree = (Node *)malloc(sizeof(Node));
    (*pTree)->data = '0';
    (*pTree)->hp = NULL;
    (*pTree)->tp = NULL;
}
char *Input()
{
    char *s = (char *)malloc(sizeof(char) * MAX);
    memset(s, '0', sizeof(char) * MAX);
    gets(s);
    int len = strlen(s);
    // 将输入的字符串转化成下标从1开始
    for (int i = strlen(s); i > 0; i--)
        s[i] = s[i - 1];
    return s;
}
// 创建一个二叉树
// 刚开始传的参数是  头指针, 字符数组, 0
void Creat(Tree tree, char *str, int i)
{
    // 这个函数的利用价值:
    // 当 i == 0 时,由于传进来的是头指针
    // 并且头指针指向的是头结点,和别的情况不一样
    // 所以需要在递归函数外面单独执行一次

    // 如果根节点就是 '0' 也就代表着这棵树是空的
    if (str[1] == '0')
        return;

    Node *p = (Node *)malloc(sizeof(Node));
    p->data = str[1];
    tree->hp = p;
    Creat2(p, str, 1);
}
void Creat2(Tree tree, char *str, int i)
{
    tree->data = str[i];
    // 先解决这个结点的hp
    if (str[i * 2] == '0' && str[i * 2 + 1] == '0')
        tree->hp = NULL;
    else
    {
        Node *p = (Node *)malloc(sizeof(Node));
        tree->hp = p;
        Creat2(p, str, i * 2);
    }
    // 然后解决这个结点的 tp
    if (str[i + 1] == '0' || i % 2 == 1)
        tree->tp = NULL;
    else
    {
        Node *q = (Node *)malloc(sizeof(Node));
        tree->tp = q;
        Creat2(q, str, i + 1);
    }
}

// 遍历并打印二叉树
// 传进来的是头结点中存的hp
// 即指向根结点的指针,而不是头指针
void PrintTree(Tree tree)
{
    if (tree == NULL)
        printf("二叉树为空\n");
    printf("%c ", tree->data);
    if (tree->hp)
        PrintTree(tree->hp);
    if (tree->tp)
        PrintTree(tree->tp);
}

// 求深度
int GetDepth(Node *T)
{
	if (!T)
		return 0;
	int max = 0;
	for (Node *temp = T; temp; temp = temp->tp)
	{
		int depth = GetDepth(temp->hp);
		if (max < depth)
			max = depth;
	}
	return max + 1;
}

求深度算法(二)

横向纵向都用到了递归,上面那个方法只有纵向用到了递归,横向依靠的是for循环

// 求深度算法 2 
int getDep(BitTree T)
{
    // 空树返回 0
    if (!T)	return 0;
    // 求当前结点的深度 - 1(既然当前结点存在,其深度必 >= 1)
    int dep1 = getDep(T->down);
    // 求当前结点的兄弟结点的深度
    // 这个语句会在第一次执行的时候不断递归,所以当递归回来到第一次
    // 执行的函数中的时候, dep2已经是第二个结点以及第二个结点之后的所有结点中
    // 深度的最大值, 看似这个递归只比较了两个结点,实则该递归比较了一级中的所有结点
    // 省去了遍历当前层所有结点的操作
    // 横向纵向同时递归
    int dep2 = getDep(T->right);
    // 比较,若当前结点深度 大于 下一个兄弟结点,就返回当前结点深度
    // 否则 返回下一个兄弟结点的深度
    if (dep1 + 1 > dep2)
		return dep1 + 1;
	return dep2;
}

网站文章

  • MySQL~Undo日志(作用、存储结构、生命周期/运行过程)

    MySQL~Undo日志(作用、存储结构、生命周期/运行过程)

    文章目录Undo日志作用存储结构生命周期/运行过程Undo日志Undo日志保证了事务原子性每次更新一条数据之前都会先写入一条undo日志在运行过程中,如果数据库宕机或是事务回滚,都需要把数据恢复成原来...

    2024-01-30 20:30:21
  • Linux中的Shell编程

    Linux中的Shell编程

    Shell 是一个命令解释器,它为用户提供了一个向 Linux 内核发送请求以便运行程序界面系统级程序,用户可以用 Shell 来启动、挂起、停止甚至是编写一些程序。2.对于JavaEE和Python...

    2024-01-30 20:30:15
  • 批量重命名文件、图片、去除文件名括号

    批量重命名文件、图片、去除文件名括号

    批量重命名文件、图片、去除文件名括号

    2024-01-30 20:30:10
  • Google面试问题指南:使用Python删除重复出现的字符

    Google面试问题指南:使用Python删除重复出现的字符

    来源 | 愿码(ChainDesk.CN)内容编辑愿码Slogan | 连接每个程序员的故事网站 | http://chaindesk.cn愿码愿景 | 打造全学科IT系统免费课程,助力小白用户、初级工程师0成本免费系统学习、低成本进阶,帮助BAT一线资深工程师成长并利用自身优势创造睡后收入。官方公众号 | 愿码 | 愿码服务号 | 区块链部落免费加入愿码全思维工程师社群 | 任一...

    2024-01-30 20:29:35
  • 装饰者模式

    装饰者模式

    设计模式:专门为解决某一类问题,而编写的固定格式的代码。装饰者模式一、职责1、动态的为一个对象增加新的功能2、装饰模式是一种用于替代继承的技术,无需通过继承增加子类就能扩展对象的新功能。使用对象的关联关系代替继承关系,更加灵活,同时避免类型体系的快速膨胀。二、实现细节1、Component抽象构件角色:真实对象和装饰对象有相同的接口。这样,客户端对象就能够以与真实...

    2024-01-30 20:29:29
  • JVM内存布局

    JVM内存布局

    Survivor区分为S0和S1两块内存空间,每次YGC时,它们将存活的对象复制到未使用的那块空间,然后将当前正在使用的空间完全清除,交换两块空间的使用状态。当大量本地方法出现时,势必会削弱JVM对系...

    2024-01-30 20:29:22
  • css固定定位

    css固定定位

    主要使用场景:可以在浏览器页面滚动元素时元素的位置不会改变。1、以浏览器的可视窗口作为参考点移动元素。4、不占有固定位置,浮起来了。3、不随滚动条的滚动而变化。2、和父元素没有关系。

    2024-01-30 20:28:51
  • 使用jQuery的ajax上传文件报错:Uncaught TypeError: Illegal invocation

    使用ajax上传文件,代码如下:$('#video-upload-btn').on('change', function(){ var file = this.files[0]; var data =...

    2024-01-30 20:28:44
  • Java代码审计之RCE(远程命令执行)

    Java代码审计之RCE(远程命令执行)

    Java代码审计系列课程(点我哦)漏洞原理:RCE漏洞,可让攻击者直接向后台服务器远程注入操做系统命令或者代码,从而控制后台系统。出现此类漏洞通常由于应用系统从设计上须要给用户提供指定的远程命令操做的...

    2024-01-30 20:28:37
  • Android面试题集-常见几个面试题详解

    Android面试题集-常见几个面试题详解

    跳槽,这在 IT 互联网圈是非常普遍的,也是让自己升职加薪,走上人生巅峰的重要方式。那么作为一个普通的Android程序猿,我们如何才能斩获大厂offer 呢? 疫情向好、面试在即,还在迷茫踌躇中的后...

    2024-01-30 20:28:06