C语言实现二叉树（链式）_写出用 c 语言定义一个二叉树的二叉链表结点结构的算法。

        一颗二叉树是一个节点的有限集合，是由一个根节点和两个子树构成；每个子树又有两个子树。这两个子树分为左子树和右子树，且顺序不能颠倒。如图，像一个倒着的树一样：

它有两种存储方式，一种是顺序存储，一种是链式存储。

顺序存储：

        对于一棵完全二叉树所有结点按照层序自顶向下，同一层自左向右顺序存入一个顺序表中，如果该节点为空，则存入一个特殊的字符代表NULL。例如： 

这就是二叉树的顺序存储。

优点：存储完全二叉树，简单省空间
缺点：存储一般二叉树尤其单支树，存储空间利用不高

链式存储：

        二叉树的链式存储结构是用结构体定义结点，每个结点有两个指针，一个指向它的左子树，一个指向右子树。如图：

下面实现二叉树链式结构的基本操作：

定义结点：

typedef char DataType;
typedef struct TreeNode
{
    DataType elem;
    struct TreeNode* rchild;
    struct TreeNode* lchild;
}TreeNode;

实现二叉树的初始化：

void InitTree(TreeNode** root)
{
    assert(root);
    if(*root == NULL)
        return;
    *root = NULL;
    return;
}

实现二叉树的先序遍历：

算法：（递归版本）

    若二叉树为空，算法结束；否则

        a 访问根节点

        b 先序遍历根节点的左子树

        c 先序遍历根节点的右子树

void PreOrder(TreeNode* root)
{
    if(root == NULL)                                                                                                                 
        return;
    printf("%c ", root->elem);
    PreOrder(root->lchild);
    PreOrder(root->rchild);
    return;
}

实现非递归版本的先序遍历：

1.若根节点为空（空树，不需要遍历），直接返回；

2.否则，将根节点入栈；

3.判断栈是否为空，不为空进入循环；

4.取栈顶结点并访问该节点，同时将该节点出栈；

5.若该节点的右子树不为空，将右孩子结点入栈；

6.若该节点的左子树不为空，将左孩子节点入栈；

7.直到栈为空，跳出循环，完成了先序遍历。

void PreOrderByLoop(TreeNode* root)
{
    if(root == NULL)
        return;
   SeqStack s;
   InitSeqStack(&s);
   PushSeqStack(&s, root);
   TreeNode* tmp;
   while(IsEmpty(&s) != 1)
   {
       TopSeqStack(&s, &tmp);
       printf("%c ", tmp->elem);
       PopSeqStack(&s);
       if(tmp->rchild != NULL)
           PushSeqStack(&s, tmp->rchild);                                                                                              
       if(tmp->lchild != NULL)
           PushSeqStack(&s, tmp->lchild);
   }
   return;
}

实现二叉树的中序遍历：

递归版本：

    若二叉树为空，直接返回；否则

1.遍历二叉树的左子树

2.访问根节点

3.遍历二叉树的右子树

void InOrder(TreeNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->lchild);
    printf("%c ", root->elem);                                                                                                       
    InOrder(root->rchild);
    return;
}

非递归版本：

1.若树为空，直接返回；否则令tmp=root，进入循环（跳出条件为栈为空 或 tmp==NULL）

2.循环的将tmp节点的所有左子树入栈

3.取栈顶结点为tmp，访问该节点并出栈

4.令tmp=tmp的右孩子，进入下一次循环

void InOrderByLoop(TreeNode* root)
{
    if(root == NULL)
        return;
    SeqStack s;
    InitSeqStack(&s);
    TreeNode* tmp = root;
    while(IsEmpty(&s) != 1 || tmp != NULL)
    {
        while(tmp != NULL)
        {
            PushSeqStack(&s, tmp);
            tmp = tmp->lchild;
        }
        TopSeqStack(&s, &tmp);
        printf("%c ", tmp->elem);                                                                                                      
        tmp = tmp->rchild;
        PopSeqStack(&s);
    }

实现二叉树的后续遍历：

递归版本：

若树为空，直接返回；否则

1.遍历根节点的左子树；

2.遍历根节点的右子树；

3.访问根节点。

void PostOrder(TreeNode* root)
{
    if(root == NULL)
        return;                                                                                                                      
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%c ", root->elem);
    return;
}

非递归版本：

1.若树为空，直接返回；否则令tmp= root，进入循环（条件为栈非空或tmp！=NULL）

2.循环的将所有左子树入栈；

3.去栈顶结点，若该节点没有右子树或者右子树已经访问过了，则访问该节点并出栈；

4.否则，令tmp为该节点的右子树，进入下一层循环。

void PostOrderByLoop(TreeNode* root)
{
    if(root == NULL)
        return;
    TreeNode* tmp = root;
    TreeNode* pre = NULL;
    TreeNode* top;
    SeqStack s;
    InitSeqStack(&s);
    while(IsEmpty(&s) != 1 || tmp != NULL)
    {
        while(tmp != NULL)
        {
            PushSeqStack(&s, tmp);
            tmp = tmp->lchild;
        }
        TopSeqStack(&s, &top);
        if(top->rchild == NULL || top->rchild == pre)
        {
            printf("%c ", top->elem);
            pre = top;
            PopSeqStack(&s);
        }
        else
            tmp = top->rchild;                                                                                                         
    }
    return;
}

实现二叉树的层序遍历：

1.若树为空，直接返回；

2.否则将根节点入队列；

3.取队首结点，访问该节点；

4.若该节点的左子树不为空，将左子树入队列；若右子树不为空，将右子树入队列；

5.循环的进行3和4，直到队列为空。

void LevelOrder(TreeNode* root)
{
    if(root == NULL)
        return;
    SeqQueue q;
    InitSeqQueue(&q);
    PushSeqQueue(&q, root);
    TreeNode* tmp;
    while(SizeSeqQueue(&q) != 0)
    {
        FrontSeqQueue(&q, &tmp);
        printf("%c ", tmp->elem);
        if(tmp->lchild != NULL)
            PushSeqQueue(&q, tmp->lchild);
        if(tmp->rchild != NULL)                                                                                                        
            PushSeqQueue(&q, tmp->rchild);
        PopSeqQueue(&q);
    }
    return;
}

二叉树前序遍历规则应用：二叉树的创建/拷贝
二叉树的创建：

        现有一个带有特殊字符的二叉树先序遍历结果，其中特殊字符是代表空节点，如何建立这样的二叉树？

        答：利用递归版本的先序遍历方法，构建还原该二叉树。

TreeNode* _CreateTree(DataType array[], size_t size, DataType null_node, size_t* index)
{
    assert(index);
    if(*index >= size)                                                                                                                 
        return NULL;
    if(array[*index] == null_node)
    {
        ++*index;
        return NULL;
    }
    TreeNode* new_node = CreateNode(array[(*index)++]);
    new_node->lchild = _CreateTree(array, size, null_node, index);
    new_node->rchild = _CreateTree(array, size, null_node, index);
    return new_node;
}
TreeNode* CreateTree(DataType array[], size_t size, DataType null_node)
{
    assert(array);
    size_t index = 0;
    return _CreateTree(array, size, null_node, &index);
}

二叉树的拷贝：

类似的：

TreeNode* TreeClone(TreeNode* root)
{
    if(root == NULL)
        return NULL;
    TreeNode* new_node = CreateNode(root->elem);
    new_node->lchild = TreeClone(root->lchild);
    new_node->rchild = TreeClone(root->rchild);
    return new_node;
}                                                                                                                                    

二叉树后序遍历规则应用：二叉树的销毁

void DestroyNode(TreeNode* node)
{
    free(node);
    return;
}
void TreeDestroy(TreeNode** root)
{
    assert(root);
    if(*root ==NULL)
        return;
    TreeDestroy(&((*root)->lchild));
    TreeDestroy(&((*root)->rchild));
    DestroyNode(*root);
    *root = NULL;                                                                                                                    
    return;
}

求二叉树的高度 ：

二叉树的高度为左子树和右子树高度较大的那一个！

size_t TreeHeight(TreeNode* root)
{
    if(root == NULL)
        return 0;                                                                                                                    
    size_t lheight = TreeHeight(root->lchild) + 1;
    size_t rheight = TreeHeight(root->rchild) + 1;
    return rheight > lheight ? rheight : lheight;
}

求二叉树叶子结点的个数

叶子结点：没有左右孩子的结点；

二叉树叶子结点的个数 = 左子树叶子结点的个数 + 右子树叶子结点的个数。

size_t TreeLeafSize(TreeNode* root)                                                                                                  
{   
    if(root == NULL)
        return 0;
    if(root->lchild == NULL && root->rchild == NULL)
        return 1;
    return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}

求二叉树第K层结点的个数

size_t TreeKLevelSize(TreeNode* root, int K)                                                                                         
{   
    if(root == NULL)
        return 0;
    if(K == 1) 
        return 1;
    return TreeKLevelSize(root->lchild, K-1) + TreeKLevelSize(root->rchild, K-1);
} 

求二叉树的镜像 

解决方法：递归的交换二叉树的左右子树。

void TreeMirror(TreeNode* root)
{                                                                                                                                    
    if(root == NULL)
        return;
    TreeNode* tmp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = tmp;
    TreeMirror(root->lchild);
    TreeMirror(root->rchild);
    return;
}

解决方法（二）：（非递归）

遍历该二叉树，同时交换每个结点的左右子树。

以下是用层序遍历实现的：

void TreeMirrorByLoop(TreeNode* root)
{
    if(root == NULL)
        return;
    SeqQueue q;                                                                                                                        
    InitSeqQueue(&q);
    PushSeqQueue(&q, root);
    TreeNode* tmp;
    while(SizeSeqQueue(&q) > 0)
    {   
        FrontSeqQueue(&q, &tmp);
        TreeNode* tp = tmp->lchild;
        tmp->lchild = tmp->rchild;
        tmp->rchild = tp; 
        if(tmp->lchild != NULL)
            PushSeqQueue(&q, tmp->lchild);
        if(tmp->rchild != NULL)
            PushSeqQueue(&q, tmp->rchild);
        PopSeqQueue(&q);
    }   
    return;
}

判断一棵二叉树是否为完全二叉树(层序遍历变形)

问题分析：

        若为完全二叉树，层序遍历每个结点，左右子树都存在，直到遍历到一个转折结点，若只有左子树或没有子树，那么接下来层序遍历的结点都没有子树。

问题解决：

1.将根节点入队列，并且置flag=0（代表不是完全二叉树）；

2.进入循环（循环条件为队列非空）；

3.取队首结点，并出队列

4.若flag==0

  若该节点左右孩子都存在，分别入队列；

  若该节点只有左孩子节点，入队列，并置flag=1；

  若该节点只有右孩子结点，返回0（不是完全二叉树）；

5.若flag==1

   若该节点左右孩子都不存在，什么都不做；

   否则，flag=0；

6.直到队列为空，跳出循环，返回flag。

int IsCompleteTree(TreeNode* root)
{
    if(root == NULL)
        return 1;
    SeqQueue q;
    int flag = 0;             //表示该树不是完全二叉树
    InitSeqQueue(&q);
    PushSeqQueue(&q, root);
    TreeNode* tmp = root;
    while(FrontSeqQueue(&q, &tmp))
    {
        PopSeqQueue(&q);
        if(flag == 0)
        {
            if(tmp->lchild != NULL && tmp->rchild != NULL)
            {
                PushSeqQueue(&q, tmp->lchild);
                PushSeqQueue(&q, tmp->rchild);
            }
            else if(tmp->lchild == NULL && tmp->rchild != NULL)
                return 0;
            else if(tmp->lchild != NULL && tmp->rchild == NULL)
            {
                PushSeqQueue(&q, tmp->rchild);
                flag = 1;                                                                                                              
            }
            else
            {
                flag = 1;
            }
        }
        else
        {
            if(tmp->lchild != NULL && tmp->rchild != NULL);
            else
                flag = 0;
        }
    }
    return flag;
}