本文共 5443 字，大约阅读时间需要 18 分钟。

在VS2011版本中调试通过。

#include "stdafx.h"#include"Stack.h"//#include
   
    //标准库中定义的栈#include
    
     using namespace std;#define MAX_LEN 15void Create_tree(TreeNode **head, char *pData){    TreeNode *sop[MAX_LEN];    TreeNode *top = NULL;    int i = 0;    int j = 0;    int k = 0;    *head = NULL;    while(pData[i])    {        switch (pData[i])        {            case '(':                j++;                if(j >= MAX_LEN)                {                    printf("-1 \n");                }                sop[j] = top;                k = 1;                break;            case ',':                k = 2;                break;            case ')':                k = 0;                j--;                if(j < 0)                {                    printf("-2\n");                }                break;            case ' ':                break;            default:                top = (TreeNode *)malloc(sizeof(TreeNode));                if(top == NULL)                {                    printf("-3\n");                }                top->left = NULL;                top->right = NULL;                top->data = pData[i];                if(NULL == *head)                {                    *head = top;                }                if(k == 1)                {                    sop[j]->left = top;                }                if(k == 2)                {                    sop[j]->right = top;                }        }        i++;    }}void show_tree(TreeNode *head){    if(head == NULL)    {        return;    }    else    {        printf("%c", head->data);        if((head->left != NULL)||(head->right != NULL))        {            printf("(");            show_tree(head->left);            if(head->right != NULL)            {                printf(",");                show_tree(head->right);            }            printf(")");        }    }}void Pre_order(TreeNode *root){	char ch;	SqStack s;	InitStatck(s);	TreeNode*ptemp=root;	while(ptemp!=NULL||!StackEmpty(s))	{		if(ptemp)		{			printf("%c",ptemp->data);// 先序就体现在这里了，先访问，再入栈 			Push(s,*ptemp);			ptemp=ptemp->left;// 依次访问左子树 		}		else		{			ptemp=Pop(s); // 回溯至父亲节点 			ptemp=ptemp->right;		}	}}void Mid_order(TreeNode *root){	char ch;	SqStack s;	InitStatck(s);	TreeNode*ptemp=root;	while(ptemp!=NULL||!StackEmpty(s))	{		while(ptemp)// 左子树入栈 		{						Push(s,*ptemp);			ptemp=ptemp->left;		}		if(!StackEmpty(s))		{			ptemp=Pop(s); // 访问根结点 			printf("%c",ptemp->data);			ptemp=ptemp->right;// 通过下一次循环实现右子树遍历		}	}}void Post_order(TreeNode *root){	SqStack s;	InitStatck(s);	TreeNode*current=root;	TreeNode*preNode=NULL;	while(current != NULL || !StackEmpty(s))	{ 		while( current != NULL)		{			Push(s,*current); 			current = current->left;		}		current = GetTop(s);		if(current->right == NULL || current->right->data == preNode->data)		{			if (current->data !=NULL)			{				printf("%c",current->data);			}							preNode = current;			current = Pop(s);			current = NULL;				}		else		{			current = current->right;				}	}	}int _tmain(int argc, _TCHAR* argv[]){	char a[] = "a(b(c),d(e(f,g),h( ,i)))";	/*char a[]="a(b(c,e),d)";*/    TreeNode *head = NULL;	Create_tree(&head, a);    show_tree(head);    printf("\nPre_Order is: ");    Pre_order(head);	printf("\nMid_order is: ");    Mid_order(head);		printf("\nPost_order is: ");    Post_order(head);	printf("\n");	system("pause");	return 0;}
    
   

#pragma once#include "stdafx.h"#include
   
    #define OK 1#define TRUE 1#define ERROR 0#define FALSE 0#define overflow -2#define STACK_INTT_SIZE 100#define STACK_INIT_INCREMENT 20#define Status int#define ElemType TreeNodetypedef struct TreeNode{    struct TreeNode *left;    struct TreeNode *right;    char data;}TreeNode;typedef struct {	ElemType *base,*top;	int stackSize;}SqStack;/*   栈的操作    Status InitStatck(SqStack &s)   初始化栈    Status DestoryStatck(SqStack &s)  销毁栈    Status ClearStack(SqStack &s)    清除栈    bool StackEmpty(SqStack s)         栈是否为空    int StackLength(SqStack s)        栈的长度    Status GetTop(SqStack s,SElemType &e)  得到栈顶    Status Push(SqStack &s,SElemType e)   压栈    Status Pop(SqStack &s,SElemType &e)   出栈   void DisplayStack(SqStack s);    显示栈内的元素   */Status InitStatck(SqStack &s){	s.base=(ElemType*)malloc(STACK_INTT_SIZE*(sizeof(ElemType)));	if(!s.base)		return ERROR;	else		s.top=s.base;	s.stackSize=STACK_INTT_SIZE;}Status DestoryStatck(SqStack &s){	s.top=s.base;	free(s.base);	s.base=NULL;	s.top=NULL;	 return OK;  }bool StackEmpty(SqStack s){	if(s.base==s.top)   	  return TRUE;   	 else    	  return FALSE;    }int StackLength(SqStack s)  {	if(s.base=s.top)    	  return ERROR;   	 else    	  return (s.top-s.base);  }ElemType *GetTop(SqStack s){	if(StackEmpty(s))	{		printf("This stack is empty.");		return NULL;	}	else	{		return 	(--s.top);	}}Status Push(SqStack &s,ElemType e){	if(StackLength(s)==STACK_INTT_SIZE)	{		ElemType*temp=(ElemType*)realloc(s.base,(STACK_INTT_SIZE+STACK_INIT_INCREMENT)*(sizeof(ElemType)));		if(!temp)			return ERROR;		s.base=temp;		s.top=s.base+STACK_INTT_SIZE;		s.stackSize=STACK_INTT_SIZE+STACK_INIT_INCREMENT;		*(s.top++)=e;		return OK;	}	else	{		*s.top=e;		s.top++;		return OK;	}}ElemType *Pop(SqStack &s){	if(StackEmpty(s))	{		printf("This stack is empty.");		return NULL;	}	else		return 	(--s.top);}Status ClearStack(SqStack &s){	s.top=s.base;	s.stackSize=0;	 return OK;  }void DisplayStack(SqStack s){	if(StackEmpty(s))		exit(-1);	while(s.top!=s.base)		printf("%d\n",*(--s.top));}
   

转载地址：http://bdsvi.baihongyu.com/