写在前面

二叉树的几乎所有实现都是依靠递归实现，递归的核心思路是把任何一个二叉树看成根和左右子树，而二叉树递归的核心玩法就是把二叉树的左右子树再看成根，再找左右子树，再看成根...

因此，解决二叉树问题实际上要把二叉树转换成一个一个子树的过程，找到一个一个的子树再组装起来就形成了二叉树

二叉树的创建

二叉树建立的正统方法是利用递归，这里展示递归的一种写法

BTNode* BuyNode(BTDataType a)
{
   
   
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = a;
    newnode->left = NULL;
    newnode->left = NULL;
    return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
   
   
    if (a[*pi] == '#')
    {
   
   
        (*pi)++;
        return NULL;
    }

    BTNode* root = BuyNode(a[*pi]);
    (*pi)++;

    root->left = BinaryTreeCreate(a, pi);
    root->right = BinaryTreeCreate(a, pi);

    return root;
}

如果你对递归的认识并不熟悉，下面我画了一幅递归展开图，更好解释这其中的原理

(右子树的部分过程由于空间原因不够完全展开，但如果看懂左子树的构建过程，右子树不难自己画出)

这里注意的是，函数栈帧的创建并不是每一个都不一样的位置，当一个栈帧被销毁后，另外一个栈帧创建就会在原来的位置，因此在计算空间复杂度的时候需要考虑这个问题：
==空间是可以重复利用的，时间是一去不复返的==

从这幅图中，相信可以理解这段代码的含义了

首先创建一个根节点，根节点去寻找左子树进入递归，而进入递归后继续寻找左子树...直到遇到NULL截止，而遇到空后就寻找右子树，右子树也找到空后返回，这样就构建出了二叉树中最小的一棵树，而这棵树会返回，作为根的左子树，然后继续进入递归寻找根的右子树...

由于是借助链表进行实现的，因此我们可以理解为首先创建好根，而根的左右子树用函数创建好后再连接起来...当遇到#就返回，形成了一个一个的小树，小树最后组成大树，就形成了二叉树

二叉树的遍历

二叉树的遍历主要有前序遍历，中序遍历，后序遍历，层序遍历

前序遍历

前序遍历是指遍历时先访问根，再访问左子树，再访问右子树

代码实现如下

void BinaryTreePrevOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    printf("%c ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}

下面依旧画出它的递归展开图

中序遍历

中序遍历是先访问左子树，再访问根，最后访问右子树

void BinaryTreeInOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    BinaryTreeInOrder(root->left);
    printf("%c ", root->data);
    BinaryTreeInOrder(root->right);
}

递归图和上面基本类似，就不做画出了

后序遍历

后序遍历是先访问左子树，再访问右子树，最后访问根

void BinaryTreePostOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->data);
}

递归图和上面基本类似，就不做画出了