数据结构重学日记（十八）二叉树先序遍历

概念

二叉树的遍历，是指从根结点出发，按某种次序依次访问树中的每个结点，使得每个结点均 被访问一次，而且仅被访问一次。

二叉树的遍历又分为先序遍历、中序遍历、后序遍历和层次遍历。

先序、中序和后序又可以分为递归和非递归。

这里先来实现下先序遍历。

先序遍历递归

如果二叉树为空，什么也不做，否则：

• 先访问根结点
• 先序遍历左子树
• 先序遍历右子树

即从上到下、从左到右。

二叉树

以上图的树为例：

遍历顺序为：
A -> B -> D -> G -> C -> E -> F

在代码中，当遇到 # 号时将对应树置为空，所以输入时直接输入一下字符串：
ABD#G###CE##F##

bool created_tree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        BiTree p = (BiTree) malloc(sizeof(BiNode));
        if (T == NULL) {
            printf("创建节点失败，无法分配可用内存...");
            exit(-1);
        } else {
            p->data = ch;
            *T = p;
            created_tree(&p->lchild);
            created_tree(&p->rchild);
        }
    }
    return true;
}


void foreach_tree(BiTree T) {
    if (T != NULL) {
        printf("%c ", T->data);
        foreach_tree(T->lchild);
        foreach_tree(T->rchild);
    }
    printf("\r\n\r\n");

}

本来是想把几种遍历都做一遍，但是太困了，眼睁不开，遍历创建也卡了很久才弄出来，还是先只做一个吧，明天看状态再继续往下做。

我要睡了。