精华内容
下载资源
问答
  • 1.设结点A 有3个兄弟结点且结点B...双亲节点:假设AB 的子节点,那么B就可以称为它的双亲节点 所以题目中A有三个兄弟节点,加上就一共有四个节点,所以B是他们的双亲结点,所以度为4,选B。 如图所示 大致就是这样...

    1.设结点A 有3个兄弟结点且结点B为结点A的双亲结点,则结点B 的度数为________。

    A.
    3

    B.
    4

    C.
    5

    D.
    6
    答案:B
    解析:首先我们搞清楚兄弟节点和双亲节点的定义。

    兄弟节点:同一双亲节点下的节点
    双亲节点:假设A是B 的子节点,那么B就可以称为它的双亲节点
    所以题目中A有三个兄弟节点,加上就一共有四个节点,所以B是他们的双亲结点,所以度为4,选B。

    如图所示 大致就是这样

    在这里插入图片描述

    展开全文
  • 前面讲了二叉树的顺序存储和链式存储,本节来学习如何存储...双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量。注意,根节点没...

    前面讲了二叉树的顺序存储和链式存储,本节来学习如何存储具有普通树结构的数据。

    48daf30f2b261ad7ab0837998adc003d.png

    图 1 普通树存储结构

    如图 1 所示,这是一棵普通的树,该如何存储呢?通常,存储具有普通树结构数据的方法有 3 种:双亲表示法;

    孩子表示法;

    孩子兄弟表示法;

    本节先来学习双亲表示法。

    双亲表示法采用顺序表(也就是数组)存储普通树,其实现的核心思想是:顺序存储各个节点的同时,给各节点附加一个记录其父节点位置的变量。

    注意,根节点没有父节点(父节点又称为双亲节点),因此根节点记录父节点位置的变量通常置为 -1。

    例如,采用双亲表示法存储图 1 中普通树,其存储状态如图 2 所示:

    48daf30f2b261ad7ab0837998adc003d.png

    图 2 双亲表示法存储普通树示意图

    图 2 存储普通树的过程转化为 C 语言代码为:#define MAX_SIZE 100//宏定义树中结点的最大数量 typedef char ElemType;//宏定义树结构中数据类型 typedef struct Snode{ TElemType data;//树中结点的数据类型 int parent;//结点的父结点在数组中的位置下标 }PTNode; typedef struct { PTNode tnode[MAX_SIZE];//存放树中所有结点 int n;//根的位置下标和结点数 }PTree;

    因此,存储图 1 中普通树的 C 语言实现代码为:#include #include #define MAX_SIZE 20 typedef char ElemType;//宏定义树结构中数据类型 typedef struct Snode  //结点结构 {     ElemType data;     int parent; }PNode; typedef struct  //树结构 {     PNode tnode[MAX_SIZE];     int n;                 //结点个数 }PTree; PTree InitPNode(PTree tree) {     int i, j;     char ch;     printf("请输出节点个数:n");     scanf("%d", &(tree.n));     printf("请输入结点的值其双亲位于数组中的位置下标:n");     for (i = 0; i < tree.n; i++)     {         getchar();         scanf("%c %d", &ch, &j);         tree.tnode[i].data = ch;         tree.tnode[i].parent = j;     }     return tree; } void FindParent(PTree tree) {     char a;     int isfind = 0;     printf("请输入要查询的结点值:n");     getchar();     scanf("%c", &a);     for (int i = 0; i < tree.n; i++) {         if (tree.tnode[i].data == a) {             isfind = 1;             int ad = tree.tnode[i].parent;             printf("%c的父节点为 %c,存储位置下标为 %d", a, tree.tnode[ad].data, ad);             break;         }     }     if (isfind == 0) {         printf("树中无此节点");     } } int main() {     PTree tree;     for (int i = 0; i < MAX_SIZE; i++) {         tree.tnode[i].data = " ";         tree.tnode[i].parent = 0;     }         tree = InitPNode(tree);     FindParent(tree);     return 0; }

    程序运行示例:

    请输出节点个数:

    10

    请输入结点的值其双亲位于数组中的位置下标:

    R -1

    A 0

    B 0

    C 0

    D 1

    E 1

    F 3

    G 6

    H 6

    K 6

    请输入要查询的结点值:

    C

    C的父节点为 R,存储位置下标为 0原文始发于:树的双亲表示法(包含C语言实现代码)

    展开全文
  • 本文主要是对数据结构中非线性结构 树 的学习和总结。树的定义专业定义:1.有且只有一个称为根的节点2.有若干个互不相交的子树,这些子树本身也是一棵树通俗的定义:1.树由节点和边组成2.... 根节点是第一层叶子...

    本文主要是对数据结构中非线性结构 树 的学习和总结。

    树的定义

    专业定义:

    1.有且只有一个称为根的节点

    2.有若干个互不相交的子树,这些子树本身也是一棵树

    通俗的定义:

    1.树由节点和边组成

    2.每一个节点只有一个父节点但可以有多个子节点

    3.当有一个节点例外,该节点没有父节点,该节点称为根节点

    专业术语:

    节点 父节点 子节点 子孙 堂兄弟

    深度:从根节点到最底层节点的层数称之为深度。 根节点是第一层

    叶子节点:没有子节点的节点

    非终端节点: 实际就是非叶子节点

    度: 子节点的个数称为度

    树的分类

    一般树: 任意一个节点的子节点个数都不受限制。

    二叉树:任意一个节点的子节点个数最多两个,且子节点的个数不可更改。

    1. 一般二叉树

    2. 满二叉树:在不增加树的层数的前提下,无法再添加一个节点的二叉树称为满二叉树。

    3. 完全二叉树:如果只是删除了满二叉树最低存最右边的若干个连续节点,这样形成的二叉树就是完全二叉树。

    森林:n个互不相交的树的集合。

    树的存储

    二叉树的存储

    连续存储【完全二叉树】

    1. 优点: 查找某个节点的父节点和子节点(也包括有没有子节点)。

    2. 缺点:耗用内存空间过大。

    链试存储

    1. 优点:耗用内存空间小。

    一般树的存储

    1.双亲表示法: 求父节点方便。

    b867ca5765cd

    树结构.png

    b867ca5765cd

    树的双亲表示法.png

    代码结构定义

    //树的双亲表示法节点结构的定义

    #define MAX_TREE_SIZE 100

    typedef int ElemType;

    typedef struct PTNode {

    ElemType data; //节点数据

    int parent; //双亲位置

    }PTNode;

    typedef struct {

    PTNode nodes[MAX_TREE_SIZE];

    int r; //根的位置

    int n; //节点数目

    }PTree;

    上面的树存储结构图根据某个节点的parent指针找到它的双亲节点,所用的时间复杂度为O(1),索引到parent的值为-1,表示找到了树节点的根。如果我们要知道某个节点的孩子节点,就的遍历整个树结构了。

    下面是改进后的树结构存储图,可以比较方便的求出某个节点的孩子节点。

    b867ca5765cd

    图片.png

    改进过后的树存储结构,没法表示树结构中兄弟之间的关系?

    如下是改进过后最终的树结构存储图:

    b867ca5765cd

    图片.png

    2.孩子表示法:求子节点方便, 求父节点麻烦。存储结构如下:

    b867ca5765cd

    图片.png

    3.双亲孩子表示法:求父节点和子节点都很方便

    b867ca5765cd

    图片.png

    代码结构如下:

    #define MAX_TREE_SIZE 100

    typedef char ElemType;

    //孩子节点

    typedef struct CTNode {

    int child; //孩子节点的下标

    struct CTNode *next;//指向下一个孩子节点的指针

    } *ChildPtr;

    typedef struct {

    ElemType data; //存放在树中的节点的数据

    int parent; //存放双亲的下标

    ChildPtr firstchild; //指向第一个孩子的指针

    }CTBox;

    //树结构

    typedef struct {

    CTBox nodes[MAX_TREE_SIZE]; //节点数组

    int r, n;

    };

    4.二叉树表示法:把一个普通树转化成二叉树来存储

    具体转换方法(把一个普通树转化成二叉树):设法保证任意一个节点的左指针域指向他的第一个孩子,右指针域指向他的下一个兄弟,只要能满足此条件就能把一个普通的树转换成二叉树,一个普通树转换成二叉树一定没有右子树。

    森林的存储

    先把森林转化为二叉树,再存储二叉树

    树的操作

    遍历

    先序遍历【先访问根节点】: 先访问根节点,再先序访问左子树,再先序访问右子树

    中序遍历【中间访问根节点】:中序遍历左子树,再访问根节点,再中序遍历右子树

    后序遍历【最后访问根节点】:先中序遍历左子树,中序遍历右子树,再访问根节点

    已知两种遍历序列求原始二叉树

    通过先序和中序或者中序和后序我们可以还原出原始二叉树,但 `通过先序和后序是无法还原出原始的二叉树`

    换种说法:只有通过先序和中序,或通过中序和后序,我们才可以唯一的确定一个二叉树。

    应用

    1. 树是数据库中数据组织一种重要的形式

    2. 操作系统子父进程的关系本身就是一棵树

    3. 面向对象语言中类的继承关系

    4. 赫夫曼树

    树的遍历相关算法的实现(C语言)

    #include

    #include

    //定义二叉树的节点

    struct BTNode {

    int data; //存放二叉树节点的数据域

    struct BTNode *pLchild; //指向左孩子结点的指针

    struct BTNode *pRchild; //指向右孩子结点的指针

    };

    //创建一颗二叉树,返回头结点的指针

    struct BTNode *CreateBTree(void);

    //先序遍历二叉树

    void PreTraverseBTree(struct BTNode *pT);

    //中序遍历二叉树

    void InTraverseBTee(struct BTNode *pT);

    //后续遍历二叉树

    void PostTraverseBTree(struct BTNode *pT);

    struct BTNode *CreateBTree(void)

    {

    struct BTNode * pA = (struct BTNode*)malloc(sizeof(struct BTNode));

    struct BTNode * pB = (struct BTNode*)malloc(sizeof(struct BTNode));

    struct BTNode * pC = (struct BTNode*)malloc(sizeof(struct BTNode));

    struct BTNode * pD = (struct BTNode*)malloc(sizeof(struct BTNode));

    struct BTNode * pE = (struct BTNode*)malloc(sizeof(struct BTNode));

    pA->data = 'A';

    pB->data = 'B';

    pC->data = 'C';

    pD->data = 'D';

    pE->data = 'E';

    pA->pLchild = pB;

    pA->pRchild = pC;

    pB->pLchild = pB->pRchild = NULL;

    pC->pLchild = pD;

    pC->pRchild = NULL;

    pD->pLchild = NULL;

    pD->pRchild = pE;

    pE->pLchild = pE->pRchild = NULL;

    return pA;

    }

    void PreTraverseBTree(struct BTNode *pT) {

    //先访问根节点 再先序访问左子树 再先序访问右子树

    if (pT == NULL)

    {

    return;

    }

    printf("%c\n", pT->data);

    PreTraverseBTree(pT->pLchild);

    PreTraverseBTree(pT->pRchild);

    }

    void InTraverseBTee(struct BTNode *pT) {

    //先访问根节点 再先序访问左子树 再先序访问右子树

    if (pT == NULL)

    {

    return;

    }

    InTraverseBTee(pT->pLchild);

    printf("%c\n", pT->data);

    InTraverseBTee(pT->pRchild);

    }

    void PostTraverseBTree(struct BTNode *pT) {

    //先访问根节点 再先序访问左子树 再先序访问右子树

    if (pT == NULL)

    {

    return;

    }

    PostTraverseBTree(pT->pLchild);

    PostTraverseBTree(pT->pRchild);

    printf("%c\n", pT->data);

    }

    int main() {

    struct BTNode *pT = CreateBTree();

    printf("先序遍历\n");

    PreTraverseBTree(pT);

    printf("中序遍历\n");

    InTraverseBTee(pT);

    printf("后序遍历\n");

    PostTraverseBTree(pT);

    return 0;

    }

    展开全文
  • 节点

    2021-01-04 19:00:24
    节点 页面在加载的时候被渲染成一棵DOM树 网页中所有的内容 - 标签、内容、属性、注释、文档在DOM中称之为节点node 节点类型 文档节点 - document 只有一个 元素节点 - 标签 div p li等 属性节点 - html属性 id ...

    节点

    • 页面在加载的时候被渲染成一棵DOM树
    • 网页中所有的内容 - 标签、内容、属性、注释、文档在DOM中称之为节点node

    节点类型

    • 文档节点 - document 只有一个
    • 元素节点 - 标签 div p li等
    • 属性节点 - html属性 id src type 等
    • 内容 - 标签之间的文字
    • 注释节点 - 注释
    • 以上五种节点我们操作最多的是元素节点

    节点属性

    • 每一个节点都有三个属性
    • nodeType 节点类型
    • nodeName 节点名称 - 重要 div - DIV
    • nodeValue 节点值

    节点关系

    • 父子
    • 祖先
    • 同胞

    节点遍历 - 了解

    • 遍历所有的节点,包括文档、注释、属性、内容、元素
    • 元素 、注释、内容
    • childNodes 获取所有的子节点(NodeList);通过索引可以获取对应的子节点,索引从0开始,具有length属性,获取子节点的数量
    • firstChild 获取第一个子节点
    • lastChild 获取最后一个子节点
    • nextSibling 获取下一个兄弟节点
    • previousSibling 获取上一个兄弟节点
    • parentNode 获取父节点 ---- 重要 - 记住

    元素遍历 - 比较重要

    • 元素 - 标签
    • 遍历 - 查找某一个元素相关联的元素 -比如: 父元素 - 子元素 -兄弟元素
    • children 获取所有的子元素(HTMLCollection),伪数组返回
    • childElementCount 获取子元素的数量
    • firstElementChild 第一个子元素节点
    • lastElementChild 最后一个子元素节点
    • previousElementSibling 上一个兄弟元素节点
    • nextElementSibling 下一个兄弟元素节点
    • parentElement 获取父元素节点

    重要: 创建元素 以及添加元素

    • document.createElement(‘标签名’) 创建元素

    • 父元素.appendChild(子元素) 追加元素

    • 父元素.insertBefore(要添加的子元素B,已有的子元素A) B元素要插入到A元素之前

    案例功能

    1. 动态添加 三步: 1.创建要添加的元素 2. 设置内容、样式、属性 3. 添加
    2. 非空判断 if判断输入框的值 === ’‘ 1.return 2. if- else
    3. 添加完成后清空 input.value = ‘’ 赋值

    单词

    • node 节点
    • type 类型
    • name 名称
    • value 值
    • child 孩子
    • first 第一个
    • last 最后一个
    • next 下一个
    • sibling 兄弟-同胞
    • previous 上一个
    • parent 双亲
    • element 元素
    展开全文
  • 双亲表示法采用注意,根节点没有父节点(父节点又称为双亲节点),因此根节点记录父节点位置的变量通常置为 -1。例如,采用双亲表示法存储图 1 中普通树,其存储状态如图 2 所示:图 2 双亲表示法存储普通树示意图图 2...
  • 树的双亲表示法

    千次阅读 2013-10-21 21:59:08
    树的双亲表示法是用一组连续空间(数组)存储树的节点,同时在每个节点中附设一个指示器指示其双亲节点在数组中的位置。 其结构如图:                   package tree; import java.util.*; ...
  • printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n"); #endif #ifdef INT printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n"); #endif CreateBiTree(&T)...
  • 树的双亲表示法,孩子表示法以及孩子兄弟表示法

    千次阅读 多人点赞 2020-06-12 14:43:11
    文章目录树的双亲表示法树的...注意,根节点没有父节点(父节点又称为双亲节点),因此根节点记录父节点位置的变量通常置为 -1。 /* * @Description: 树的双亲表示法 * @Version: V1.0 * @Autor: Carlos * @Date:
  • *建立双亲节点 *创建数据节点 *创建一维数组 *输入数据 *查找指定节点的双亲在数组中的位置 *返回指点节点的在数组中的位置 */ #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 //一维数组的...
  • 解法1:利用二叉树后序遍历非递归算法中,每一个叶子节点出现时,栈中从栈顶到栈底,正好是叶子节点到根节点的逆序的性质编写。[参考解答](btreee.h见算法库)#include #include "btree.h"void
  • 树的双亲存储:

    2019-09-17 03:26:47
    1.perface: 如下树结构: 若用树的双亲表示法,结果是:树的双亲表示: 0 1 A 2 B 1 ...
  • 此时要获取A的左子树中的最大值,首先分析最大值一定在左子树中的最右边,即B,这个最大值B也一定没有右孩子,那么我们只需要把A的右孩子的指向指向C即可,涉及到B双亲节点B的左孩子。 然后把得到的B节点返回...
  • 树的双亲存储

    2013-10-28 20:16:12
    若用树的双亲表示法,结果是:树的双亲表示: 0     1 A   2 B 1 3 C 1 4 D 2 5 E 2 6 F 2 7 G 3 8 H 5 9 I 5   2.code
  • 样例输入 A## A ABC#### B 样例输出 L:#,R:# L:C,R:# 1052: 输出利用先序遍历创建的二叉树中的指定结点的双亲结点 题目描述 利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点...
  • 求二叉树的双亲结点

    千次阅读 2020-07-08 20:53:22
    思路就是如果当前任一个孩子结点的值等于k,说明当前节点即为所需结点的双亲结点,通过递归实现唯一比较麻烦的是要写很多条件,不然会报错。 主要功能实现是preorder函数其他是构建和打印二叉树的函数。 #include<...
  • 二叉树的下一个节点

    2017-10-21 14:27:04
    [d,b,h,e,i,a,f,c,g] 观察二叉树的结构可知; 如果给定的节点有右子树,那么他的下一个节点是他的右子树的最左子节点 如果给定的节点没有右子树,如果他的节点是他父节点的左节点,那么他的下一个节点就是他的父...
  • 寻找二叉树双亲结点

    千次阅读 2020-02-25 16:53:00
    * @Issue: 寻找X结点的双亲结点 * @Author: 一届书生 * @LastEditTime: 2020-02-25 16:50:27 */ #include<iostream> using namespace std; #define type char typedef struct node{ type data; node ...
  • 题目描述 背景 大家都知道,sheep有两只可爱的宠物(一只叫神牛,一只叫神菜)。有一天,sheep带着两只宠物到狗狗家时,这两只可爱的宠物竟然迷路了...sheep的宠物非常笨,他们只会向前走,不会退后(只向双亲节点
  • 双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲; 兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点; 祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的...
  • 树-双亲表示法(含全部代码)

    千次阅读 多人点赞 2019-02-25 21:46:03
    T) 参数T,树根节点 作用:初始化树,先序递归创建 InsertNode(Tree &amp;T, TElemType node) 插入树的结点 参数:树T,结点node 作用:在双亲数组中插入结点,增加树的结点值 InsertParent(Tree &amp;T, ...
  • 注意看这个知识点需要有的树数据结构的基本知识,本文不贴实际代码只是讲解孩子...图的深入分析:这个树的根节点是字符A,他的孩子节点又 是3个子树,分别是根节点B,C,D组成。叶子节点也就是没有孩子了有C,F,H,I,J,K.
  • 从数据结构中树的定义可知,除根节点外,树中的每个节点都有唯一的一个双亲结点。根据这一特性,可用一组连续的存储空间(一维数组)存储树中的各节点。树中的结点除保存本身结点的信息外,还要保存其双亲结点在数组...
  • 提示:文章写完后,目录可以自动生成,如何...双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 根结点:一棵树中,没
  • 【算法导论】B

    千次阅读 2013-12-04 20:21:25
    1.每个节点x有一下域:(a)num,当前存储在节点x的关键字个数,关键字以非降序存放,因此key[i]  (b)isleaf,是一个bool值,如果x为叶子节点,则isleaf=true.  (c)每个节点包括num+1个指向其子女的指针p
  • 前面讲了二叉树的顺序存储和链式存储,本节来学习如何存储具有普通树结构的数据。 图1 普通树存储结构 如图 1 所示,这是一棵普通的树,该如何存储呢?...双亲表示法; 孩子表示法; 孩子兄弟表示法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,838
精华内容 4,735
关键字:

b是a双亲节点