数据结构简单入门/复习(五)-树与二叉树的代码示例(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;
    }
}

满二叉树.png

示例:
以上图的六结点完全二叉树为例:
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); 

You may also like...

发表评论

您的电子邮箱地址不会被公开。

6 + 1 =