Chapter3: 更好的查找与排序算法

10. 基础学习：树、二叉树

用数组来表示一棵树

结构分为逻辑结构和物理结构(或存储结构)

存储结构只有两种：顺序存储和和链式存储

用数组来表示1棵树，可以按照从上到下，从左到右的顺序给树编号，这样结点i 的左子结点下标为 2i+1 , 右子结点下标为 2i+2 ，如果其范围超出了数组长度，说明它没有对应的子结点；其父结点为 [(i-1)/2] (实际上整数除法也是下取整) 。

树的遍历方式

树的遍历方式有：

• 先序遍历(根，左子树，右字数)

  从整棵树的根节点开始，遍历完根节点的整棵左子树再遍历其右子树，对于每一个子树而言顺序也是如此(根、左子树，右子树)。其实就是一个递归

• 中序遍 历(左子树，根，右子树)

• 后序遍历(左子树，右子树，根)

"序" 可以理解为 "跟"，"先序"即 "先跟"，"中序"即"中根"，"后序"即"后根"。

如对于下面这棵树：

• 先序 : 78,56,43,2,23,4,34,1,14

• 中序：2,43,23,56,4,78,1,34,15

• 后序 :2,23,43,4,56,1,15,34,78

一棵二叉树

树的遍历方式的代码

先序遍历

/*递归形式的中序遍历
参数：输入数组，数组长度，当前访问子树根结点索引*/
void inOrder(int*arr,int arrLen,int i){
    if(i>arrLen)
        return;
    printf("%d",arr[i]);//根结点
    preOder(arr,arrLen,arr[i*2+1]);//左子树
    preOrder(arr,arrLen,arr[i*2+2]);//右子树
}

中序遍历

/*递归形式的中序遍历
参数：输入数组，数组长度，当前访问子树根结点索引*/
void preOrder(int*arr,int arrLen,int i){
    if(i>arrLen)
        return;
    printf("%d",arr[i*2+1]);//左子树
    preOder(arr,arrLen,arr[i]);//根结点
    preOrder(arr,arrLen,arr[i*2+2]);//右子树
}