树

二叉树

二叉树是一种非线性数据结构，体现了“一分为二”的分治逻辑。与链表类似，其基本单元是节点每个节点包含值和左右两个节点引用。

C语言实现二叉树如下：

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

// 构造函数
TreeNode *newTreeNode(int val){
    TreeNode *node;
    node=(TreeNode*)malloc(sizeof(TreeNode));
    node->val=val;
    node->height=0;
    node->left=NULL;
    node->right=NULL;
    return node;
}

二叉树常见术语

1. 根节点
   位于二叉树顶层的节点，没有父节点
2. 叶节点
   没有子节点的节点，其两个指针均指向None
3. 边
   连接两个节点的线段，即节点引用（指针）
4. 节点所在的层
   从顶至底递增，根节点所在层为 1
5. 节点的度
   节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2
6. 二叉树的高度
   从根节点到最远叶节点所经过的边的数量
7. 节点的深度
   从根节点到该节点所经过的边的数量
8. 节点的高度
   从距离该节点最远的叶节点到该节点所经过的边的数量

二叉树基本操作

初始化

直接调用上文中的newTreeNode()函数即可。

// 初始化节点
TreeNode *n1=newTreeNode(1);
TreeNode *n2 = newTreeNode(2);
TreeNode *n3 = newTreeNode(3);
TreeNode *n4 = newTreeNode(4);
TreeNode *n5 = newTreeNode(5);
// 构建节点间的引用
n1->left=n2;
n1->right=n3;
n2->left=n4;
n2->right=n5;

插入与删除节点

类比链表，可通过修改指针实现。

TreeNode *P=newTreeNode(0);
// 在n1->n2中插入P
n1->left=P;
P->left=n2;
// 删除P
n1->left=n2;
free(P);

常见的二叉树类型

完美二叉树

所有层的节点都被完全填满的二叉树被称为完美二叉树或满二叉树。在完美二叉树中，叶节点的度为$0$，其余所有节点的度均为$2$，而且若树高为$h$，则节点总数为$2^{h+1}-1$，呈现标准的指数级关系。

完全二叉树

其仅允许最底层的节点不被完全填满，且必须从左至右依次连续填充。

完美二叉树也是一棵完全二叉树。

完满二叉树

其除了叶节点外其余所有节点都有两个子节点，即也满足叶节点的度为$0$，其余所有节点的度均为$2$。

平衡二叉树

其任意节点的左子树和右子树高度差的绝对值不超过1。

二叉树的退化

当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。

链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至$O(n)$

如下表所示，在最佳结构和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大值或极小值。

项目	完美二叉树	链表
第 i 层的节点数量	(2^{i-1})	1
高度为 h 的树的叶节点数量	(2^h)	1
高度为 h 的树的节点总数	(2^{h+1}-1)	(h+1)
节点总数为 n 的树的高度	(\log_2(n+1)-1)	(n-1)

二叉树遍历

层序遍历

这种方式从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的方式访问节点。层序遍历属于广度优先遍历（广度优先搜索），它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：

int *levelOrder(TreeNode *root,int *size){
    int front,rear;
    int index,*arr;
    TreeNode *node;
    TreeNode **queue;
    queue=(TreeNode**)malloc(sizeof(treeNode*)*MAX_SIZE);
    front=0,rear=0;
    queue[rear++]=root;
    arr=(int*)malloc(sizeof(int)*MAX_SIZE);
    index=0;
    while(front<rear){
        node=queue[front++];            // 队列出队
        arr[index++]=node->val;         // 保存节点值
        if(node->left!=NULL){
            queue[rear++]=node->left;   // 左子节点入队
        }
        if(node->right!=NULL){
            queue[rear++]=node->right;  // 右子节点入队
        }
    }
    *size=index;
    arr=realloc(arr,sizeof(int_*(*size)));  // 将数组大小精确缩减至刚好够装所有数据

    free(queue);
    return arr;
}

该算法的时间和空间复杂度均为$O(n)$

前、中、后序遍历

这几种遍历都属于深度优先遍历（深度优先搜索），它体现了一种“先走到尽头，再回溯继续”的遍历方式。

深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

深度优先搜索通常基于递归实现:

// 前序遍历
void preOrder(TreeNode *root,int *size){
    if(root==NULL)
        return;
    arr[(*size)++]=root->val;
    preOrder(root->left,size);
    preOrder(root->right,size);
}
// 中序遍历
void inOrder(TreeNode *root,int *size){
    if(root==NULL)
        return;
    inOrder(root->left,size);
    arr[(*size)++]=root->val;
    inOrder(root->right,size);
}
// 后序遍历
void postOrder(TreeNode *root,int *size){
    if(root==NULL)
        return;
    postOrder(root->left,size);
    postOrder(root->right,size);
    arr[(*size)++]=root->val;
}

这种遍历方式的时间复杂度为$O(n)$，树退化为链表时的最差情况下系统占用的栈帧空间为$O(n)$。

二叉树的数组表示

二叉树可以用数组表示，完美二叉树可以按顺序将每个元素放入数组，而其他类型的二叉树可以通过将空缺位对应的数组元素置为空实现，如下图所示：

用该方法表示完全二叉树时可以省略存储所有None。

用数组表示的这种表示方法有如下的优点：

1. 其存储在连续的内存空间中，对缓存友好，访问和遍历的速度较快。
2. 无需存储指针，比较节省空间。
3. 允许随机访问节点。
   但是存在如下缺点：
4. 其需要连续的内存空间进行存储，故不适合存储数据量过大的树。
5. 增删节点需要通过数组的插入与删除操作是实现，效率较低。
6. 当二叉树中存在大量None时空间利用率低

代码实现：

typedef struct{
    int*tree;
    int size;
}ArrayBinaryTree;

// 构造函数
ArrayBinaryTree *newArrayBinaryTree(int *arr,int arrSize){
    ArrayBinaryTree*abt=(ArrayBinaryTree*)malloc(sizeof(ArrayBinaryTree));
    abt->tree=malloc(sizeof(int)*arrSize);
    memcpy(abt->tree,arr,sizeof(int)*arrSize);
    abt->size=arrSize;
    return abt;
}

// 析构函数
void delArrayBinaryTree(ArrayBinaryTree *abt){
    free(abt->tree);
    free(abt);
}

// 列表容量
int size(ArrayBinaryTree *abt){
    return abt->size;
}

// 获取索引为i的节点值
int val(ArrayBinaryTre*abt,int i){
    if(i<0||i>=size(abt))
        return INT_MAX;
    return abt->tree[i];
}

// 层序遍历
int *levelOrder(ArrayBinaryTree *abt，int *returnSize){
    int *res=(int*)malloc(sizeof(int)*size(abt));
    int index=0;
    for(int i=0;i<size(abt);i++){
        if(val(abt,i)!=INT_MAX)
            res[index++]=val(abt,i);
    }
    *returnSize=index;
    return res;
}

// 深度优先遍历
void dfs(ArrayBinaryTree *abt,int i,char *order,int *res,int*index){
    if(val(abt,i)==INT_MAX)
    return;
    if(strcmp(order,"pre")==0)
        res[(*index)++]=val(abt,i);
    dfs(abt,left(i),order,res,index);
    if(strcmp(order,"in")==0)
        res[(*index)++]=val(abt,i);
    dfs(abt,right(i),order,res,index);
    if(strcmp(order,"post")==0)
        res[(*index)++]=val(abt,i);  
}

/* 前序遍历 */
int *preOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "pre", res, &index);
    *returnSize = index;
    return res;
}

/* 中序遍历 */
int *inOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "in", res, &index);
    *returnSize = index;
    return res;
}

/* 后序遍历 */
int *postOrder(ArrayBinaryTree *abt,int *returnSize){
    int*res=(int*)malloc(sizeof(int)*size(abt));
    int index=0;
    dfs(abt,0,"post",res,&index);
    *returnSize=index;
    return res;
}

注：本文是作者阅读《hello算法》一书的读书笔记，内容会与原书有重合，特此声明。