妙趣横生的算法--二叉树-低调大师

妙趣横生的算法--二叉树

2017-09-30 644

基本

结点的度：结点拥有的子树的数目。

叶子：度为零的结点。

分支结点：度不为零的结点。

树的度：树中结点的最大的度。

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。

树的高度：树中结点的最大层次。

无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。

有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置。

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

性质

1：二叉树第i层上的结点数目最多为 2^{i-1}(i≥1)。

2：深度为k的二叉树至多有2^{k}-1个结点(k≥1)。

3：包含n个结点的二叉树的高度至少为log₂ (n+1)。

4：在任意一棵二叉树中，若终端结点的个数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

C实现

用先序序列创建一棵二叉树，并且输出字符D位于二叉树的层数。

#include "stdio.h"
#include "stdlib.h"

typedef struct BiTNode{
    char data;   /*结点的数据域*/
    struct BiTNode *lchild , *rchild;  /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
/*创建一棵二叉树*/
void CreatBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    if(c == ' ') *T = NULL;
    else{
       *T = (BiTNode * )malloc(sizeof(BiTNode));  /*创建根结点*/
        (*T)->data = c;    /*向根结点中输入数据*/
        CreatBiTree(&((*T)->lchild));  /*递归地创建左子树*/
        CreatBiTree(&((*T)->rchild));  /*递归地创建右子树*/
    }
}
/*访问二叉树结点，输出包含D字符结点位于二叉树中的层数*/
void visit(char c,int level){
     if(c == 'D')
        printf("%c is at %d lever of BiTree\n",c,level);
}
/*遍历二叉树*/
void PreOrderTraverse(BiTree T,int level){
    if(T){   /*递归结束条件，T为空*/
        visit(T->data,level);  /*访问根结点*/
        PreOrderTraverse(T->lchild,level+1);  /*先序遍历T的左子树*/
        PreOrderTraverse(T->rchild,level+1);  /*先序遍历T的右子数*/
    }
}

void main()
{
   int level = 1;
   BiTree T = NULL;  /*最开始T指向空*/
   CreatBiTree(&T);  /*创建二叉树*/
   PreOrderTraverse(T,level); /*遍历二叉树，找到包含D字符结点位于二叉树中的层数*/
}


本文转自我爱物联网博客园博客，原文链接：http://www.cnblogs.com/yydcdut/p/3678697.html如需转载请自行联系原作者

微信关注我们

原文链接：https://yq.aliyun.com/articles/357515

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

顺序查找 && 折半查找

顺序查找算法描述顺序比较即可。平均查找长度 (n+1)/2, 其中n为表长。时间复杂度 O(n) #include "stdio.h" typedef struct student{ int id; /*学生编号*/ char name[10]; /*学生姓名*/ float score; /*成绩*/ }Student; int search(Student stu[],int n,int key){ int i; for(i=0; i<n; i++) if( stu[i].id == key ) /*查找成功*/ return i; return -1; /*查找失败*/ } void main() { Student stu[4] = {{1004,"TOM",100} , {1002,"LILY",95}, {1001,"ANN",93}, {1003,"LUCY",98} }; /*初始化结构体数组*/ int addr; /*要查找的记录的地址*/ addr = search(stu,4,1003); printf("Student ID: %d\n",stu...

2017-09-30

733

懒汉，线程不安全 public class Singleton { private static Singleton instance; private Singleton (){} public static Singleton getInstance() { if (instance == null) { instance = new Singleton(); } return instance; } } 懒汉，线程安全 public class Singleton { private static Singleton instance; private Singleton (){} public static synchronized Singleton getInstance() { if (instance == null) { instance = new Singleton(); } return instance; } } 饿汉 public class Singleton { private static Singleton instance = new Single...

2017-09-30

721

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。