info

《数据结构与算法》清华-邓俊辉
https://www.bilibili.com/video/BV1ub411H7PK?p=5

二叉树

二叉树遍历

前序遍历

// 递归版本
void traverse(node){
    while (node){
        visit(node);
        traverse(node->left);
        traverse(node->right);
    }
}
void visitLeftBranch(node, stack){
    while (node){
        visit(node);
        stack.push(node->right);
        node = node -> left;
    }
}
void pre_traverse(node){
    while (true){
        visitLeftBranch(node, stack);
        if (stack.empty()) break;
        node = stack.pop();
    }
}

中序遍历

void goLeftBranch(node, stack){
    while (node) {
        stack.push(node);
        node = node->left;
    }
}
void inorder_traverse(node){
    while (true){
        goLeftBranch(node, stack);
        if (stack.empty()) break;
        node = stack.pop();
        visit(node);
        stack = stack->right;
    }
}