二叉树（二）

布满荆棘的人生 2024-03-24 12:04 60阅读 0赞

#### 二叉树 ####

*  一.遍历二叉树

## 一.遍历二叉树 ##

![在这里插入图片描述][4195bceaed6e4dc88088dbfcea527a1f.png]

![在这里插入图片描述][0e453bc094bb46da962819c420587593.png]

> **遍历分为前序，中序，后序，层序四种遍历。**

*一个例子，前序遍历*

> **先根，然后左子树，然后右子树。**

![在这里插入图片描述][c1e66c67ca7647a88f65522fad95fb6f.png]

> **由于一个普通的二叉树遍历并没有任何意义，所以为了方便起见直接链接一个题。改题的思路就是将一个数组先建成一个前序遍历的树，然后再中序遍历这棵树再输出。**

[二叉树的遍历][Link 1]

#include <stdio.h>
    #include<stdlib.h>
    
    struct TreeNode {
        
        struct TreeNode* left;
        struct TreeNode* right;
        char val;
    };
    
    struct TreeNode* TreeCreat(int* pi, char* a)
    {
        
        if (a[*pi] == '#')
        {
        
            (*pi)++;
            return NULL;
        }
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = a[(*pi)++];
        root->left = TreeCreat(pi, a);
        root->right = TreeCreat(pi, a);
        return root;
    }
    
    void InOrder(struct TreeNode* root)
    {
        
        if (root == NULL)
            return;
        InOrder(root->left);
        printf("%c ", root->val);
        InOrder(root->right);
    }
    
    int main() {
        
        char a[110];
        scanf("%s", a);
        int i = 0;
        struct TreeNode* root = TreeCreat(&i, a);//创建一个前序遍历的树
    
        InOrder(root);//中序遍历
    
        return 0;
    }

> **层序遍历，利用队列进行入队出队操作。队列里存的是树的结点指针。**

![在这里插入图片描述][7e3dbe60b04a4e90ad48a9500e4ab989.png]

[4195bceaed6e4dc88088dbfcea527a1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/62a9ca05f4fa49c495b5039d3891f9b9.png
[0e453bc094bb46da962819c420587593.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4b1e7168ebd84ddca2fc0b3ed6df2098.png
[c1e66c67ca7647a88f65522fad95fb6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d548ba9e42d64d889f21f847583d2550.png
[Link 1]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[7e3dbe60b04a4e90ad48a9500e4ab989.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f9d4fc0646ca499fbd96948aa07387ec.png