《数据结构》03-树2 List Leaves

Dear 丶 2022-05-15 15:06 152阅读 0赞

# 题目 #

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

**Input Specification:**  
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

**Output Specification:**  
For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

**Sample Input:**

8
    1 -
    - -
    0 -
    2 7
    - -
    - -
    5 -
    4 6

**Sample Output:**

> 4 1 5

# 分析 #

题目大意：按从上到下，从左到右的顺序输出叶子结点  
也就是有限制的"层序遍历"  
如何组织输入的树在上一题已经讲过，在此不再赘述 [《数据结构》03-树1 树的同构][03-_1]

关于层序遍历，构造一个队列，根结点入队，再循环地做：

1.  出队一个结点
2.  该结点是否没有左右子结点，满足条件输出该结点的值
3.  如果该结点有左儿子结点，左儿子结点入队
4.  如果该结点有右儿子结点，右儿子结点入队

直到队列为空  
还需要注意一些小细节，比如如果返回的根节点是 null 如何处理，比如如何处理空格

#include<queue>
    #include<iostream> 
    #define null -1
    using namespace std;
    struct TreeNode{
        
    	int data;  // 存值
    	int left;  // 存左儿子结点 
    	int right;   // 存右儿子结点 
    }T[10];
    //  把树整理出来 
    int create(){
        
    	int n;
    	int root = 0;
    	char left,right;
    	cin>>n;
    	if(!n)
    		return null;
    	for(int i=0;i<n;i++){
        
    		T[i].data = i;
    		cin>>left>>right;
    		if(left=='-')
    			T[i].left = null;
    		else{
        
    			T[i].left = left-'0';
    			root -= T[i].left;
    		}
    		if(right=='-')
    			T[i].right = null;
    		else{
        
    			T[i].right = right-'0';
    			root -= T[i].right;
    		}
    		root +=i;
    	}
    	return root;
    }
    // 层序遍历 
    void LevelorderTraversal(int root){
        
    	// 创建队列 
    	queue<struct TreeNode> q;
    	struct TreeNode t;
    	bool flag = false;
    	
    	// 如果树为空，直接打印 
    	if(root == null){
        
    		cout<<"-";
    		return;	
    	}
    	q.push(T[root]);
    	while(!q.empty()){
        
    		t = q.front();  // 得到当前队首元素 
    		q.pop();  // 出队 
    		if(t.left == null && t.right == null){
          // 如果为叶子结点就输出 
    			if(flag)
    				cout<<" ";
    			else
    				flag = true;
    			cout<<t.data;	
    		}
    		if(t.left != null)  // 如果有左儿子结点，入队左儿子结点 
    			q.push(T[t.left]);
    		if(t.right != null)  // 如果有右儿子结点，入队右儿子结点 
    			q.push(T[t.right]);
    	}
    } 
    int main(){
        
    	int root;
    	root = create();
    	LevelorderTraversal(root);
    	return 0;
    }

[03-_1]: https://blog.csdn.net/liyuanyue2017/article/details/83538124