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

#include
   
    #include
    
     #include
     
      using namespace std;typedef struct TreeNode* BiTree;typedef char ElementType;struct TreeNode{	ElementType Data;	BiTree Left;	BiTree Right;};BiTree CreateTree()	{		ElementType ch;		BiTree T = (BiTree)malloc(sizeof(struct TreeNode));		if(T == NULL){			printf("Over flow");			return NULL;		}		scanf("%c",&ch);		if(ch == '#')			T = NULL;		else{			T->Data = ch;			T->Left = CreateTree();			T->Right = CreateTree();			}		return T;		}	void PreTraversal(BiTree T)//递归版本 先序遍历 	{		if(T != NULL){			printf("%c ",T->Data);			PreTraversal(T->Left);			PreTraversal(T->Right);		}		}	void PreTraversalRe(BiTree T)//非递归前序遍历 	{		stack
      
        S;		while(T != NULL || !S.empty()){			while(T != NULL){				printf("%c ",T->Data);				S.push(T);				T = T->Left;			}			if(!S.empty()){				T = S.top();				S.pop();				T = T->Right;			}		}	}void InTraversal(BiTree T)//递归版本中序遍历 	{		if(T != NULL){			InTraversal(T->Left);			printf("%c ",T->Data);			InTraversal(T->Right);		}		}				void InTraversalRe(BiTree T)//非递归中序遍历 	{		stack
       
         S;		while(T != NULL || !S.empty()){			while(T != NULL){				S.push(T);				T = T->Left;			}			if(!S.empty()){				T = S.top();				printf("%c ",T->Data);				S.pop();				T = T->Right;			}		}		}		void PostTraversal(BiTree T)//递归版本 后续遍历 	{		if(T != NULL){			PreTraversal(T->Left);			PreTraversal(T->Right);			printf("%c ",T->Data);		}		}		void PostTraversalRe(BiTree T) //非递归 后序遍历	{		BiTree Pre = NULL;		stack
        
          S; while(T != NULL || !S.empty()){ while(T != NULL){ S.push(T); T = T->Left; } T = S.top(); if(T->Right == NULL || Pre == T->Right){ printf("%c ",T->Data); S.pop(); Pre = T; T = NULL; //为了 继续取栈顶元素 } else{ T = T->Right; } } } void LevelOrderTraversal(BiTree T)//层序遍历 { deque
         
           Q; if(T == NULL) return; Q.push_back(T); while( !Q.empty()){ T = Q.front(); Q.pop_front(); printf("%c ",T->Data); if(T->Left != NULL) Q.push_back(T->Left); if(T->Right != NULL) Q.push_back(T->Right); } } int main() { BiTree BT; BT = CreateTree(); printf("递归先序遍历 :\n"); PreTraversal(BT); printf("\n非递归先序遍历 :\n"); PreTraversalRe(BT); printf("\n递归中序遍历 ：\n"); InTraversal(BT); printf("\n非递归中序遍历 ：\n"); InTraversalRe(BT); printf("\n递归后续遍历 :\n"); PostTraversalRe(BT); printf("\n非递归后续遍历 :\n"); PostTraversalRe(BT); printf("\n层序遍历 :\n"); LevelOrderTraversal(BT); return 0; }