二叉树的递归遍历

矫情吗；* 2022-03-28 14:20 214阅读 0赞

## 二叉树的递归遍历 ##

简单递归遍历二叉树.

#include<stdio.h>
    #include<stdlib.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    #define TRUE 1
    #define FALSE 0
    #define SIZEINIT 10
    #define INCRESIZE 5
    
    typedef int Status;
    typedef char TElemType;
    
    typedef struct node{ 
    	TElemType data;
    	struct node *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //前序创建二叉树
    void CreateBiTree(BiTree &T){ 
    	char ch;
    	scanf("%c",&ch);
    	if(ch=='#'){ 
    		T = NULL;
    	}else{ 
    		T = (BiTree)malloc(sizeof(struct node));
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    
    //前序遍历
    Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ 
    	if(T){ 
    		if(Visit(T->data)){ 
    			if(PreOrderTraverse(T->lchild,Visit)){ 
    				if(PreOrderTraverse(T->rchild,Visit)) return OK;
    			}
    		}
    		return ERROR;
    	}
    	return OK;
    }
    
    //中序遍历
    Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ 
    	if(T){ 
    		if(InOrderTraverse(T->lchild,Visit)){ 
    			if(Visit(T->data)){ 
    				if(InOrderTraverse(T->rchild,Visit)) return OK;
    			}
    		}
    		return ERROR;
    	}
    	return OK;
    }
    
    //后序遍历
    Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ 
    	if(T){ 
    		if(PostOrderTraverse(T->lchild,Visit)){ 
    			if(PostOrderTraverse(T->rchild,Visit)){ 
    				if(Visit(T->data)) return OK;
    			}
    		}
    		return ERROR;
    	}
    	return OK;
    }
    
    //访问函数
    Status Visit(TElemType e){ 
    	printf("%c",e);
    	return OK;
    }
    
    int main(){ 
    	BiTree T = NULL;
    	printf("请前序创建第一棵树(空位置用'#'来代替)\n");
    	CreateBiTree(T);
    	printf("\n二叉树前序遍历的结果\n");
    	PreOrderTraverse(T,Visit);
    	printf("\n二叉树中序遍历的结果\n");
    	InOrderTraverse(T,Visit);
    	printf("\n二叉树后序遍历的结果\n");
    	PostOrderTraverse(T,Visit);
    	printf("\n");
        return 0;
    }
    //AB#D##CE###