一、递归

#include "stdlib.h"
#include "stdio.h"
typedef struct TNode
{
 int value;
 struct TNode *left, *right;
} TNode;

char * str=NULL;
//从序列化字符串中获取输入
int getvalue()
{
 if(str == NULL)
 return 0;
 if(str[0] == '#')
 {
 str = &str[2];
 return -1;
 }
 int index = strcspn(str,"!");
 char* svalue = (char*)malloc((index+1));
 strncpy(svalue,str,index);
 svalue[index] = '\0';
 str = &str[index+1];
 return atoi(svalue);
}

//前序反序列化树
TNode * initTree()
{
 int value = getvalue();
 if(value == -1)
 return NULL;
 TNode *node = (TNode*)malloc(sizeof(TNode));
 if(!node)
 exit(0);
 node->value = value;
 node->left = initTree();
 node->right = initTree();
 return node;
}

//访问节点
void visit(TNode* T)
{
 if(T)
 printf("%d!", T->value);
 else
 printf("#!");
}
//先序序列化
void PPrintTree(const TNode* T,void (*fun)())
{
 (*fun)(T);
 if(T)
 {
 PPrintTree(T->left,*fun);
 PPrintTree(T->right,*fun);
 }
}
//中序序列化
void MPrintTree(const TNode* T,void(*fun)())
{
 if(T) 
 MPrintTree(T->left,*fun);
 (*fun)(T);
 if(T) 
 MPrintTree(T->right,*fun);
}
//后续序列化
{
 if(T)
 {
 EPrintTree(T->left,*fun);
 EPrintTree(T->right,*fun);
 }
 (*fun)(T);
}

int main(int argc, char const *argv[])
{
 str = "11!12!13!18!#!#!#!14!#!19!#!#!15!16!#!#!17!#!100!#!#!";
 //char tmp[1024];
 //scanf("%s",tmp);
 //str = tmp;
 TNode * T = initTree();
 printf("\n 先序：");
 PPrintTree(T,visit);
 printf("\n 中序：");
 MPrintTree(T,visit);
 printf("\n 后序：");
 EPrintTree(T,visit);
 printf("\n");
 return 0;
}

二、非递归

/*
 * 如何不用栈，也不用递归来实现二叉树的中序遍历。
 * 这个问题的实现就是迭代器问题，无论是Java 还是C++，利用迭代器遍历树节点(Java 中是TreeMap 类.C++中是map 类）
 * 都使用了中序遍历，且无法使用递归和栈，算法效率近似为O(1)，不可能每个节点只访问一次。
 * 节点中会多一个指向父节点的指针。
*/
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include <stack>
#include <queue>
typedef struct TNode
{
 int value;
 struct TNode *left, *right;
} TNode;

char * str="11!12!13!18!#!#!#!14!#!19!#!#!15!16!#!#!17!#!100!#!#!";

//从序列化字符串中获取输入
int getvalue()
{
 if(str == NULL)
 return 0;
 if(str[0] == '#')
 {
 str = &str[2];
 return -1;
 }
 int index = strcspn(str,"!");
 char* svalue = (char*)malloc((index+1));
 strncpy(svalue,str,index);
 svalue[index] = '\0';
 str = &str[index+1];
 return atoi(svalue);
}

//前序反序列化树
TNode * initTree()
{
 int value = getvalue();
 if(value == -1)
 return NULL;
 TNode *node = (TNode*)malloc(sizeof(TNode));
 if(!node)
 exit(0);
 node->value = value;
 node->left = initTree();
 node->right = initTree();
 return node;
}

//先序遍历
void PPrintTree( TNode* T)
{
 if(T==NULL)
 return;
 std::stack<TNode*> nodeStack;
 TNode *p = T;
 while(p || !nodeStack.empty())
 {
 visit(p);
 if(p){
 nodeStack.push(p);
 p = p->left;
 }
 else{
 p = nodeStack.top();
 nodeStack.pop();
 p = p->right;
 }
 }
}

//中序遍历
void MPrintTree( TNode* T)
{
 if(T == NULL)
 return;
 std::stack<TNode*> nodeStack;
 TNode* p = T;
 while(p || !nodeStack.empty())
 {
 if(p) {
 nodeStack.push(p);
 p=p->left;
 } else {
 p=nodeStack.top();
 nodeStack.pop();
 visit(p);
 p = p->right;
 }
 }
}

//后续遍历
void EPrintTree(TNode* T)
{
 if(T == NULL)
 return;
 std::stack<TNode*> nodeStack;
 TNode* p = T;
 while(p || !nodeStack.empty())
 {
 if(p){
 nodeStack.push(p);
 p=p->left;
 }
 else{
 TNode* pre = NULL; //上一个被访问的
 p=nodeStack.top();
 while(!nodeStack.empty() && p->right == pre && nodeStack.size()!=0)
 {
 p = nodeStack.top();
 nodeStack.pop();
 visit(p);
 pre = p;
 if(!nodeStack.empty()) //此处要注意，不然根节点时，栈为空会报错
 p = nodeStack.top();
 }
 if (!nodeStack.empty())
 p = p->right;
 else
 p=NULL; //作为while 的结束，p==NULL&&nodeStack.empty()
 }
 }
}

//非递归后序遍历
/*要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；
或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和
左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。*/
void EPrintTree2(TNode *root)     
{
    std::stack<TNode*> s;
    TNode *cur;                      //当前结点 
    TNode *pre=NULL;                 //前一次访问的结点 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if( (cur->left==NULL&&cur->right==NULL) || (pre!=NULL&&(pre==cur->left||pre==cur->right)))
        {
         visit(cur); //如果当前结点没有孩子结点或者孩子节点都已被访问过 
            s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->right!=NULL)
                s.push(cur->right);
            if(cur->left!=NULL)    
                s.push(cur->left);
        }
    }    
}

//层次遍历
void CPrintTree(TNode* T)
{
 if(T==NULL)
 return;
 std::queue<TNode*> nodeQueue;
 TNode* p = T;
 nodeQueue.push(p);
 while(!nodeQueue.empty())
 {
 p=nodeQueue.front();
 nodeQueue.pop();
 if(p->left)
 nodeQueue.push(p->left);
 if(p->right)
 nodeQueue.push(p->right);
 visit(p);
 }
}

int main(int argc, char const *argv[])
{
 TNode* T = initTree();
 printf("\n 前序遍历：");
 PPrintTree(T);
 printf("\n 中序遍历：");
 MPrintTree(T);
 printf("\n 后序遍历：");
 EPrintTree(T);
 printf("\n 层次遍历：");
 CPrintTree(T);
 printf("\n");
 return 0;
}

转载标明出处：https://blog.evanxia.com/2015/11/1016