先序创建二叉树及先序、中序、后序遍历

短命女 2022-05-27 09:09 190阅读 0赞

先序二叉树

//先序建立二叉树
    void createBiTree(BiTree &T){
    	int cnt;
    	scanf("%d",&cnt);
    	if(cnt == -1){
    		T = NULL;
    		return ;
    	}
    	T = (BiTNode *)malloc(sizeof(BiTNode));
    	T->data = cnt;
    	T->lchild = NULL;
    	T->rchild = NULL;
    	createBiTree(T->lchild);
    	createBiTree(T->rchild);
    }

先序遍历：

//先序遍历
    void PreOrder(BiTree T){
    	if(T==NULL){
    		return ;
    	}
    	visit(T);
    	PreOrder(T->lchild);
    	PreOrder(T->rchild);
    }

中序遍历：

//中序遍历
    void InOrder(BiTree T){
    	if(T == NULL){
    		return ;
    	}
    	InOrder(T->lchild);
    	visit(T);
    	InOrder(T->rchild);	
    }

后序遍历：

//后序遍历 
    void PostOrder(BiTree T){
    	if(T==NULL){
    		return ;
    	}
    	PostOrder(T->lchild);
    	PostOrder(T->rchild);
    	visit(T);
    }

完整代码：

#include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #define ElemType int
    #define MaxSize 100
    using namespace std;
    //构造节点 
    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //先序建立二叉树
    void createBiTree(BiTree &T){
    	int cnt;
    	scanf("%d",&cnt);
    	if(cnt == -1){
    		T = NULL;
    		return ;
    	}
    	T = (BiTNode *)malloc(sizeof(BiTNode));
    	T->data = cnt;
    	T->lchild = NULL;
    	T->rchild = NULL;
    	createBiTree(T->lchild);
    	createBiTree(T->rchild);
    } 
    //访问节点 
    void visit(BiTree T){
    	printf("%d",T->data);
    }
    //先序遍历
    void PreOrder(BiTree T){
    	if(T==NULL){
    		return ;
    	}
    	visit(T);
    	PreOrder(T->lchild);
    	PreOrder(T->rchild);
    } 
    //中序遍历
    void InOrder(BiTree T){
    	if(T == NULL){
    		return ;
    	}
    	InOrder(T->lchild);
    	visit(T);
    	InOrder(T->rchild);	
    }  
    //后序遍历 
    void PostOrder(BiTree T){
    	if(T==NULL){
    		return ;
    	}
    	PostOrder(T->lchild);
    	PostOrder(T->rchild);
    	visit(T);
    }
    
    int main(){
    	BiTNode *bTree;
    	
    	createBiTree(bTree); 
    	PreOrder(bTree);
    	printf("\n");
    	InOrder(bTree);
    	printf("\n");
    	PostOrder(bTree);
    	printf("\n"); 
    	//printf("\n");
    	
    	return 0;
    }