前言

Algorithms Data Structures = Programs
”数据结构 + 算法 = 程序“
by Niklaus Wirth

二叉树

注意：在阅读本文之前需要掌握栈和队列这两种基本的数据结构

二叉树是一种树形结构，其特点是每个节点至多只有两颗子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

基本数据结构

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define dataType char
#define MAX_SIZE 50
#define Element BinaryTree *
#define endl() printf("\n")
typedef struct TreeNode
{
    /* data */
    dataType val;
    struct TreeNode *left;		//左子树
    struct TreeNode *right;		//右子树
} BinaryTree;
typedef struct Stack		//栈
{
    /* data */
    Element data[MAX_SIZE];
    int cursor;
} Stack;

typedef struct Queue		//队列
{
    /* data */
    Element data[MAX_SIZE];
    int rear;
    int front;
} Queue;

基本数据结构算法

void visited(BinaryTree *tree);
Stack initStack();
Element pop(Stack *st);
void push(Stack *st, Element el);
bool IsEmpty(Stack st);
Element peek(Stack st);
Queue initQueue();
Element get(Queue *q);
void put(Queue *q, Element el);
bool IsEmptyQueue(Queue q);
bool IsOverflowQueue(Queue q);

void visited(BinaryTree *tree)
{
    printf("%c\t", tree->val);
}
Queue initQueue()
{
    Queue q;
    q.front = 0;
    q.rear = 0;
    return q;
}
bool IsEmptyQueue(Queue q)
{
    return q.rear == q.front;
}
bool IsOverflowQueue(Queue q)
{
    return q.front >= MAX_SIZE;
}
Element get(Queue *q)
{
    return (*q).data[(*q).rear++];
}
void put(Queue *q, Element el)
{
    (*q).data[(*q).front++] = el;
}
Stack initStack()
{
    Stack st;
    st.cursor = -1;
    return st;
}
Element pop(Stack *st)
{
    return (*st).data[(*st).cursor--];
}
void push(Stack *st, Element el)
{
    (*st).data[++(*st).cursor] = el;
}
bool IsEmpty(Stack st)
{
    return st.cursor == -1 ? true : false;
}
Element peek(Stack st)
{
    return st.data[st.cursor];
}

建立一颗二叉树

递归建立二叉树

BinaryTree *create_binary_tree();
BinaryTree *create_binary_tree()
{
    dataType ch = getchar();
    if (ch != '#')
    {
        BinaryTree *tree = (BinaryTree *)malloc(sizeof(BinaryTree));
        tree->val = ch;
        tree->left = create_binary_tree();
        tree->right = create_binary_tree();
        return tree;
    }
    return NULL;
}

二叉树样例

ABD##E#H##CG#I##F##

二叉树样例

二叉树的四种基本遍历

前序遍历

前序遍历（VLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

实现前序遍历之前，请读者先思考一下一个问题，怎么才算遍历完一个节点？

要进行前序遍历，就得从根节点（样例中的A节点）出发，遍历完其右结点，遍历其左节点，我们发现如果直接分析根节点是很复杂的，于是我们选择自低向上的分析法，先看D节点，由于D节点没有子节点，所以在访问完D节点之后，是不需要保存D节点的。

再看B节点，在访问完B节点之后，如果不将B节点保存，则无法访问到其后继节点，因此首先确定一点如果存在有后继节点的节点是需要先保存下来的，然后进入到其子节点，A节点同理。于是我们发现，越是后面保存的节点反而越先被访问完，因此我们选取一种能够实现后进先出得数据结构 — — 栈，这种数据结构作为保存节点的工具。

数据结构确定了，那我们应该采取何种算法呢？这就需要找到前序遍历的特点了，前面有底向上分析，得出数据结构，接下来就模拟遍历过程，找出规律或者是共同点。访问A，A是否有子节点，是，那就将A节点存入栈，然后往下走，此时问题又来了，往哪里走？往C走？显然不符合先序遍历，那么就只能往B走，走走走，边走边存，走到D，发现D点没有子节点，访问完之后可以不保存，那么接下来怎么办呢，我们发现B的的右节点E还没访问，那么怎么才能访问到E呢，我们惊喜的发现栈中存了B而且还是最后一个存入的，因此取出B，进入B的右子树E，发现E也有子节点，因此将E也存入栈，如此循环往复，直至栈为空，也就是遍历完成，分析至此，程序也不难写出，代码如下：

void preorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            visited(temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = pop(&st);
            temp = temp->right;
        }
    }
}

前序遍历： A B D E H C G I F

中序遍历

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

把所有的节点投影到水平面就是中序遍历的顺序。
中序遍历与前序遍历的思路差不多，区别在于什么时候进行访问节点。

void inorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = pop(&st);
            visited(temp);
            temp = temp->right;
        }
    }
}

中序遍历： D B E H A G I C F

后序遍历

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

后序遍历比较难，主要难点在于如何判断一个节点的左右节点是否都已访问。

void postorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    BinaryTree *record = NULL;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = peek(st);

            if (temp->right != NULL && temp->right != record)
            {
                temp = temp->right;
            }
            else
            {
                visited(temp);
                record = pop(&st);
                temp = NULL;
            }
        }
    }
}

后序遍历： D H E B I G F C A

层次遍历

二叉树的层次遍历，顾名思义就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。

void levelorder(BinaryTree *tree)
{
    Queue q = initQueue();
    BinaryTree *temp = tree;
    put(&q, temp);
    while (!IsEmptyQueue(q))
    {
        /* code */
        temp = get(&q);
        visited(temp);
        if (temp->left != NULL)
            put(&q, temp->left);
        if (temp->right != NULL)
            put(&q, temp->right);
    }
}