二叉树四种遍历方法

树

树是一个n个节点的有限集，当n=0时称之为空树

基本概念

性质
1. 树的定义是递归的，树的定义中又用到了自身
2. 树的根节点没有前驱，除根结点外，其他所有节点有且只有一个前驱
3. 树中的所有节点有0个或多个后驱
度
节点拥有的子树数称为结点的度，树的度取各个节点的度的最大值
1. 度为0的节点称为叶节点或终端节点
2. 度不为0的节点成为分支节点或非终端节点，除根节点外，分支节点也称内部节点
层次
1. 根为第一层
2. 树中节点的最大层次称为树的深度或高度
其他概念
如果树中节点的各子树次序不能互换，则称为有序树，否则是为无序树

二叉树

一种特殊的数据结构
每个节点至多两个子树
子树的次序不能改变

二叉树的五种形态

树的五种形态

特殊二叉树

斜树
满二叉树

特点：①叶子只能出现在最下一层 ②非叶子节点的度一定是2
完全二叉树
特点：①叶子节点出现在最下两层 ②最下层叶子一定集中在左部连续位置 ③倒数第二层若有叶子节点一定在右部连续位置 ④如果节点度为1，则该节点只有左孩子 ⑤同样节点数的二叉树，完全二叉树深度最小
tips：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

二叉链表创建

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

四种遍历方法

前序遍历
根-左-右
中序遍历
左-根-右
后序遍历
左-右-根
层序遍历

代码实现

前序、中序、后序遍历基本代码类似，不同点在于遍历根节点、左子树和右子树的顺序
以下注释部分：
①②③为前序遍历，②①③为中序遍历，②③①为后序遍历
分别对应力扣中的144，94，145题

struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };
 
void digui(struct TreeNode* root,int *res,int *returnSize){
    if(root == NULL){
        return;
    }
    res[(*returnSize)++] = root->val;    //①
    digui(root->left, res, returnSize);  //②
    digui(root->right, res, returnSize); ///③
}

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

层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    int **res = (int**)malloc(sizeof(int*)*2001);
    *returnColumnSizes = (int*)malloc(sizeof(int)*2001);
    *returnSize = 0;
    if(root == NULL){
        return res;
    }
    
	//模拟队列
    struct TreeNode **queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*2001);
    
    int head = 0, rear = 0;//两个指针分别指向队列的头尾
    queue[rear++] = root;//先录入根节点

	//判断条件：队列不为空
    while(rear != head){
        int len = rear-head;
        (*returnColumnSizes)[*returnSize] = len;//当前队列长度即为返回的数组列数
        res[*returnSize] = (int*)malloc(sizeof(int)*len);
        for(int i = 0; i < len; i++){
            res[(*returnSize)][i] = queue[head]->val;
            if(queue[head]->left){
                queue[rear++] = queue[head]->left;
            }
            if(queue[head]->right){
                queue[rear++] = queue[head]->right;
            }
            head++;
        }
        (*returnSize)++;//遍历完一层后，对返回的数组行数+1
    }

    return res;
}