精华内容
下载资源
问答
  • * 求二叉树中的结点个、叶子结点个、某结点层次和二叉树宽度 * 实验目的: * 掌握二叉树遍历算法的应用,熟练使用先序、中序、后序三种递归 * 遍历算法和层次遍历算法进行二叉树问题求解。 * 实验内容: * 设计...

    /**
    *    实验题目:
    *        求二叉树中的结点个数、叶子结点个数、某结点层次和二叉树宽度
    *    实验目的:
    *        掌握二叉树遍历算法的应用,熟练使用先序、中序、后序三种递归
    *    遍历算法和层次遍历算法进行二叉树问题求解。
    *    实验内容:
    *        设计程序,实现如下功能:
    *    1、输出二叉树b的结点个数
    *    2、输出二叉树b的叶子结点个数
    *    3、求二叉树b中指定结点值的结点的层次
    *    4、利用层次遍历求二叉树b的宽度
    */

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

    #define MAX_SIZE 100

    typedef char ElemType;
    typedef struct node
    {
        ElemType data; // 数据元素
        struct node *lchild; // 指向左孩子结点
        struct node *rchild; // 指向右孩子结点
    }BTNode; // 声明二叉链结点类型

    /*-------------由括号表示串str创建二叉链b-----------------*/
    static void create_btree(BTNode *&b, char *str) // 创建二叉树(形参b:指针的引用)
    {
        BTNode *p;
        BTNode *St[MAX_SIZE]; // 定义一个顺序栈
        int k;
        int j = 0;
        int top = -1; // 栈顶指针初始化
        char ch;

        b = NULL; // 建立的二叉树初始时为空
        ch = str[j]; // 取第一个字符
        while(ch != '\0') // str未扫描完时循环
        {
            switch(ch)
            {
            case '(': // 开始处理左子树
                top++;
                St[top] = p;
                k = 1;
                break;
            case ')': // 子树处理完毕
                top--;
                break;
            case ',': // 开始处理右子树
                k = 2;
                break;
            default:
                p = (BTNode *)malloc(sizeof(BTNode)); // 动态分配结点p的存储空间
                p->data = ch;
                p->lchild = p->rchild = NULL;
                if(b == NULL) // 若b为空,p置为二叉树的根结点
                    b = p;
                else // 已建立二叉树根结点
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild = p;
                        break;
                    case 2:
                        St[top]->rchild = p;
                        break;
                    }
                }
                break;
            }
            // 取下一个字符
            j++;
            ch = str[j];
        }
    }

    /*--------------------------以括号表示法输出二叉树b----------------------*/
    // "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
    static void disp_btree(BTNode *b)
    {
        if(b != NULL)
        {
            printf("%c", b->data);
            if(b->lchild != NULL || b->rchild != NULL)
            {
                printf("("); // 有孩子结点时才输出(
                disp_btree(b->lchild); // 递归处理左子树
                if(b->rchild != NULL) // 有右孩子结点时才输出,
                    printf(",");
                disp_btree(b->rchild); // 递归处理右子树
                printf(")"); // 有孩子结点时才输出)
            }
        }
    }

    /*--------------------------释放二叉树b的所有结点----------------------*/
    static void destroy_btree(BTNode *&b) // 销毁二叉树(形参b:指针的引用)
    {
        if(b != NULL)
        {
            destroy_btree(b->lchild);
            destroy_btree(b->rchild);
            free(b);
        }
    }

    /*--------------------------返回b结点的左孩子结点指针----------------------*/
    static inline BTNode *left_child_node(BTNode *b)
    {
        return b->lchild;
    }

    /*--------------------------返回b结点的右孩子结点指针----------------------*/
    static inline BTNode *right_child_node(BTNode *b)
    {
        return b->rchild;
    }

    /*--------------------------返回data域为x的结点指针----------------------*/
    static BTNode *find_node(BTNode *b, ElemType x) // 查找值为x的结点
    {
        BTNode *p;

        if(b == NULL)
            return NULL;
        else if(b->data == x)
            return b;
        else
        {
            p = find_node(b->lchild, x);
            if(p != NULL)
                return p;
            else
                return find_node(b->rchild, x);
        }
    }

    /*--------------------------求二叉树b的深度----------------------*/
    static int btree_height(BTNode *b)
    {
        int left_child_height, right_child_height;

        if(b == NULL) // 空树的深度为0
            return 0;
        else
        {
            // 求左子树的深度
            left_child_height = btree_height(b->lchild);
            // 求右子树的深度
            right_child_height = btree_height(b->rchild);

            return (left_child_height > right_child_height) ? (left_child_height + 1) : (right_child_height + 1);
        }
    }

    /*--------------------------求二叉树b的结点个数----------------------*/
    static int btree_nodes(BTNode *b)
    {
        int num1;
        int num2;

        if(b == NULL)
            return 0;
        else if(b->lchild == NULL && b->rchild == NULL)
            return 1;
        else
        {
            num1 = btree_nodes(b->lchild);
            num2 = btree_nodes(b->rchild);

            return (num1 + num2 + 1);
        }
    }

    /*--------------------------求二叉树b的叶子结点个数----------------------*/
    static int btree_leaf_nodes(BTNode *b)
    {
        int num1;
        int num2;

        if(b == NULL)
            return 0;
        else if(b->lchild == NULL && b->rchild == NULL)
            return 1;
        else
        {
            num1 = btree_leaf_nodes(b->lchild);
            num2 = btree_leaf_nodes(b->rchild);

            return (num1 + num2);
        }
    }

    /*--------------------------求二叉树b中结点值为x的结点的层次----------------------*/
    static int btree_node_level(BTNode *b, ElemType x, int h)
    {
        int level;

        if(b == NULL)
            return 0;
        else if(b->data == x)
            return h;
        else
        {
            level = btree_node_level(b->lchild, x, h + 1); // 在左子树中查找
            if(level != 0)
                return level;
            else // 在左子树中未找到,再在右子树中查找
                return btree_node_level(b->rchild, x, h + 1);
        }
    }

    /*--------------------------求二叉树b的宽度----------------------*/
    static int btree_width(BTNode *b)
    {
        struct
        {
            int level; // 结点的层次
            BTNode *p; // 结点指针
        }que[MAX_SIZE]; // 定义非环形队列
        int que_front, que_rear; // 定义队头、队尾指针
        int index;
        int same_level_node_nums; // 同一层结点个数
        int level; // 结点的层次
        int width; // 树的宽度

        que_front = que_rear = 0; // 置队列为空队
        if(b != NULL)
        {
            que_rear++; // 队尾指针增1
            que[que_rear].p = b; // 根结点进队
            que[que_rear].level = 1; // 根结点的层次为1
            while(que_rear != que_front) // 队列不为空时循环
            {
                que_front++;
                b = que[que_front].p; // 出队结点b
                level = que[que_front].level;
                printf("入队结点%c的层次:%d\n", b->data, level);
                if(b->lchild != NULL) // 有左孩子,将其进队
                {
                    que_rear++;
                    que[que_rear].p = b->lchild;
                    que[que_rear].level = level + 1;
                }
                if(b->rchild != NULL) // 有右孩子,将其进队
                {
                    que_rear++;
                    que[que_rear].p = b->rchild;
                    que[que_rear].level = level + 1;
                }
            }
            printf("入队完成时,que_rear = %d\n", que_rear);
            width = 0; // 存放宽度
            level = 1;
            index = 1;
            while(index < que_rear)
            {
                same_level_node_nums = 0;
                while(index < que_rear && que[index].level == level)
                {
                    same_level_node_nums++; // same_level_node_nums累计一层中的结点个数
                    index++; // index扫描队列中所有结点
                }
                level = que[index].level;
                if(same_level_node_nums > width)
                {
                    width = same_level_node_nums;
                }
            }
            return width;
        }
        else
            return 0;
    }

    int main(void)
    {
        ElemType x = 'A';
        BTNode *b;

        create_btree(b, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
        printf("输出二叉树b:");
        disp_btree(b);
        printf("\n");
        printf("二叉树b的结点个数:%d\n", btree_nodes(b));
        printf("二叉树b的叶子结点个数:%d\n", btree_leaf_nodes(b));
        printf("二叉树b中值为%c结点的层次:%d\n", x, btree_node_level(b, x, 1));
        printf("二叉树b的宽度:%d\n", btree_width(b));
        destroy_btree(b);

        return 0;
    }
    测试结果:

    输出二叉树b:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
    二叉树b的结点个数:14
    二叉树b的叶子结点个数:6
    二叉树b中值为A结点的层次:1
    入队结点A的层次:1
    入队结点B的层次:2
    入队结点C的层次:2
    入队结点D的层次:3
    入队结点E的层次:3
    入队结点F的层次:3
    入队结点G的层次:3
    入队结点H的层次:4
    入队结点I的层次:4
    入队结点J的层次:5
    入队结点K的层次:5
    入队结点L的层次:6
    入队结点M的层次:6
    入队结点N的层次:7
    入队完成时,que_rear = 14
    二叉树b的宽度:4

    展开全文
  • 结点及其所在层次

    千次阅读 2019-10-30 20:00:16
    题目描述 从键盘接收扩展先序序列,...data是二叉树结点数据域值,level是该结点所在的层次。 设根节点在第一。 输出的元素间不用间隔,()都是英文字符 样例输入 Copy AB#DG###CE##FH### 样例输出 Copy (A,1)(...

    题目描述

    从键盘接收扩展先序序列,以二叉链表作为存储结构,建立二叉树。按先序遍历次序输出各结点的内容及相应的层次数,要求以二元组的形式输出,其所对应的输出结果为:(data,level)
    data是二叉树结点数据域值,level是该结点所在的层次。
    设根节点在第一层。
    输出的元素间不用间隔,()都是英文字符

    样例输入 Copy

    AB#DG###CE##FH###
    

    样例输出 Copy

    (A,1)(B,2)(D,3)(G,4)(C,2)(E,3)(F,3)(H,4)
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef struct Node{
        char data;
        struct Node* Lchild;
        struct Node* Rchild;
    }BiTNode, *BiTree;
    void PreOrder(BiTree root, int n)
    {
    
        if(root)
        {
            printf("(%c,%d)", root->data, n);
            PreOrder(root->Lchild, n+1);
            PreOrder(root->Rchild, n+1);
        }
    }
    
    void CreateBiTree(BiTree *root)
    {
        char ch;
        ch = getchar();
        if(ch == '#')
            *root = NULL;
        else
        {
            (*root) = (BiTree)malloc(sizeof(BiTNode));
            (*root)->data = ch;
            CreateBiTree(&((*root)->Lchild));
            CreateBiTree(&((*root)->Rchild));
        }
    }
    int main()
    {
        BiTree root;
        CreateBiTree(&root);
        PreOrder(root, 1);
        return 0;
    }
    
    
    展开全文
  • 层次 宽度 深度 高度 其中只有层次是树原生的概念,其他都是从树中的结点来的。 层次 从根节点开始算起,根节点算第一。如图所示的树 第1:A 第2:B,C 第3:D,E,F 第4:G,H,I 宽度 其实就是...

    目录

    层次

    宽度

    深度

    高度

    其中只有层次是树原生的概念,其他都是从树中的结点来的。

    层次

    从根节点开始算起,根节点算第一层。如图所示的树

    第1层:A

    第2层:B,C

    第3层:D,E,F

    第4层:G,H,I

    宽度

    其实就是度,把结点的子树的棵树称为结点的度,树的度是树中度最大的结点的度。

    如图所示的树度取决于结点D的度,为3。

    思考:二叉树==度为2的树?

    非也,二叉树的子树区分左子树和右子树,且二叉树的度未必为2。

    深度

    结点的深度指从根节点(度为1)自顶向下逐层累加至该结点时的深度。树的深度是树中深度最大的结点的深度。

    高度

    结点的高度指从该结点最底层的叶子节点(度为1)出发,自底向上逐层累加至该结点时的高度。树的高度是树中高度最大的结点的高度。

    对于一个结点来说,高度未必等于深度,对于一棵树来说,高度等于深度。

    展开全文
  • 但是按层次建立二叉树长的像什么呢?。。。答对了,当然是像bfs广度优先搜索啦。 下面的代码是:先给一个n,代表这棵树上有多少个节点。然后呢输入节点的值,节点的值位‘0’,说明这个节点位虚节点(就是...

    大家熟悉的二叉树建立都是按先序的顺序建立的,就是输入的节点值是先左子树作为根建到头,然后右子树作为根建到头。这样出来的代码就是递归建立。看着是不是特别想dfs深度优先搜索的说。但是按层次建立二叉树长的像什么呢?。。。答对了偷笑,当然是像bfs广度优先搜索啦。


    下面的代码是:先给一个数n,代表这棵树上有多少个节点。然后呢输入节点的值,节点的值位‘0’,说明这个节点位虚节点(就是实际上没有这个节点)。注意:当父亲是‘0’的时候,肯定他就不需要输入左右子树的值了啊,因为如果链表的话那个节点都NULL了,又怎么可能会连接上新的链表呢!


    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    #include <malloc.h>-
    #include <queue>
    #include <math.h>
    #include <map>
    using namespace std;
    
    typedef struct Node
    {
        char data;
        struct Node *left, *right;
    }sn,*ssn;
    queue<ssn> que;
    int n;
    ssn create_tree()
    {
        int tn = n;
        char ch, ch1, ch2;  ///根节点字符,左右字符
        ssn t, p, q;    ///链表
        ch = getchar();
        if (ch != '0')
        {
            p = (ssn)malloc(sizeof(sn));
            p -> data = ch;
            que.push(p);
            tn--;
        }
        else
        return NULL; ///根就是0还扯啥
        while (!que.empty()) ///开始按成次建树
        {
            t = que.front();
            que.pop();
            if (tn == 0) break;
            getchar();
            ch1 = getchar(); 
            if (ch1 != '0')
            {
                q = (ssn)malloc(sizeof(sn));
                q -> data = ch1;
                t -> left = q;  ///也就是根的左子树是q
    
                que.push(q);
                tn--;
            }
            else t->left = NULL; ///否则跟的左子树空
            getchar();
            ch2 = getchar();
            if (ch2 != '0')
            {
                q = (ssn)malloc(sizeof(sn));
                q -> data = ch2;
                t -> right = q;
                que.push(q);
                tn--;
            }
            else t->right = NULL;
        }
        return p;
    }
    
    void query(ssn tt, int tn)
    {
        ssn t, q;
        while(que.size())
        que.pop();
    
        que.push(tt);
        t = que.front();
        printf("%2c", t->data);
        tn--;
       while (!que.empty())
        {
            t = que.front();
            que.pop();
            if (tn == 0) break;
            if (t -> left)
            {
                q = (ssn)malloc(sizeof(sn));
                q = t -> left;
                printf("%2c", q->data);
                que.push(q);
                tn--;
            }
            else printf(" NULL");       ///有的题问你有多少叶子
            if (t -> right)
            {
                q = (ssn)malloc(sizeof(sn));
                q = t -> right;
                printf("%2c", q->data);
                que.push(q);
                tn--;
            }
            else printf(" NULL");   ///如果上边那个和这个都是NULL,那他们的父亲就是叶子呗
            ///最后计算总的叶子时候别忘了加上最后一层的不为NULL值的节点(为什么:因为是最后一层)
            ///判断是否是最后一层就在“tn--;”的上边判断tn是不是1就行了
        }
    }
    
    int main()
    {
        ssn t, tl, tr;
        while (scanf("%d", &n) == 1)
        {
            getchar();
            t = create_tree();
            query(t, n);
        }
        return 0;
    }
    


    展开全文
  • Python:层次聚类分析

    千次阅读 2018-06-01 14:55:54
    linkage函数从字面意思是链接,层次分析就是不断链接的过程,最终从n条数据,经过不断链接,最终聚合成一类,算法就此停止。 dendrogram是用来绘制树形图的函数。 from scipy.cluster.hierarchy import linkage,...
  • 数据结构——二叉树的结点的层次

    千次阅读 2018-11-21 18:45:30
    二叉树结点的层次 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; typedef struct Node{ //二叉树的链式存储结点 char data; int depth; struct Node *...
  • 聚类算法(4)--Hierarchical clustering层次聚类

    万次阅读 多人点赞 2018-11-07 17:45:47
    一、层次聚类 1、层次聚类的原理及分类 2、层次聚类的流程 3、层次聚类的优缺点 二、python实现 1、sklearn实现 2、scipy实现 树状图分类判断 一、层次聚类 1、层次聚类的原理及分类 1)层次法...
  • PCB的层数怎么看?

    千次阅读 2020-02-18 10:33:00
    1、目测法 由于PCB中的各层都紧密的结合,...因为目前的多层PCB板都用上了更多单或双面的布线板,并在每层板间放进一层绝缘层后压合,PCB板的层数就代表了有几层独立的布线层,而层与层之间的绝缘层就成为了我们用...
  • 【Scratch-外观模块】层次指令

    千次阅读 2020-06-05 09:58:23
    Scratch层次指令 指令解析 移到最前面/后面:是将角色移动到所有角色的最前面,以及除舞台背景外的最后面 前移/后移XX:是将角色像前/后移动具体的XX 比如我这边角色总共有4个,小猫是在最后面一,如果我...
  • 1.依据构造原理中的排布顺序,其实质是各能级的能量高低顺序,可由...(3)倒数第三由(n-2)s(n-2)p(n-2)d(n-2)f组成,电子不大于2+6+10+14=32。补充:基态原子的核外电子排布规律包括以下三条原则:(1)...
  • 原文链接:网络层次划分及网络协议 1 OSI七模型、TCP/IP四模型、TCP/IP五模型 不管是OSI七模型还是TCP/IP的四、五模型,每一中都要自己的专属协议,完成自己相应的工作以及与上下层级之间进行沟通。 ...
  • R语言-层次聚类的初步了解

    万次阅读 2018-07-31 14:40:57
    当需要嵌套聚类有意义的层次结构时,层次聚类可发挥奇效,(生物科学中这种情况就很常见),缺点是层次聚类中一旦一个观测值被划分到一个类,它就不能再重新分配。层次聚类难以应用到百甚至千观测值的大样本中...
  • 小白都能了解的聚类算法之三(层次聚类)

    千次阅读 多人点赞 2020-03-29 12:07:22
    1.简介 层次聚类(Hierarchical Clustering)通过计算各类别中数据之间的相似度,最终创建一棵有...自底向上聚合(agglomerative)策略自顶向下分拆(divisive)策略是层次聚类中常见的两种划分策略。 算法的基本步...
  •  聚合层次聚类是一种自下而上的算法,首先将每个样本都视为一个簇,然后开始按一定规则,将相似度高的簇进行合并,最后所有样本都形成一个簇或达到某一个条件时,算法结束。  确定簇与簇之间相似度是该算法的要点...
  • R语言 : 层次聚类分析

    千次阅读 2017-08-19 21:09:42
    R语言 层次聚类分析 双色球
  • 1. 层次聚类 1.1 层次聚类的原理及分类 1)层次法(Hierarchicalmethods):先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。不停的合并...
  • 帆软层次坐标常用公式整理

    千次阅读 2018-05-23 15:53:07
    1.1在C3(占比)单元格中直接使用占比公式:=PROPORTION(B3);占比:当前值占总值的比例 1.2 计组内占比注:C2[!... 层次坐标条件写法B2[!0]{A2=$A2} 表示b2按相同的单元条件扩展出来的的单元格 2...
  • 关于产品层次

    千次阅读 2013-12-26 23:54:10
    产品层次,系统里默认是3,但实际系统支持9,最多18位。 In the standard system,the product hierarchy consists of up to 3 levels. The first and second levelshave 5 digits and the third level has 8. ...
  • MATLAB中zeros表示表示什么意思发表时间:2019-12-26 10:20:18小编:4326手游网阅读:在手机上看手机扫描阅读MATLAB中zeros表示表示什么意思[展开/闭合]zeros功能是返回一个m×n×p×...的double类零矩阵的一个函数...
  • 二叉树的层次遍历(分层输出)

    千次阅读 2020-10-27 15:59:40
    题目描述   给定一个二叉树,返回...要区分每一节点的个数,可以考虑每次访问时,访问同一的所有元素,将下一的所有元素放入队列(使用 size 函数来计算一节点) 程序设计 /** * struct TreeNode { * i
  • 二叉树的层次遍历 二叉树的层次遍历即从上往下、从左至右依次打印树的节点。 其思路就是将二叉树的节点加入队列,出队的同时将其非空左右孩子依次入队,出对到队列为空即完成遍历。 # -*- coding:utf-8 -*- # ...
  • 聚类属于无监督学习,其中聚类的方法有很多种常见的有K-means、层次聚类(Hierarchical clustering)、谱聚类(Spectral Clustering)等,在这里,上来不会直接介绍这些理论,需要一些基础知识铺垫,前面一样,一...
  • 聚类分析常用算法原理:KMeans,DBSCAN, 层次聚类

    万次阅读 多人点赞 2018-01-01 10:52:32
    聚类分析是非监督学习的很重要的领域。所谓非监督学习,就是数据是没有类别标记的,算法要从对原始数据的探索...KMeansKMeans算法在给定一个k之后,能够将数据集分成k个“簇”C={C1,C2,⋯,Ck}\mathcal C = \{C_1, C_2
  • R语言 层次聚类(系统聚类)

    千次阅读 2018-03-20 21:25:37
    层次聚类试图在不同层次对数据集进行划分 library(NbClust) data(nutrient, package = 'flexclust') row.names(nutrient) (row.names(nutrient)) nutrient.scale (nutrient) d (nutrient.scale)
  • 不同平均的比较;图片来源:维基百科 大概是最常见的数据分析任务 ...意思是:没有可以恰当地称作“平均”的数学运算。我们通常所说的平均是“算术平均”,具体计算过程如前所述。我们称其为...
  • 引入Hierarchical Clustering背景:k-means算法却是一种方便好用的聚类算法,但是始终有K值选择初始聚类中心点选择的问题,而这些问题也会影响聚类的效果...1.1Hierarchical Clustering:一如其字面意思,是层次化...
  • 文章目录一、前言2、自底向上的层次算法python实现层次聚类4、使用Sklearn中的层次聚类5、使用Scipy库中的层次聚类(1)linkage(y, method=’single’, metric=’euclidean’)(2).fcluster(Z, t, criterion=’...
  • 编写按层次顺序(同一自左至右)遍历二叉树的算法。二叉链表类型定义:[cpp] view plain copy typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { T...
  • 深度学习中的隐藏是干什么的?

    万次阅读 多人点赞 2019-07-25 21:34:26
    隐藏的意义 要说明隐藏的意义,需要从两个方面理解,一个是单个隐藏的意义,一个是多层隐藏的意义。 单个隐藏的意义 隐藏的意义就是把输入数据的特征,抽象到另一个维度空间,来展现其更抽象化的特征...
  • 层次聚类的Matlab实现代码

    万次阅读 多人点赞 2015-06-09 15:44:45
    最近需要用到层次聚类,发现在Matlab上很容易实现,下面是代码加详细注释 clear all clc close all mdist=input('输入坐标文件名字\n'); disp('读取数据坐标') %获取坐标 %文件为二维的坐标,第一列为x轴坐标,第...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 85,160
精华内容 34,064
关键字:

层数和层次是什么意思