网站全屏弹出窗口企业自建网站

二叉树同上一篇的递归遍历：
关于二叉树的非递归遍历，我们可以模拟堆栈：
先序遍历：先访问根节点，然后压入栈中，然后向左访问左子树节点，依次访问并压入栈中，当左子树为空时（如图所示），
获取栈顶元素并弹出栈顶，然后访问右子树（注意右子树不压入栈中），重复以上步骤，二叉树得以遍历。
以下是本人用自己写的栈接口实现的二叉树的非递归遍历（C语言实现）：

#include <stdio.h>
#include <stdlib.h>
#include "Linkstack.h"
struct Person
{struct LinkNode head;int age;struct Person* left;struct Person* right;
};
//中序遍历
void inorderTraversal(struct Person* root)
{if (NULL == root){return;}struct Person* r = root;//创建初始化堆栈Stack stack = Init_LinkStack();//树非空或栈非空while (r || !isEmpty(stack)){//一直向左将节点压入栈中while (r){Push_LinkStack(stack, r);r = r->left;}//如果栈非空，弹出栈顶，节点向右子树移动if (!isEmpty(stack)){r=Top_LinkStack(stack);Pop_LinkStack(stack);printf("%d  ", r->age);r = r->right;}}
}
//先序遍历
void preorderTraversal(struct Person* root)
{if (NULL == root){return;}struct Person* r = root;//创建初始化堆栈Stack stack = Init_LinkStack();//树非空或栈非空while (r || !isEmpty(stack)){//一直向左将左子树压入栈中while (r){printf("%d  ", r->age);Push_LinkStack(stack, r);r = r->left;}//如果栈非空，弹出栈顶，节点向右子树移动if (!isEmpty(stack)){r = Top_LinkStack(stack);Pop_LinkStack(stack);r = r->right;}}
}
//后序遍历
void postorderTraversal(struct Person* root)
{if (NULL == root){return;}struct Person* r = root;//作为节点是否访问的标志struct Person* p = NULL;//创建初始化堆栈Stack stack = Init_LinkStack();//树非空或栈非空while (r || !isEmpty(stack)){//一直向左将左子树压入栈中while (r){Push_LinkStack(stack, r);r = r->left;}//如果栈非空，获取栈顶r = Top_LinkStack(stack);if (r->right && r->right != p)//右子树存在，未被访问{r = r->right;}else {Pop_LinkStack(stack);printf("%d  ", r->age);p = r;         //记录最近访问过的节点r = NULL;    //节点访问完后，重置r指针}}
}

下面是测试代码：

void test()
{struct Person p1 = { 0,1,NULL,NULL };struct Person p2 = { 0,2,NULL,NULL };struct Person p3 = { 0,3,NULL,NULL };struct Person p4 = { 0,4,NULL,NULL };struct Person p5 = { 0,5,NULL,NULL };struct Person p6 = { 0,6,NULL,NULL };struct Person p7 = { 0,7,NULL,NULL };struct Person p8 = { 0,8,NULL,NULL };struct Person p9 = { 0,9,NULL,NULL };struct Person p10 = { 0,10,NULL,NULL };struct Person p11 = { 0,11,NULL,NULL };struct Person p12 = { 0,12,NULL,NULL };struct Person p13 = { 0,13,NULL,NULL };p1.left = &p2;p1.right = &p3;p2.left = &p4;p2.right = &p5;p3.left = &p6;p3.right = &p7;p4.left = &p8;p4.right = &p9;p5.left = &p10;p5.right = &p11;p6.left = &p12;p6.right = &p13;printf("---------非递归先序遍历二叉树---------\n");preorderTraversal(&p1);printf("\n");printf("---------非递归中序遍历二叉树---------\n");inorderTraversal(&p1);printf("\n");printf("---------非递归后序遍历二叉树---------\n");postorderTraversal(&p1);printf("\n");
}
int main(int argc, char** argv)
{test();system("pause");return 0;
}

`在VS2017中代码正确执行：

下面是栈的接口声明：

#pragma once
#ifdef __cplusplus
extern"C" {
#endif // __cplusplus
#include<stdlib.h>//链表节点struct LinkNode{struct LinkNode* next;};//头节点struct LinkStack{struct LinkNode head;int size;};typedef void* Stack;//初始化栈Stack Init_LinkStack();//入栈void Push_LinkStack(Stack stack,void* data);//出栈void Pop_LinkStack(Stack stack);//获取栈顶void* Top_LinkStack(Stack stack);//获取栈的大小int Size_LinkStack(Stack stack);//销毁栈void Destroy_LinkStack(Stack stack);//是否为空int isEmpty(Stack stack);#ifdef __cplusplus
}
#endif // __cplusplus

栈接口的具体实现：

  #include"LinkStack.h"typedef void* Stack;//初始化栈Stack Init_LinkStack(){struct LinkStack* stack = malloc(sizeof(struct LinkStack));if (NULL == stack){return NULL;}stack->head.next= NULL;stack->size = 0;return stack;}//入栈void Push_LinkStack(Stack stack, void* data){if (NULL == stack){return;}if (NULL == data){return;}struct LinkStack* pstack = (struct LinkStack*)stack;struct LinkNode* p = (struct LinkNode*)data;p->next = pstack->head.next;pstack->head.next = p;//p->next = NULL;++(pstack->size);}//出栈void Pop_LinkStack(Stack stack){if (NULL == stack){return;}struct LinkStack* pstack = (struct LinkStack*)stack;if (pstack->size == 0){return;}struct LinkNode* node = pstack->head.next;pstack->head.next = node->next;--(pstack->size);}//获取栈顶void* Top_LinkStack(Stack stack){if (NULL == stack){return NULL;}struct LinkStack* pstack = (struct LinkStack*)stack;if (pstack->size == 0){return NULL;}return pstack->head.next;}int Size_Link(Stack stack){if (NULL == stack){return -1;}struct LinkStack* pstack = (struct LinkStack*)stack;return pstack->size;}//销毁栈void Destroy_LinkStack(Stack stack){if (NULL == stack){return;}free(stack);stack = NULL;}//栈是否为空int isEmpty(Stack stack){if (NULL == stack){return 0;}struct LinkStack* st = (struct LinkStack*)stack;//if(st->size==0)//    return 1;return st->size==0;}//获取栈的大小int Size_LinkStack(Stack stack){if (NULL == stack){return -1;}struct LinkStack* st = (struct LinkStack*)stack;return st->size;}