9.树【遍历】

第一章 自测&关键词回顾

栈实现遍历: 前序 中序 后序

• 用栈实现遍历
  • 前中序: 一直找左,只是打印的地方不一样
  • 后序: 打印同前序; 但一直找右,翻转打印结果(可以借助栈)
    

第一节 自测

第一部分【树中常见的定义】

第二节 关键词回顾

1.2.1 【树中常见的定义】层数，深度，高度，度

1.2.2【树中常见的定义】节点个数，边数，所有节点度数之和

1.2.3【树中常见的定义】满, 完全二叉树, 高度h和节点n的关系

1.2.4【遍历】树的遍历

1.2.5【遍历】森林的遍历

879真题, 还要你写代码咯

第二章 手撕

• tree.h
• tree.c
• test.h

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 100

typedef char DataType;
typedef struct TreeNode {
    DataType data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

// 1.创建树(前序序列的顺序)
void createTree(TreeNode **tree);
// 2.前序遍历
void preOrder(TreeNode *tree);
// 3.中序遍历
void inOrder(TreeNode *tree);
// 4.后续遍历
void postOrder(TreeNode *tree);
// 5.[栈]前序遍历
void preOrderWithStack(TreeNode *tree);
// 6.[栈]中序遍历
void inOrderWithStack(TreeNode *tree);
// 7.[栈]后续遍历
void postOrderWithStack(TreeNode *tree);
// 8.层次遍历
void levelOrder(TreeNode *tree);

#include "tree.h"

// 1.创建树(前序序列的顺序)
void createTree(TreeNode **tree) {
    char input;
    while (scanf("%c", &input) == 1 && input != '\n') {
        if (input == '#') {
            *tree = NULL;  // 当前节点是空的
            return;
        } else {
            // 创建节点
            TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
            newNode->data = input;
            newNode->lchild = NULL;
            newNode->rchild = NULL;
            *tree = newNode;
            createTree(&(*tree)->lchild);
            createTree(&(*tree)->rchild);
            return;  // 在循环里面,所以要显式return
        }
    }
}
// 2.前序遍历
void preOrder(TreeNode *tree) {
    if (tree != NULL) {
        printf("%c ", tree->data);
        preOrder(tree->lchild);
        preOrder(tree->rchild);
    }
}
// 3.中序遍历
void inOrder(TreeNode *tree) {
    if (tree != NULL) {
        inOrder(tree->lchild);
        printf("%c ", tree->data);
        inOrder(tree->rchild);
    }
}
// 4.后序遍历
void postOrder(TreeNode *tree) {
    if (tree != NULL) {
        postOrder(tree->lchild);
        postOrder(tree->rchild);
        printf("%c ", tree->data);
    }
}
TreeNode *stack[SIZE];
int top = -1;
// 5.[栈]前序遍历
void preOrderWithStack(TreeNode *tree) {
    top = -1;
    TreeNode *pmove = tree;
    while (top != -1 || pmove != NULL) {
        if (pmove == NULL) {
            pmove = stack[top--]->rchild;  // 没左了,取栈顶的右边孩子(开始向右走)
        }
        // 还有左
        else {
            printf("%c ", pmove->data);
            stack[++top] = pmove;   //  入栈当前节点
            pmove = pmove->lchild;  // 继续往左
        }
    }
}
// 6.[栈]中序遍历
void inOrderWithStack(TreeNode *tree) {
    top = -1;
    TreeNode *pmove = tree;
    while (top != -1 || pmove != NULL) {
        if (pmove == NULL) {
            printf("%c ", stack[top]->data);  // 没有左了,pmove已经到NULL了,说明栈顶(上一个入的)就是最左的,打印他
            pmove = stack[top--]->rchild;     // 没有左,就只能向右了;
        }
        // 还有左
        else {
            stack[++top] = pmove;
            pmove = pmove->lchild;
        }
    }
}
// 7.[栈]后续遍历
void postOrderWithStack(TreeNode *tree) {
    top = -1;
    TreeNode *pmove = tree;
    char printStack[100];
    int pTop = -1;
    while (top != -1 || pmove != NULL) {
        if (pmove == NULL) {
            pmove = stack[top--]->lchild;
        } else {
            printStack[++pTop] = pmove->data;  // 打印位置同"前序"
            stack[++top] = pmove;
            pmove = pmove->rchild;  // 一直找右
        }
    }
    // 翻转打印
    while (pTop != -1) {
        printf("%c ", printStack[pTop--]);
    }
}

TreeNode *queue[SIZE];
int hh = 0, tt = -1;  // 这里我们采用普通队列
// 回顾下:hh = 0, tt = 0; 循环队列=>空?hh==tt; 满?(tt+1)%SIZE==hh; 出入队:(tt/hh+1)%SIZE
// 8.层次遍历
void levelOrder(TreeNode *tree) {
    hh = 0, tt = -1;  // 初始化队列
    queue[++tt] = tree;
    while (hh <= tt) {
        TreeNode *temp = queue[hh++];  // 出队
        printf("%c ", temp->data);
        if (temp->lchild != NULL) {
            queue[++tt] = temp->lchild;
        }
        if (temp->rchild != NULL) {
            queue[++tt] = temp->rchild;
        }
    }
}

#include "tree.h"

void test01(void) {
    TreeNode *tree = NULL;
    createTree(&tree);
    preOrder(tree);
    puts("");
    inOrder(tree);
    puts("");
    postOrder(tree);
    puts("");
    puts("=================");
    preOrderWithStack(tree);
    puts("");
    inOrderWithStack(tree);
    puts("");
    postOrderWithStack(tree);
    puts("");
    puts("=================");
    levelOrder(tree);
}

int main() {
    test01();
    return 0;
}

第三章 相关应用

第四章 上手真题

第五章 比赛怎么用