首页 > 其他分享 >二叉树遍历(C语言版)

二叉树遍历(C语言版)

时间:2023-12-31 19:33:06浏览次数:36  
标签:遍历 cur returnSize int res C语言 right 二叉树 root

二叉树遍历

先序

递归

int *res;

void preorder(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    // 根左右
    res[(*returnSize)++] = root->val;
    preorder(root->left, returnSize);
    preorder(root->right, returnSize);
}

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    preorder(root, returnSize);
    return res;
}

迭代

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    struct TreeNode *stack[100];
    int top = 0;

    while (top != 0 || root != NULL) {
        // 左子树入栈
        while (root != NULL) {
            // 访问
            res[(*returnSize)++] = root->val;
            stack[top++] = root;
            root = root->left;
        }

        root = stack[--top];
        root = root->right;
    }

    return res;
}

迭代(右子树先入栈)

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    struct TreeNode *stack[100];
    int top = 0;
    stack[top++] = root;

    while (top != 0) {
        root = stack[--top];
        res[(*returnSize)++] = root->val;
        // 右子树先入栈
        if (root->right != NULL) stack[top++] = root->right;
        if (root->left != NULL) stack[top++] = root->left;
    }
    return res;
}

右左根访问,再反转序列

int *res;

void dfs(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    // 按右左根的顺序访问,再把序列反过来
    dfs(root->right, returnSize);
    dfs(root->left, returnSize);
    res[(*returnSize)++] = root->val;
}

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    dfs(root, returnSize);

    // 序列反过来
    int left = 0, right = *returnSize - 1;
    while (left < right) {
        int temp = res[left];
        res[left] = res[right];
        res[right] = temp;
        left++;
        right--;
    }

    return res;
}

Morris

int *res;

// Morris
void preorderMorris(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;

    struct TreeNode *cur = root;

    while (cur != NULL) {
        if (cur->left != NULL) {
            // 左子树不空,遍历左子树,找到左子树的最右侧节点
            struct TreeNode *rightMost = cur->left;
            while (rightMost->right != NULL && rightMost->right != cur) {
                rightMost = rightMost->right;
            }
            // 最右侧节点的右指针指向NULL或者cur
            if (rightMost->right == NULL) {
                // 有左右孩子的节点第一次被访问
                res[(*returnSize)++] = cur->val;
                // 把最右侧节点的right指向cur
                rightMost->right = cur;
                // 访问左子树
                cur = cur->left;
            } else {
                // 有左右孩子的节点第二次被访问
                // 恢复
                rightMost->right = NULL;
                // 遍历右子树
                cur = cur->right;
            }
        } else {
            // 只有右孩子的节点只会被访问一次
            res[(*returnSize)++] = cur->val;
            // 遍历右子树
            cur = cur->right;
        }
    }
}

int *preorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    preorderMorris(root, returnSize);
    return res;
}

中序

递归

int *res;

void inorder(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    // 左根右
    inorder(root->left, returnSize);
    res[(*returnSize)++] = root->val;
    inorder(root->right, returnSize);
}

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    inorder(root, returnSize);
    return res;
}

迭代

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    struct TreeNode *stack[100];
    int top = 0;

    while (top != 0 || root != NULL) {
        // 左子树入栈
        while (root != NULL) {
            stack[top++] = root;
            root = root->left;
        }

        root = stack[--top];
        // 访问
        res[(*returnSize)++] = root->val;
        root = root->right;
    }

    return res;
}

Morris

int *res;

void inorderMorris(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    struct TreeNode *cur = root;
    while (cur != NULL) {
        if (cur->left != NULL) {
            struct TreeNode *rightMost = cur->left;
            while (rightMost->right != NULL && rightMost->right != cur) {
                rightMost = rightMost->right;
            }
            if (rightMost->right == NULL) {
                rightMost->right = cur;
                cur = cur->left;
            } else {
                // 有左右孩子的节点第二次被经过,左子树都遍历完了,访问节点
                res[(*returnSize)++] = cur->val;
                rightMost->right = NULL;
                cur = cur->right;
            }
        } else {
            // 只有右孩子的节点只会被经过一次,直接访问
            res[(*returnSize)++] = cur->val;
            cur = cur->right;
        }
    }
}

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    inorderMorris(root, returnSize);
    return res;
}

后序

递归

int *res;

void postOrder(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    // 左右根
    postOrder(root->left, returnSize);
    postOrder(root->right, returnSize);
    res[(*returnSize)++] = root->val;
}

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    postOrder(root, returnSize);
    return res;
}

迭代

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    struct TreeNode *stack[100];
    int top = 0;
    // 记录上个访问的节点
    struct TreeNode *pre = NULL;

    while (top != 0 || root != NULL) {
        // 左子树入栈
        while (root != NULL) {
            stack[top++] = root;
            root = root->left;
        }

        root = stack[--top];
        if (root->right == NULL || root->right == pre) {
            // 右子树为空或者已经访问完了,可以访问这个节点了
            res[(*returnSize)++] = root->val;
            pre = root;
            root = NULL;
        } else {
            // 遍历右子树
            // 先把当前节点再次压栈
            stack[top++] = root;
            root = root->right;
        }
    }

    return res;
}

Morris

int *res;

// 把右子树反转
struct TreeNode *reverseRightTree(struct TreeNode *root) {
    struct TreeNode *pre = NULL;
    struct TreeNode *cur = root;
    while (cur != NULL) {
        struct TreeNode *nextRight = cur->right;
        cur->right = pre;
        pre = cur;
        cur = nextRight;
    }
    return pre;
}

// 自底向上访问右节点(访问反转后的右节点)
void visitReversedRightTree(struct TreeNode *root, int *returnSize) {
    // 反转右子树
    struct TreeNode *reversed = reverseRightTree(root);
    struct TreeNode *cur = reversed;
    while (cur != NULL) {
        res[(*returnSize)++] = cur->val;
        cur = cur->right;
    }
    // 反转回去
    reverseRightTree(reversed);
}

void postorderMorris(struct TreeNode *root, int *returnSize) {
    struct TreeNode *cur = root;
    while (cur != NULL) {
        if (cur->left != NULL) {
            struct TreeNode *rightMost = cur->left;
            while (rightMost->right != NULL && rightMost->right != cur) {
                rightMost = rightMost->right;
            }
            if (rightMost->right == NULL) {
                rightMost->right = cur;
                cur = cur->left;
            } else {
                rightMost->right = NULL;
                // 一个节点被第二次经过的时候,自底向上访问左子树的所有的右节点
                visitReversedRightTree(cur->left, returnSize);
                cur = cur->right;
            }
        } else {
            cur = cur->right;
        }
    }
    // 再遍历一次
    visitReversedRightTree(root, returnSize);
}


int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    postorderMorris(root, returnSize);
    return res;
}

层序

int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
    // 一层最多元素个数
    const int size = 1002;
    // 最多层数
    const int leverMax = 2000;

    // 返回的二维数组,第一维表示所在层,第二维表示该层的所有元素
    int **res = (int **) malloc(sizeof(int *) * leverMax);
    // 一维的维度(多少层)
    *returnSize = 0;
    // 每个二维的维度(每层多少元素)
    *returnColumnSizes = (int *) malloc(sizeof(int) * leverMax);
    if (root == NULL) return res;


    // 循环队列
    struct TreeNode *queue[size];
    int lever = 0;
    // 保存每层元素个数,下标就是所在层,从0开始
    int *columnSize = (int *) calloc(leverMax, sizeof(int));
    int front = 0, rear = 0;
    queue[rear++] = root;

    while (front != rear) {
        // 当前层元素数
        int count = (rear - front + size) % size;
        res[lever] = (int *) malloc(sizeof(int) * count);
        int temp = 0;
        while (count-- > 0) {
            root = queue[(front++) % size];
            // 记录当前层的元素
            res[lever][temp++] = root->val;
            // 当前层元素总数加一
            columnSize[lever]++;
            if (root->left != NULL) queue[(rear++) % size] = root->left;
            if (root->right != NULL) queue[(rear++) % size] = root->right;
        }
        // 加一层
        lever++;
    }

    *returnSize = lever;
    for (int i = 0; i < lever; ++i) 
        (*returnColumnSizes)[i] = columnSize[i];
    return res;
}

标签:遍历,cur,returnSize,int,res,C语言,right,二叉树,root
From: https://www.cnblogs.com/sprinining/p/17937905

相关文章

  • 2023-2024-1 20231407陈原第计算机科学概论与C语言程序设计第十四周学习总结
    这个作业属于哪里计算机科学概论与C语言程序设计作业要求https://www.cnblogs.com/rocedu/p/9577842.html#WEEK14作业内容学习C语言程序设计第十三章作业正文  https://www.cnblogs.com/CCCY12345/p/17937889  ......
  • 力扣543-二叉树的直径
    难度:【简单】定义:在一个二叉树中,任意两个节点之间的路径中最长的路径的长度称为其直径。路径长度由两个节点之间经过的“边”表示,而不是节点数。且二叉树的直径不一定经过根节点。先大致看了官方解法,不理解,心情暴躁没看懂,就自己瞎写。起初不理解直径不一定经过根节点。根据示......
  • C语言学习-char型数据
    字符型数据1.1字符型常量用单引号括起来的一个字符型常量,且只能包含一个字符,例如'a'、'A'、'1'、''是正确的字符型常量,而'abc'、"a"是错误的字符型常量。1.2字符型变量Markdown更多语法一个字符型常量存放到一个字符型变量中时,实际上并不是把该字符的字型放到内存中,而是把该......
  • 代码随想录算法训练营第12天 | 树的遍历
    (本合集全部为Go语言实现)相关文章链接:递归遍历迭代遍历统一迭代法相关视频链接:Leetcode94状态:实现过程中的难点:迭代法的模拟过程比较难想个人写法递归方式funcinorderTraversal(root*TreeNode)[]int{varres[]intinorderTraversal0(root,&res)return......
  • 二叉树面试题解析
    二叉树面试题解析判断相同的树/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNode......
  • 手写topN算法-c语言
    #include<stdio.h>#include<malloc.h>structTreeHeap{intv;};typedefstructTreeHeapTreeHeap;staticvoidprint_bp(intbp[],intlen);voidcreate_treeheap(TreeHeap*treeheap,intdata[10],intbp[11]){treeheap->v=1;......
  • 结构体变量的定义和初始化、结构体内存对齐——《初学C语言第44天》
    //////5.——————结构体变量的定义和初始化////——定义////方式1//structPoint//{// intx;// inty;//}p1;//声明类型的同时定义变量p1////方式2//structPoint//{// intx;// inty;//};//intmain()//{// structPointp2;//定义结构体变量p2// return0......
  • 算法学习Day18左下角的值,路径总和,构建二叉树
    #Day18左下角的值,路径总和,构建二叉树`ByHQWQF2023/12/30`##笔记***##513.找树左下角的值给定一个二叉树的**根节点**`root`,请找出该二叉树的 **最底层 最左边**节点的值。假设二叉树中至少有一个节点。**示例2:****输入:**\[1,2,3,4,null,5,6,null,null,7]**......
  • C语言实现井字棋
    首先简述一下:九宫格的棋盘,连成三个连续的即为胜现在拆分三子棋的步骤(1)打印菜单,1开始0退出(2)初始化棋盘(3)打印棋盘(4)玩家下棋,子为’*’(5)判断(6)电脑下棋,为‘#’(7)判断(8)返回步骤三现在分析过后,对其进行编写写game.h(头文件)game.c(游戏主体,函数文件) test.c(测试)我们创建的棋盘大致为下边......
  • C语言小案例
    二维数组输出题目描述:输入一个整数N,输出一个N行N列的二维矩阵,矩阵中的元素用\1~N*N顺序螺旋填充。输入格式一个整数N(N<=10)输出格式输出N行N列的矩阵,元素之间用一个空格隔开,行末不要有多余的空格。样例输入数据3输出数据123894765代码示例如下:#include<stdio.h>voids......