计蒜客非递归二叉树的前序遍历（树结构）

约定不等于承诺〃 2024-02-18 16:29 15阅读 0赞

给定一个层数小于等于10的二叉树，输出对其前序遍历的节点名序列。

输入包括一行，为由空格分隔开的各节点，按照二叉树的分层遍历顺序给出，每个节点形式如X(Y,num)，X表示该节点，Y表示父节点，num为0,1,2中的一个，0 表示根节点，1表示为父节点的左子节点，2表示为父节点的右子节点。输出为一行，为前序遍历的结果。

##### 样例输入 #####

A(0,0) B(A,1) C(A,2) D(B,1) E(B,2) F(C,1) G(D,1) H(D,2)

##### 样例输出 #####

A B D G H E C F

与后序遍历一样，打印顺序变了，为保证最后打印的节点不打印空格，判断条件有点区别：

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    const int maxn = 1e4;
    char s[maxn];
    int lchild[500] , rchild[500]; //保存ACSII值 
    int cnt = 0,tol = 0;
    
    void printNode(int root){
    	cnt++;  //当前第n个节点，用于打印最后一个节点时不打印空格 
    	if(lchild[root] == -1 && rchild[root] == -1){
    		if(cnt != tol) 
    		    printf("%c ",root); 
    	    else printf("%c",root);
    		return ;
    	}
    	
    	printf("%c ",root);
    	if(lchild[root] != -1) printNode(lchild[root]);
    	if(rchild[root] != -1) printNode(rchild[root]);
    }
    
    int main(){
    	while(gets(s)){
    		int root ;  //根节点 
    		for(int i = 0; i <= strlen(s) - 5; i+=7){   //构建二叉树 
    			int x = s[i];
    			int y = s[i+2];
    			int num = s[i+4] - '0';
    			if(num == 0){
    				root = x;
    			}else if(num == 1){
    				lchild[y] = x;
    			}else if(num ==2){
    				rchild[y] = x;
    			}
    				lchild[x] = -1; //-1表示该节点没有左节点 
    				rchild[x] = -1; //-1表示该节点没有右节点 	
    				
    				tol++; //节点总个数						
    		} 
    		printNode(root); 
    		printf("\n");
    	}
    	return 0;
    }