Icoding题解

题干

先序遍历

已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法：
void pre_order(BiTree root);

在遍历过程中，pre_order函数需要调用 visit_node 函数来实现对结点的访问，该函数声明如下：
void visit_node(BiTNode *node);

二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

遍历所使用栈的相关操作如下：

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

分析

简要分析题干：
利用栈进行非递归的先序遍历。
应当注意的问题：
1. 先序遍历：先访问根结点，再访问左子树，最后访问右子树
2. 非递归的先序遍历方法
3. 栈的基本操作
4. 树的基本概念与基本操作
解题思路：
1. 一直对左结点向下访问
2. 每次访问都将结点存到栈中
3. 一旦指针指向为空，就出栈元素，访问其右结点

注释代码

void pre_order(BiTree root) {
    if (root == NULL)
        return;
    //先声明一个栈用于之后的使用
    Stack S;
    init_stack(&S);

    //首先获取根
    BiTree CurrNode = root;
    //循环的条件是 当前指针指向的不是空结点，而且栈不为空
    while (CurrNode != NULL || !is_empty(&S)) {
        //如果指向的不是空结点
        //这说明依然有左子树没有访问完成
        //我们需要继续向左下访问，直到为空
        if (CurrNode != NULL) {
            visit_node(CurrNode);
            push(&S, CurrNode);
            CurrNode = CurrNode->left;
        }
        //左子树为空了，此时我们访问了某个树的根和左子树
        //接下来就需要访问右子树，这也是先序遍历的要求
        else {
            //这一步是出栈，我们回溯到左儿子的根，访问根的右节点
            pop(&S, &CurrNode);
            CurrNode = CurrNode->right;
        }
    }
}

完整代码

void pre_order(BiTree root){
    Stack S;
    init_stack(&S);
    
    while(root != NULL || !is_empty(&S))
    {
        if(root != NULL)
        {
            visit_node(root);
            push(&S, root);
            root = root->left;
        }
        else
        {
            pop(&S, &root);
            root = root->right;
        }
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。