【数据结构】二叉树前序遍历(非递归)

xiaoxiao2023-03-22  42

前序遍历的顺序:根-左-右

思路分析:

非递归的二叉树前序遍历大的思想分为:①访问它的左路节点;②访问左路节点的右子树

具体非递归的实现思路如下:   ①拿到根节点,然后将其入栈,再看它的左子树是否为空;  ②若左子树不为空,则把此时左子树作为当前节点,重复操作①;  ③当左子树为空时,让栈顶节点出栈,但不输出,并去访问出栈节点的右子树,看其是否为空;  ④若出栈节点的右子树不为空,则取出节点,循环到操作①;  ⑤如果出栈节点的右子树为空,则继续出栈,但不输出,同时将出栈节点的右子树置为当前节点,看其是否为空,重复操作④和⑤;  ⑥直到当前节点为NULL并且栈空,遍历结束。 

具体实现代码如下:

void BinaryTreePrevOrderNonR(BTNode* root)//前序遍历的非递归 { Stack st; StackInit(&st,10); BTNode* cur = root; while (cur || StackEmpty(&st) != 0) { //开始访问一棵树 //1.先访问树的左路节点 while (cur) { printf("%c ", cur->_data); StackPush(&st, cur); cur = cur->_left; } BTNode* top = StackTop(&st); StackPop(&st); //2.访问左路节点的右子树 cur = top->_right; } printf("\n"); }

 

转载请注明原文地址: https://www.6miu.com/read-4987488.html

最新回复(0)