以下面这棵树为例：
#include <bits/stdc++.h> #define SIZE 100 using namespace std; typedef struct BiTNode //定义二叉树节点结构 { char data; //数据域 struct BiTNode *lchild,*rchild; //左右孩子指针域 } BiTNode,*BiTree; //建立二叉树 void CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); //读入一个字符 if(ch=='*') T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点 T->data=ch; CreateBiTree(T->lchild); //生成左子树 CreateBiTree(T->rchild); //生成右子树 } } //先序遍历的递归 void PreOrder(BiTree T) { if(T) { printf("%c ",T->data); //访问结点 PreOrder(T->lchild); //遍历左子树 PreOrder(T->rchild); //遍历右子树 } } void InOrder(BiTree T) { if(T) { InOrder(T->lchild); printf("%c ",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ",T->data); } } void InOrderTraverse(BiTree T) { stack<BiTree> S; BiTree p; S.push(T); while(!S.empty()) { while((p=S.top())&&p) { printf("%c ",p->data); S.push(p->lchild); } S.pop(); if(!S.empty()) { p=S.top(); S.pop(); S.push(p->rchild); } } } int visit (BiTree T) { if(T) { printf("%c ",T->data); return 1; } else return 0; } void LeverTraverse(BiTree T) { queue<BiTree> Q; BiTree p; p=T; if(visit(p)==1) Q.push(p); while(!Q.empty()) { p=Q.front(); Q.pop(); if(visit(p->lchild)==1) Q.push(p->lchild); if(visit(p->rchild)==1) Q.push(p->rchild); } } int main() { BiTree T; char j; int flag=1; printf("本程序实现二叉树的操作：\n"); printf("叶子节点以空格表示。\n"); printf("可以进行二叉树，递归先序，中序，后序遍历，非递归先序，中序遍历，及非递归层序遍历等操作。\n"); printf("请建立二叉树。\n"); printf("例如:1 2 3 4 5 6 (回车)\n"); CreateBiTree(T); //初始化队列 getchar(); while(flag) { printf("\n"); printf("请选择: \n"); printf("1.递归先序遍历\n"); printf("2.递归中序遍历\n"); printf("3.递归后序遍历\n"); printf("4.非递归中序遍历\n"); printf("5.非递归先序遍历\n"); printf("6.非递归层序遍历\n"); printf("0.退出程序\n"); scanf(" %c",&j); switch(j) { case '1': if(T) { printf("递归先序遍历二叉树:"); PreOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '2': if(T) { printf("递归中序遍历二叉树:"); InOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '3': if(T) { printf("递归后序遍历二叉树:"); PostOrder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '4': if(T) { printf("非递归中序遍历二叉树:"); InOrderTraverse(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '5': if(T) { printf("非递归先序遍历二叉树:"); InOrderTraverse(T); printf("\n"); } else printf("二叉树为空!\n"); break; case '6': if(T) { printf("非递归层序遍历二叉树:"); LeverTraverse(T); printf("\n"); } else printf("二叉树为空!\n"); break; default: flag=0; printf("程序运行结束，按任意键退出!\n"); } } }