数据结构—【二叉树（深度优先遍历）】重难点
关注我
重点：
使用栈的遍历算法思想
非递归算法的实现
难点：
非递归算法的实现及栈的思想
1. 先序遍历
void preorderNonrecursion(BTNode *bt){if(bt != NULL){// 定义一个栈BTNode *Stack[MaxSize];// 指针设为-1,第一个元素在0处int top = -1;// 再设一个结点pBTNode *p;// 将根节点入栈Stack[++top] = bt;// 孩子不空则进行入栈和出栈while(top!=-1){// 将根节点出栈p = Stack[top--];// 访问根节点,相当于输出Visit(p);// 先放右孩子，再放左孩子，访问的顺序就为左孩子，右孩子，符合先序遍历。if(p -> rchild != NULL )Stack[++top] = p ->rchild;if(p -> lchild != NULL )Stack[++top] = p ->lchild;}}}
2. 中序遍历
void inorderNonrecursion(BTNode *bt){if(bt != NULL){// 定义一个栈BTNode *Stack[MaxSize];// 指针设为-1,第一个元素在0处int top = -1;// 再设一个结点pBTNode *p;p = bt;while(top!=-1 || p!=NULL){// 找到最左孩子，并将左一侧孩子都入栈while(p!=NULL){Stack[++top] = p;p = p -> lchild;}if(top!=-1){p = Stack[top--];Visit(p);p = p ->rchild;}}}}
3. 后序遍历
void postorderNonrecursion(BTNode *bt){if(bt != NULL){// 定义两个栈BTNode *Stack1[MaxSize];BTNode *Stack2[MaxSize];// 指针设为-1,第一个元素在0处int top1 = -1;int top2 = -1;// 再设一个结点pBTNode *p = NULL;// 将根节点入栈Stack[++top1] = bt;// 孩子不空则进行入栈和出栈while(top1 !=-1){// 这里使用先序遍历入栈1p = Stack1[top1--];// 紧接着入栈2Stack2[++top2] = p;if(p -> lchild != NULL)Stack1[++top1] = p ->lchild;if(p -> rchild != NULL)Stack1[++top1] = p ->rchild;}// 最后全部逆序，出一个，打印一个while(top2 != -1){p = Stack[top2--];Visit(p);}}}