数据结构简单入门/复习（五）-树与二叉树的代码示例（C语言）(2021/4/20更新)

2021/4/14更新：加了个非递归后序遍历。
2021/4/20更新：加了个使用线性队列的反向层序遍历，并为链式队列层序遍历添加注释。
2022/1/24更新：更改为 Markdown 格式，修复挂的图，修改不规范的代码格式。

链式存储结构

typedef struct BiTNode{
    TElemType data;                   //数据存储
    struct BiTNode *lchild, *rchild;  //左右孩子指针
}BiTNode; 

递归遍历

原理：以先序遍历为例，为了完成 根左右 的遍历方式，我们每次碰到根，就要输出根，输出完成后，再遍历左孩子，左孩子遍历完成后，遍历右孩子，之后结束遍历，这个遍历在递归遍历中较为容易理解与使用。

//先序遍历的递归算法
void preOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL，则直接结束这次小遍历。 
    printf(%d,, T->data);         //先进行结点数据输出。    (根)
    preOrderTraverse(T->lchild);    //再遍历左孩子。          (左)
    preOrderTraverse(T->rchild);    //最后遍历右孩子。        (右)
}
//中序遍历的递归算法
void inOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL，则直接结束这次小遍历。
    inOrderTraverse(T->lchild);     //先遍历左孩子。          (左) 
    printf(%d,, T->data);         //再进行结点数据输出。     (根)
    inOrderTraverse(T->rchild);     //最后遍历右孩子。        (右)
}
//后续遍历的递归算法
void postOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL，则直接结束这次小遍历。
    postOrderTraverse(T->lchild);   //先遍历左孩子。           (左) 
    postOrderTraverse(T->rchild);   //再遍历右孩子。           (右)
    printf(%d,, T->data);         //最后进行结点数据输出。    (根)
} 

非递归遍历

原理：
在非递归先序遍历中，我们使用栈，
先初始化一个栈，并将根结点推入栈

开始一个循环（栈非空）｛
    栈顶结点设置为node；
    栈顶结点退出；
    循环（node存在）｛
        输出node数据；
        如果（node有右孩子）右孩子推入栈；
        node的左孩子设置为node；
    ｝
｝

示例：
以上图的六结点完全二叉树为例：
1.初始化栈S；
2.根结点1推入栈S；
3.栈非空：栈顶结点1设置为node，栈退出一个结点1；
4.node1存在：输出1数据，右孩子3推入栈，左孩子2设置为node；
5.node2存在：输出2数据，右孩子5进入栈，左孩子4设置为node；
6.node4存在：输出4数据，左孩子NULL设置为node：
7.node不存在：栈顶结点5设置为node，栈退出一个结点5；
8.node5存在：输出5数据，左孩子NULL设置为node；
9.node不存在：栈顶结点3设置为node，栈退出一个结点3；
10.node3存在：输出3数据，左孩子6设置为node；
11.node6存在；输出6数据，左孩子NULL设置为node；
12.node不存在：栈空：循环结束。

//先序遍历非递归算法代码实现
//这串代码自带了简单的栈功能，为了方便理解，因为作为入门，栈的使用大多还不是很熟练。
//除非特殊需求或者爱好，请不要学习这个栈调用方式。
//伪代码已经在上方原理处了，稍微修改即可
void preOrderTraverse(BiTNode *T){
    BiTNode *stack[20], *node;            //定义一个大小为20的顺序栈stack，以及一个临时变量node
    int stackSize = 0;                    //栈的当前大小设置为0
    stack[stackSize] = T;                 //栈顶设置为根节点T
    stackSize++;                          //栈的大小增加
    while(stackSize != 0){                //如果栈非空，循环
        node = stack[stackSize-1];        //将栈顶元素设置成node
        stackSize--;                      //退栈
        while(node){                      //node存在，则循环
            printf(%d,, node->data);    //打印数据
            if(node->rchild){             //如果node的右孩子存在，则：
                stack[stackSize] = node->rchild;    //右孩子入栈
                stackSize++;              //栈的大小增加
            }
            node = node->lchild;          //node设置成node的左孩子
        }
    }
} 

• 时隔半年我又回来了，带来个后序遍历非递归，这里简单说明思路：

  • 设置topNode = temp = t，并入栈node

  • 循环：如果栈非空

  • 注：下面的node指的是是栈顶元素

  • temp != topNode->left && temp != topNode->right && topNode->left存在:temp = topNode，入栈left，continue

  • (temp == topNode->left || topNode->left == NULL)&& temp != topNode->right && topNode->right存在: temp = topNode，入栈right，continue

  • temp == topNode->right: temp = topNode，退栈，continue

  • topNode->left == topNode->right(仅空时成立): temp = topNode，退栈，continue

void postOrderTraverse(BiTNode* t) {
    BiTNode *s[10], *temp;
    int top = 0;
    s[top] = temp = t;
    while (top >= 0) {
        if (temp != s[top]->lchild && temp != s[top]->rchild && s[top]->lchild) {
            temp = s[top];
            top++;
            s[top] = temp->lchild;
            continue;
        }
        else if ((temp == s[top]->lchild || !s[top]->lchild ) && temp != s[top]->rchild && s[top]->rchild) {
            temp = s[top];
            top++;
            s[top] = temp->rchild;
            continue;
        }
        temp = s[top];
        printf(%d , temp->data);
        top--;
    }
}

层序遍历

今天这篇工作量有点大，我翻了翻以前写的代码，直接用了。

原理：与非递归算法类似，但是调用的是队列，更简单。
一句话概括：开始根节点入队，执行循环，循环中将队列出队一个，输出数据，并将其左右孩子入队，直到队列空，循环结束。

也以六结点完全二叉树为例
根结点1入队
1出队，输出1数据，1的孩子2 3入队
2出队，输出2数据，2的孩子4 5入队
3出队，输出3数据，3的孩子6入队
4出队，输出4数据，无孩子入队
5出队，输出5数据，无孩子入队
6出队，输出6数据，无孩子入队
队列空，循环结束

//从上到下，从左到右层序遍历
//使用链式队列
typedef struct queue {//层序遍历存储队列单元
    BiTNode *node;
    struct queue *next;
}queue;

typedef struct linkQueue {//层序遍历存储队列
    queue *front;
    queue *rear;
}linkQueue;

void levelOrder(BiTNode *bTree) {//层序遍历
    BiTNode *temp = bTree;
    if (temp) {
        linkQueue linkQ;
        queue *q=(queue*)malloc(sizeof(queue));
        q->node = temp;
        q->next = NULL;
        linkQ.front = linkQ.rear = q;
        while (linkQ.front) {    //队列非空
            if (linkQ.front->node->lChild) {    //有左孩子，入队左孩子
                linkQ.rear->next = (queue*)malloc(sizeof(queue));
                linkQ.rear->next->node = linkQ.front->node->lChild;
                linkQ.rear = linkQ.rear->next;
                linkQ.rear->next = NULL;
            }
            if (linkQ.front->node->rChild) {    //有右孩子，入队右孩子
                linkQ.rear->next = (queue*)malloc(sizeof(queue));
                linkQ.rear->next->node = linkQ.front->node->rChild;
                linkQ.rear = linkQ.rear->next;
                linkQ.rear->next = NULL;
            }
            printf(%d , linkQ.front->node->data);    //打印队头数据
            if(linkQ.front->next)linkQ.front = linkQ.front->next;    //队列非空，出队一个
            else break;    //队列空，结束循环
        }
        printf(\n);

    }
} 

// 从下到上，从右到左的层序遍历。
// 使用线性队列。
// 实际上是将上面的从头输出到尾的队列，改成从尾巴向头输出。
void orderOrderTraverse(BiTNode* t) {
    BiTNode *q[10];
    int front, rear;
    front = 0;
    q[front] = t;
    rear = 1;
    while (front != rear) {
        if (q[front]->lchild) {
            q[rear] = q[front]->lchild;
            rear += 1;
        }
        if (q[front]->rchild) {
            q[rear] = q[front]->rchild;
            rear += 1;
        }
        front += 1;
    }
    while (rear > 0) {
        rear -= 1;
        printf(%d , q[rear]->data);
    }
}

使用示例

//创建一个六结点完全二叉树
//下面这串创建二叉树的代码只是为了方便使用，用函数展示不太方便
//如果有人参考下面这个创建示例，请不要找我出医药费。
BiTNode *bTree = (BiTNode*)malloc(sizeof(BiTNode));
bTree->data = 1;
bTree->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->data = 2;
bTree->rchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->rchild->data = 3;
bTree->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->lchild->data = 4;
bTree->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->rchild->data = 5;
bTree->lchild->lchild->lchild = NULL;
bTree->lchild->lchild->rchild = NULL;
bTree->lchild->rchild->lchild = NULL;
bTree->lchild->rchild->rchild = NULL;
bTree->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->rchild->lchild->data = 6;
bTree->rchild->rchild = NULL;
bTree->rchild->lchild->lchild = NULL;
bTree->rchild->lchild->rchild = NULL;

//先序遍历
preOrderTraverse(bTree);
levelOrder(bTree);

//结束前暂停
system(PAUSE);