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

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

本文如有纰漏，请指出。