树的非递归遍历

男娘i 2021-06-24 15:56 457阅读 0赞

在VS2011版本中调试通过。

#include "stdafx.h"
    #include"Stack.h"
    //#include<stack>//标准库中定义的栈
    #include<cstdio>
    using namespace std;
    #define MAX_LEN 15
    void 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;
    }

头文件：Stack.h的定义

#pragma once
    #include "stdafx.h"
    #include<cstdlib>
    #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 TreeNode
    typedef 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));
    }