最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 树 二叉树 多叉树

    本文先介绍了树的概念,然后给出了2叉树和多叉树的实现源码实例。

    1、树的概念

    树(本质上就使用了递归来定义的,递归就是堆栈利用,因此树离不开递归和堆栈):树是n个点的有限结合。n=0时是空树,n=1时有且唯一1个结点叫做根,n>1,其余的结点被分成m个互不相交的子集,每个子集又是1棵树。

    森林

    2叉树

    满2叉树 深度为k,结点个数是2的k次方⑴的2叉树。
    完全2叉树 深度为k,结点为n,当且仅当每个结点的编号与对应的满2叉树完全1致。

    顺序存储:访问方便
    链式存储:删除方便

    2叉排序树:对每个结点的值都大于其左子结点,都小于其右子结点。

    遍历:将非线性结构通过线性的方式表访问。利用于不同需求。
    典型的有先生成2叉排序树,然后中序遍历,就实现了从小到达的输出。

    前序遍历:先打印,然后左递归,最后右递归。
    中序遍历:先左递归,然后打印,最后右递归。
    后序遍历:先左递归,然后右递归,最后打印。
    层次遍历:利用队列。左,右顺次放入队列。先左子出栈打印然后访问其子,如果存在左右顺次放入栈。然后右子出栈打印如果存在子,类推……

     

    2、2叉树

    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    //构造2叉树:左子树不大于根,右子树大于根。
    int constructTree(int data[],int num,int tree[])
    {
    tree[1] = data[1];
    for (int i=2;i<9;i++)
    {
    int j=1;
    while(tree[j]!=0)
    {
    if (data[i]<=tree[j])//下1级2的k次方⑴(从1开始)
    {
    j=j*2;
    }
    else
    {
    j=j*2+1;
    }
    }
    tree[j] = data[i];
    }
    for (int i=0;i<20;i++)
    {
    printf("%d ",tree[i]);
    }
    printf("
    ");
    return 0;
    }
    //遍历2叉树:递归
    //相对与根的位置,分为中序遍历,前序遍历,后序遍历。

    //后序遍历
    void ergodic1(int data[],int pos)
    {
    //不等于0也就是存在,那末就要寻觅左右
    if (data[pos*2]!=0)//左存在则遍历
    {
    printf("%d ",data[pos*2]);
    ergodic1(data,pos*2);
    }
    if (data[pos*2+1]!=0)//右存在则遍历
    {
    printf("%d ",data[pos*2+1]);
    ergodic1(data,pos*2+1);
    }
    }

    //中序遍历
    void ergodic2(int data[],int pos)
    {

    //不等于0也就是存在,那末就要寻觅左右
    if (data[pos*2]!=0)//左存在则遍历
    {
    ergodic2(data,pos*2);
    }
    if (data[pos]!=0)
    {
    printf("%d ",data[pos]);
    }
    if (data[pos*2+1]!=0)//右存在则遍历
    {
    ergodic2(data,pos*2+1);
    }
    }
    //后序遍历
    void ergodic3(int data[],int pos)
    {
    //不等于0也就是存在,那末就要寻觅左右
    if (data[pos*2]!=0)//左存在则遍历
    {
    ergodic3(data,pos*2);
    printf("%d ",data[pos*2]);
    }
    if (data[pos*2+1]!=0)//右存在则遍历
    {
    ergodic3(data,pos*2+1);
    printf("%d ",data[pos*2+1]);
    }
    }

    int main()
    {
    int data[100] = {0,6,3,9,2,5,7,8,4,2};
    int num = 9;
    int tree[100] = {0};
    constructTree(data,num,tree);

    ergodic1(tree,0);
    printf("
    ");
    ergodic2(tree,0);
    printf("
    ");
    ergodic3(tree,0);
    printf("
    ");
    }

     

    3、多叉树-寻觅共同的先人

    //寻觅共同的先人

    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    typedef struct ST_TREE TREE;
    struct ST_TREE {
    int deep;
    char name[200];
    int nextNum;
    int next[200];
    TREE *father;
    };
    void tree_init(TREE *tree)
    {
    tree->deep = 0;//头结点
    memset(tree->name,0,200);
    tree->nextNum = 0;
    memset(tree->next,0,200);
    tree->father = NULL;
    }

    void tree_insert(TREE *tree0,TREE *tree)
    {
    tree->father = tree0;
    tree->deep = tree0->deep+1;
    tree0->next[tree0->nextNum++]=(int)tree;
    }
    // TREE *tree_getChild(TREE *tree0,int no)
    // {
    // return (TREE *)tree0->next[no];
    // }

    //单独设立头结点
    TREE header;

    TREE *getChild(TREE *father,char *name)
    {

    TREE *current = father;
    if (strcmp(name,"")==0)
    {
    return current;
    }
    //特别注意在递归的进程中,不能混淆不同层变量的值。此处不管current怎样变,每次循环都要来源于原来的current,也就是后来的f
    int num = current->nextNum;
    TREE *f = current;
    for (int i=0;i<num;i++)
    {
    current = (TREE *)f->next[i];
    if (strcmp(name,current->name)==0)
    {
    return current;
    }
    else
    {
    TREE *c = getChild(current,name);
    if (c)
    {
    return c;
    }
    }
    }
    return NULL;
    }

    void insertPC(char *fatherName,char *sonName)
    {
    TREE *f = getChild(&header,fatherName);
    if(f)
    {
    TREE *son = (TREE *)malloc(sizeof(TREE));
    tree_init(son);
    strcat(son->name,sonName);
    tree_insert(f,son);
    }
    else
    {
    insertPC("",fatherName);//插入头结点
    insertPC(fatherName,sonName);
    }
    }

    //寻觅共同的先人:比较深度
    TREE *getAncestor(char *a,char *b)
    {
    TREE *aTree = getChild(&header,a);
    TREE *bTree = getChild(&header,b);
    while(true)
    {
    if (aTree->father==NULL || bTree->father==NULL)
    {
    break;
    }
    // if (strcmp(aTree->name,"")==0 || strcmp(aTree->name,"")==0)
    // {
    // break;
    // }
    if(aTree->deep>bTree->deep)
    {
    aTree = aTree->father;
    }
    else if(bTree->deep>aTree->deep)
    {
    bTree = bTree->father;
    }
    else
    {
    if (strcmp(aTree->father->name,bTree->father->name)!=0)
    {
    aTree = aTree->father;
    bTree = bTree->father;
    }
    else
    {
    return aTree->father;
    }
    }
    }
    return NULL;
    }

    int main(void)
    {
    tree_init(&header);
    insertPC("a","b");
    insertPC("b","d");
    insertPC("a","c");
    insertPC("c","e");
    insertPC("e","f");

    // TREE *t = getChild(&header,"f");
    // printf("%s",t->name);

    TREE *ancestor = getAncestor("d","f");
    printf("%s",ancestor->name);

    return 0;
    }

     

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 树 二叉树 多叉树

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级