最近在学习数据结构中树的概念，迟迟不得入门，应该是自己的懒惰和没有勤加练习导致的，以后应该多加练习

每一个节点最多有两棵子树，所以二叉树中不存在度大于2的节点，注意，是最多有两棵，没有也是可以的
左子树和右子树是有顺序的，次序不能颠倒，这点可以在哈夫曼编码中体现， 顺序不同编码方式不同

-即使树中某个节点中只有一个子树的花，也要区分它是左子树还是右子树
二叉树一般有五种形态
1.空二叉树
2.只有一个根节点
3.根结点只有左子树
4.根节点只有右子树

二叉树的性质
1：在二叉树的第i层上最多有2^(i-1)个节点
2：深度为K的二叉树之多有2^(k-1)个节点

注：这里的深度K意思就是有K层的二叉树

3：对于任何一棵二叉树T，如果其终端节点有No个，度为2的节点数有N2，则No=N2+1
4: 具有n个节点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数）

1，二叉树的存储结构（二叉链表）

//二叉树的存储结构，一个数据域，2个指针域

 typedef struct BiTNode

{

     char data;

     struct BiTNode *lchild,*rchild;

  }BiTNode,*BiTree;

2，首先要建立一个二叉树，建立二叉树必须要了解二叉树的遍历方法。，我在这里展示的是二叉树的递归建立方式

//我在这里实现的是，二叉树的前序遍历方式创建，如果要使用中序或者后序的方式建立二叉树，只需将生成结点和构造左右子树的顺序改变即可

 void CreateBiTree(BiTree *T)

  { 

   

      char ch;

      scanf("%c",&ch);

      if(ch=='#')

          *T=NULL;

      else

     { 

   

         *T=(BiTree  )malloc(sizeof(BiTNode));

         if(!*T)

             exit(-1);

          (*T)->data=ch;

          CreateBiTree(&(*T)->lchild);

         CreateBiTree(&(*T)->rchild);

      }

 }

3。二叉树的遍历方式（递归建立）

void PreOrderTraverse(BiTree T)//二叉树的先序遍历

{ 

   

    if(T==NULL)

        return ;

    printf("%c ",T->data);

    PreOrderTraverse(T->lchild);

    PreOrderTraverse(T->rchild);

}

void InOrderTraverse(BiTree T)//二叉树的中序遍历

{ 

   

   if(T==NULL)

       return ;

   InOrderTraverse(T->lchild);

    printf("%c ",T->data);

   InOrderTraverse(T->rchild);

}

void PostOrderTraverse(BiTree T)//后序遍历

{ 

   

    if(T==NULL)

        return;

    PostOrderTraverse(T->lchild);

    PostOrderTraverse(T->rchild);

    printf("%c ",T->data);

}

4.完整代码

#include

#include

typedef struct BiTNode

{ 

   

    char data;

    struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

void PreOrderTraverse(BiTree T)//二叉树的先序遍历

{ 

   

    if(T==NULL)

        return ;

    printf("%c ",T->data);

    PreOrderTraverse(T->lchild);

    PreOrderTraverse(T->rchild);

}

void InOrderTraverse(BiTree T)//二叉树的中序遍历

{ 

   

   if(T==NULL)

       return ;

   InOrderTraverse(T->lchild);

    printf("%c ",T->data);

   InOrderTraverse(T->rchild);

}

void PostOrderTraverse(BiTree T)//后序遍历

{ 

   

    if(T==NULL)

        return;

    PostOrderTraverse(T->lchild);

    PostOrderTraverse(T->rchild);

    printf("%c ",T->data);

}

void CreateBiTree(BiTree *T)

{ 

   

    char ch;

    scanf("%c",&ch);

    if(ch=='#')

        *T=NULL;

    else

    { 

   

        *T=(BiTree  )malloc(sizeof(BiTNode));

        if(!*T)

            exit(-1);

        (*T)->data=ch;

        CreateBiTree(&(*T)->lchild);

        CreateBiTree(&(*T)->rchild);

    }

}

int main()

{ 

   

    BiTree T;

    CreateBiTree(&T);

    PreOrderTraverse (T);

    InOrderTraverse(T);

    PostOrderTraverse(T);

    return 0;

}

对知识点的补充：
（1）建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。

如图为扩展二叉树：（前序遍历为：ABDG##H###CE#I##F##）