二叉树的顺序存储结构

  • 通过拼接方式，用一维数组存储一棵二叉树

若结点的索引为 i ，则该结点的左子结点索引为 2i+1 ，右子节点索引为 2i+2

只会用顺序结构来存储完全二叉树或满二叉树，其他类型二叉树比较浪费空间

二叉树链式存储结构

  • left存储左子结点的地址，right存储右子结点的地址
1
2
3
4
5
6
7
typedef struct TreeNode{
    char data; //数据域  存放的字符
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef TreeNode* BiTree;//Bitree是TreeNode的别名

二叉树的前序遍历

  • 遍历顺序：根，左，右
  • 左：指的是左子树，先打印左半部分，而不是最近的左子结点
1
2
3
4
5
6
7
8
9
// 递归思维
void preOrderTraversal(Bitree root){//确定参数，根结点root
    if(root == NULL){//确定终止条件，遇到空结点遍历停止
        return;
    }
    printf("%c", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

二叉树的中序遍历

  • 遍历顺序：左、根、右
1
2
3
4
5
6
7
8
void inOrderTraversal(BiTree root){
    if(root == NULL){
        return;
    }
    inOrderTraversal(root->left);
    printf("%c",root->data);
    inOrderTraversal(root->right);
}
  • eg：遍历结果：DBEAC

二叉树的后序遍历

  • 遍历顺序：左、右、根
1
2
3
4
5
6
7
8
void postOrderTraversal(BiTree root){
    if(root == NULL){
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%c",root->data);
}
  • 根据上图，后序遍历结果为DEBCA

非递归方法实现遍历

二叉树前序遍历（使用栈实现）

  • 根节点入栈
  • 栈顶结点出栈，打印输出当前栈顶节点
  • 把当前的节点的右孩子、左孩子入栈（栈的特点，后进先出，保持输出为根左右就要保证右先入栈）
  • 重复2-3步，直至栈空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void preOrderTraversal(Bitree root){
    initStack(&stack);//初始化
    push(&stack,root);//根节点入栈
    while(!isEmpty(&stack)){//while循环：取出栈顶元素
        Bitree current = pop(&stack);//current当前栈顶元素
        printf("%c",current->data);//处理根节点
        if(current->right !=NULL){//右孩子入栈
            push(&stack,current->right);
        }
        if(current->left != NULL){//左孩子入栈
            push(&stack,current->left);
        }
    }
}

后序遍历

  • 遍历顺序：左、右、根
  • 经过两次颠倒可以实现前序遍历转化为后序遍历,通过第二个栈实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void preOrderTraversal(Bitree root){
    Stack s1,s2;
    initStack(&s1);//初始化
    initStack(&s2);//用来颠倒顺序的
    push(&s1,root);//根节点入栈
    while(!isEmpty(&s1)){//while循环：取出栈顶元素
        Bitree current = pop(&s1);//current栈顶元素出栈
        push(&s2,current);//存储到s2栈中
        if(current->left !=NULL){//左孩子入栈
            push(&s1,current->left);
        }
        if(current->right != NULL){//右孩子入栈
            push(&s1,current->right);
        }
    }
    while(isEmpty(&s2)){
        BiTree current = pop(&s2);
        printf("%c",current->data);
    }//将第二个栈中的元素依此出栈
}

中序遍历（最难）

无法通过前序遍历和后序遍历得到

  • 不停的往左访问，每访问一个节点入栈
  • 如果访问到空节点，就从栈中取出元素，打印输出
  • （当左边走到尽头）访问右孩子并入站，如果右孩子为空，就从栈中取出元素，打印输出
  • 重复1-3步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void inOrderTraversal(Bitree root){
    Stack s;
    initStack(&s);
    Bitree current = root;
    while(current != NULL || idEmpty(&s)){
        //一直向左遍历，将节点入栈
        while(current != NULL){
            push(&s,current);
            current = current->left;
        }
        //左子树为空是，去除栈顶元素并访问
        current = pop(&s);
        printf("%c",current->data);
        //转向右子树
        current = current->right;
    }
}