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

╰半夏微凉° 2024-02-18 16:28 11阅读 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)

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

G H D E B F C A

思路：先构建二叉树，s字符数组保存输入， lchild\[root\] ，rchild\[root\]分别保存根节点为root的左节点、右节点的ASCII值；最后递归打印即可

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    const int maxn = 1e4;
    char s[maxn];
    int lchild[500] , rchild[500]; //保存ACSII值 
    int r;
    
    void printNode(int root){
    	if(lchild[root] == -1 && rchild[root] == -1){
    		printf("%c ",root);
    		return ;
    	}
    	if(lchild[root] != -1) printNode(lchild[root]);
    	if(rchild[root] != -1) printNode(rchild[root]);
    	if(root != r)
    	  printf("%c ",root);
    	else printf("%c",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;
    				r = root;
    			}else if(num == 1){
    				lchild[y] = x;
    			}else if(num ==2){
    				rchild[y] = x;
    			}
    				lchild[x] = -1; //-1表示该节点没有左节点 
    				rchild[x] = -1; //-1表示该节点没有右节点 							
    		} 
    		printNode(root); 
    		printf("\n");
    	}
    	return 0;
    }