二叉树的遍历方式一般有前序、中序、后序三种方式。其中每种方式都可以由递归和非递归实现，非递归主要借助于栈来实现，还可以借助队列实现层级遍历。下面的代码在vs2019编译通过，其中的栈和队列是自己简单实现的。实现思路和代码如下：
#include <iostream> #define _CRT_SECURE_NO_WARNINGS #define STACK_SIZE 100 #define QUEUE_SIZE 100 typedef struct Btree { char data; struct Btree* lChild; struct Btree* rChild; }Btree, *PBtree; //循环队列 class Myqueue { private: PBtree queue[QUEUE_SIZE]; int front, rear; public: Myqueue() { rear = front = 0; } bool IsEmpty() { return rear == front ? true : false; } bool enQueue(const PBtree T) { if ((rear + 1) % QUEUE_SIZE == front) { return false; } queue[rear] = T; rear = (rear + 1) % QUEUE_SIZE; return true; } PBtree deQueue() { if ( rear == front) { return NULL; } PBtree p = queue[front]; front = (front + 1) % QUEUE_SIZE; return p; } }; //栈 class MyStack { private: PBtree stack[STACK_SIZE]; int top; public: MyStack() { top = -1; } bool IsEmpty() { return -1 == top ? true : false; } bool push(const PBtree T) { if (STACK_SIZE - 1 == top ) { return false; } stack[++top] = T; return true; } PBtree pop() { if (-1 == top) { return NULL; } return stack[top--]; } }; //采用前序创建二叉树 void CreateTree(PBtree *T) { char data; scanf_s("%c", &data); if (data == '#') { *T = NULL; return; } else { *T = (PBtree)malloc(sizeof(Btree)); if (!*T) { exit(-1); } (*T)->data = data; CreateTree(&(*T)->lChild); CreateTree(&(*T)->rChild); } } //递归前序遍历 //比较简单 按照根-左-右顺序访问即可 void PreOrder(PBtree T) { if (T) { printf("--%c--", T->data); PreOrder(T->lChild); PreOrder(T->rChild); } } //非递归前序遍历 //思路：初始将根节点入栈，栈不空就继续循环，出栈访问栈顶元素（根结点），再看右子树 //不空入栈，再看左子树，不空入栈（根据栈先入后出的特点） void PreOrderNoRecursion(const PBtree T) { if (!T) return; MyStack stack; PBtree p = T; stack.push(p); while (!stack.IsEmpty()) { p = stack.pop(); printf("--%c--", p->data); if (p->rChild) { stack.push(p->rChild); } if (p->lChild) { stack.push(p->lChild); } } } //递归中序遍历 //左-根-右 void InOrder(PBtree T) { if(T) { InOrder(T->lChild); printf("--%c--", T->data); InOrder(T->rChild); } } //非递归中序遍历 //思路：左子树入栈遍历到最左边，栈不空，则退栈访问栈顶元素(根结点)，再将右子树入栈 //继续循环，注意循环条件为栈不空或者指针不空 void InOrderNoRecursion(const PBtree T) { MyStack stack; PBtree p = T; while (!stack.IsEmpty() || p != NULL) { while(p) //if(p) { stack.push(p); p = p->lChild; } if(!stack.IsEmpty())//else { p = stack.pop();// printf("--%c--", p->data); p = p->rChild; } } } //递归后序遍历 //左-右-根 void PostOrder(PBtree T) { if (T) { PostOrder(T->lChild); PostOrder(T->rChild); printf("--%c--", T->data); } } //非递归后序遍历（方法较多，这里选取最容易理解的一种） //非递归后序遍历和非递归前序遍历存在联系，仔细观察可以得到如下规律： //1栈：调整前序非递归遍历的入栈顺序为 先左后右 //2栈：将前序遍历的访问操作存入2栈，然后输出2栈即可 void PostOrderNoRecursion(const PBtree T) { if (!T) return; MyStack stack1; MyStack stack2; PBtree p = T; stack1.push(p); while (!stack1.IsEmpty()) { p = stack1.pop(); stack2.push(p); if (p->lChild) { stack1.push(p->lChild); } if (p->rChild) { stack1.push(p->rChild); } } while (!stack2.IsEmpty()) { p = stack2.pop(); printf("--%c--", p->data); } } //层次遍历,借助队列实现 //根先入队，出队访问，并按照从左到右依次将子树入队即可，队空退出循环 void LevelOrder(const PBtree T) { Myqueue queue; PBtree p = T; queue.enQueue(p); while (!queue.IsEmpty()) { p = queue.deQueue(); printf("--%c--", p->data); if (p->lChild) { queue.enQueue(p->lChild); } if (p->rChild) { queue.enQueue(p->rChild); } } } int main() { printf("please input string in PreOrder(# is null)!\n"); //abc##d##e#f## /* a / \ b e / \ \ c d f */ PBtree T; CreateTree(&T); printf("\n PreOrder-Recursion:\n"); PreOrder(T); printf("\n PreOrder-No-Recursion:\n"); PreOrderNoRecursion(T); printf("\n InOrder-Recursion:\n"); InOrder(T); printf("\n InOrder-No-Recursion:\n"); InOrderNoRecursion(T); printf("\n PostOrder-Recursion:\n"); PostOrder(T); printf("\n PostOrder-No-Recursion:\n"); PostOrderNoRecursion(T); printf("\n LevelOrder:\n"); LevelOrder(T); return 0; }