二叉树的建立与遍历

为什么学二叉树?因为计算机二级会涉及到一部分知识。在模拟考试的时候看到就直接跳过去了,心塞。终于花时间在网上找了源码好好看了一下也懂了个一二三。搜的时候是简单二叉树建立与遍历,所以自己学的不深,但是我感觉应付计算机二级也是够了。计算机二级主要还是主要以选择题出,所以基本知识点还是有必要了解的。
本次参考文章讲解:点击访问(本文章代码几乎和原文相同)
本文基本知识点参考于:未来教育二级C

计算机二级主要还是主要以选择题出,所以基本知识点还是有必要了解的。

树的基本

树(Tree)是简单的非线性结构。样子基本长这样

百度图
百度图

关键词:

父节点:例如A就是父节点(根节点),在它没有前件(也就是它之上没有连接它的了,它是开头)。

子节点:B、C、D就是子节点,有上一个点连接它,它同时还连接下面的点。

叶节点:E、F、G、H、I、J是叶节点,上面有连接它的,但是它没有连接下面的。

度:简单而言就是它所连接下面的个数,例如A连接B、C、D,A的度就是3个,B连接E、F、G度也是3个,C连接一个H,所以C的度是1个。对于这一个树而言度的大小取决于所有节点中最大的度,A的度是3,B的度是3,C的度是1,D的度是2,所以取最大就是3,因此数的度是3。

深度:也就是有多少层数,A在1层,B、C、D在2层,E、F、G、H、I、J第三层。下面就没了,所以深度是数的最大深度为3。

子树:一个子节点可以看成一个根节点连接到下面,例如B连接下面E、F、G可以称为树,而又因为A在B上连接它,所以称为子树。(其实也可以把叶节点称为子树,只是没有连接其他节点而已,只有根节点一个节点。)

小结论:树的节点数等于数中所有节点的度之和加上1。(理解:度就是上节点下面连接的节点,A连接3个,B连接3个,E连接0个等等以此类推,加起来正好是除了A之外的所有节点之和,再加上A这1个,所以就是所有节点数。)

二叉树及其基本性质

二叉树:可以看成树只能最多连接下面的两个节点的数。
二叉树在计算机中储存通常采用链式储存结构,储存单元里要有左指针域,右指针域和数据。例如下面结构体代码:

struct code
{
    struct code *left;
    struct code *right;
    int data;
};

二叉树的链式储存结构也称为二叉链表。

二叉树的特点

1.二叉树可以为空,空的二叉树没有节点,非空的二叉树有且只有一个根节点。

2.每个节点最多同时连接下面的两个节点,即二叉树中不存在度大于2的节点。

3.二叉树的子树有左右之分,其次序不能任意颠倒。(关键)

二叉树的性质

1:在二叉树的第k层上,最多有2^(k-1)(k≥1)个节点。

2:深度为m的二叉树中,最多有(2^m)-1个节点。

3:对任何一棵二叉树,度为0的节点(即叶子节点)总是比度为2的节点多一个。(选择题出现过相关计算题)

4:具有n个节点的二叉树,其深度至少为[log(2)(n)]+1,其中[log(2)(n)]表示取log(2)(n)的整数部分。
(第一个括号为底,第二个为括号为真数)

5.具有n个节点的完全二叉树的深度为[log(2)(n)]+1。

满二叉树和完全二叉树

满二叉树:除了最后一层,每一层上的所有节点都有两个节点,第k层有2^(k-1)(k≥1)个节点,深度为m有(2^m)-1个节点。

满二叉树
满二叉树

完全二叉树:除最后一层外,每一程上的节点数均达到最大值,在最后一层上只缺少右边若干节点的二叉树。
完全二叉树
完全二叉树

二叉树建立与遍历

首先先了解一下遍历 分为前序遍历(DLR),中序遍历(LDR),后序遍历(LRD)三种不同
我们以上图完全二叉树图为例:
前序遍历是: 1 2 4 8 9 5 10 3 6 7
中序遍历是: 8 4 9 2 10 5 1 6 3 7
后序遍历是: 8 9 4 10 5 2 6 7 3 1

前序遍历方法:从根开始先顺着左面的数一直走,就是1 2 4 8,之后8下面没了,退到4子树上看到4右节点有数,就把它读出来 就变成了1 2 4 8 9。之后4节点也没了,退到2节点,右节点有数 就往下走到10节点停了,在退回5节点,5右节点没数,之后退回到2节点,2节点没了,退到1节点,此时是1 2 4 8 9 5 10。之后1节点右节点有3,之后从3走到6 此时为 1 2 4 8 9 5 10 3 6,之后6节点下无节点,退回到3,3节点有右节点7,读出7.7下面无节点,退回到3,3节点左右都读完了。返回到1,1左右节点读完了,所以就结束了。

中序遍历方法:从左至右看(将所有节点降到8,9,10这一条线上),8和9之间是4 9和10之间是2 10和1之间是1 1和3之间是6,6和7是3。

后序遍历方法:先读子树左右节点的值,之后在读父节点(依然先左后右)。从1出发一直到8(只要有左右节点那么就不读出根节点的数),8无左右节点,之后读取4的右节点9,4的左右节点读取完毕,然后读取4,此时为8 9 4.之后退到2,之后开始读2的右节点5,之后退到2,在读取2节点。此时为8 9 4 10 5 2。之后2节点完毕后退到1,之后开始读1节点的右节点,一直到6,6节点读完退到3节点,在读3节点的右节点7,7读完退到3,在读取3节点,此时为8 9 4 10 5 2 6 7 3。之后退到1,1左右节点读取完毕,在读取1,结束。此时为8 9 4 10 5 2 6 7 3 1

如何遍历懂了之后,创建就从代码中学习。如果有疑问代码我自己遇到的疑问和解答。
(手机上代码显示不全?请更换浏览器或使用电脑查看)

#include<stdio.h>
#include<stdlib.h>
typedef struct code
{
    struct code *left;
    struct code *right;
    int data;
}code,*coder;
void bitree(coder &t)//指针的引用法
{
    t =(code*) malloc (sizeof(code));
    printf("Enter the data \n");
        scanf(" %d",&t->data);
        if(t->data==0) t = NULL;
        if(t){
                bitree(t->left);
               bitree(t->right);
        }
}
void bitree1(code **t)//指针的指针法
{
    *t =(code*) malloc (sizeof(code));
    printf("Enter the data \n");
        scanf(" %d",&(*t)->data);
        if((*t)->data==0) *t = NULL;
        if(*t){
                bitree1(&(*t)->left);
               bitree1(&(*t)->right);
        }
}
void dlr(coder t)//前序遍历
{
   if (t) {
      printf(" %d\n",t->data);   // 访问根结点
      dlr(t->left); // 遍历左子树
      dlr(t->right);// 遍历右子树
   }
}
void ldr(coder t)//中序遍历
{
   if (t) {
      ldr(t->left); // 遍历左子树
      printf(" %d\n",t->data);   // 访问根结点
      ldr(t->right);// 遍历右子树
   }
}
void lrd(coder t)//后序遍历
{
   if (t) {
       
       lrd(t->left); // 遍历左子树
       lrd(t->right);// 遍历右子树
      printf(" %d\n",t->data);   // 访问根结点
   }
}
int depth(coder t)//二叉树深度
{
    int left=0;
    int right=0;
    if(t)
    {
        left=1+depth(t->left);
        right=1+depth(t->right);
        return left>right?left:right;
    }
    return 0;
}
void main()
{
    coder t;
    code *t1;
    bitree(t);
    //bitree1(&t1);
    printf("\n");
    printf("先序遍历二叉树.\n");
    dlr(t);
     printf("中序遍历二叉树.\n");
    ldr(t);
     printf("后序遍历二叉树.\n");
    lrd(t);
     printf("\n深度为%d",depth(t));
}

首先先从结构体开始解释:

typedef struct code
{
    struct code *left;
    struct code *right;
    int data;
}code,*coder;

typedef struct code{} code,*coder;这段意思是给struct code这个类型起个别名叫code和 *coder(这是指针形式);于结构体声明结构体变量不同。

在下面代码中我用了两种方式进行二叉树的建立,代码大致相同,主要是传递的参数不同。在看讲解的时候自己就有个疑问:为什么直接传递地址不行?而要采用传递地址的地址的方案?
后来想了想应该是这样:如果直接传递地址bitree(t)的话,在创建二叉树的void bitree(coder t1),此时t1是形参和t的地址相同,但是在函数中改变了t1的地址,但是这不会让t的地址修改。这就相当于

#include<stdio.h>
void max(int t)
{
    t=2;
    printf("max中的%d\n",t);
}
void main()
{
    int t=1;
    max(t);
    printf("mian中的%d\n",t);
}

虽然改变了t1的地址,但是并没有对t的地址改变。
因此要改变t的地址就需要传递地址的地址,就是t的地址来修改t。或者采用引用的方法,因为引用就相当于是个别名,修改全部同步。

void bitree(coder &t)//指针的引用法
{
    t =(code*) malloc (sizeof(code));
    printf("Enter the data \n");
        scanf(" %d",&t->data);
        if(t->data==0) t = NULL;
        if(t){
                bitree(t->left);
               bitree(t->right);
        }
}
void bitree1(code **t)//指针的指针法
{
    *t =(code*) malloc (sizeof(code));
    printf("Enter the data \n");
        scanf(" %d",&(*t)->data);
        if((*t)->data==0) *t = NULL;
        if(*t){
                bitree1(&(*t)->left);
               bitree1(&(*t)->right);
        }
}

对于遍历就不多做解释了,上面已经解释的很详细了,本代码实例仅采用了先序输入二叉树的值,如果想采用其他方式,可以参考相应的遍历代码进行修改。

本文如有纰漏,请指出。

添加新评论

评论列表