2020考研-王道数据结构-树和二叉树-树和森林

朱雀 2022-01-20 23:27 342阅读 0赞

# 头文件定义 #

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <queue>

# 数据结构定义 #

typedef char ElemType;
    
    typedef struct CSNode // 孩子兄弟表示法的树
    {
        
    	ElemType data;
    	struct CSNode *first, *next;
    }CSNode, *CSTree;

# 第五题 #

##### 题目描述 #####

编程求以孩子兄弟表示法存储的森林的叶子结点数。

##### 题目分析 #####

无左孩子的结点就是叶子。

##### 代码 #####

// 求以孩子兄弟表示法的树的叶子节点的个数
    int getLeafNodeCounter(CSTree tree)
    {
        
    	static int res = 0;
    	if (!tree) return 0;
    	if (!tree->first) res++;
    	getLeafNodeCounter(tree->first);
    	getLeafNodeCounter(tree->next);
    	return res;
    }

# 第六题 #

##### 题目描述 #####

以孩子兄弟链表为存储结构，设计递归算法求树的深度。

##### 题目分析 #####

对于孩子兄弟表示法来说，二叉树的递归求深度的时候：

1.  向左子树走，左子树是当前结点的子节点，所以深度+1.
2.  向右子树走，右子树是当前结点的兄弟结点，深度不变。
3.  总深度 = max(左子树的深度+1，右子树的深度)

##### 代码 #####

// 求以孩子兄弟表示法的树的深度
    int getHeight(CSTree tree)
    {
        
    	if (!tree) return 0;
    	return max(getHeight(tree->first) + 1, getHeight(tree->next));
    }

# 第七题 #

##### 题目描述 #####

已知一棵树的层次序列以及每个结点的度，编写算法构造此树的孩子-兄弟链表。

##### 题目分析 #####

我说一下下面代码的思路：  
从根节点开始看，根节点有3个度，意思就是能收留3个结点。则向后收留三个结点，按照逻辑顺序连接即可。  
然后把这三个结点入队。  
根节点已经满了，所以出队。依次进行，知道队列为空，整棵树就建好了。  
建议大家先在纸上模拟一下。给大家一棵树。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70][]

##### 代码 #####

// 一直一棵树的层序遍历序列和每个结点的度，求这棵树的孩子兄弟表示法的树
    CSTree getCSTree(string level, vector<int> degree)
    {
        
    	if (!level.size()) return NULL;
    	CSTree tree = new CSNode();
    	queue<CSTree> que;
    	que.push(tree);
    	int i = 0, j = 0;
    
    	tree->data = level[i++];
    	tree->first = tree->next = NULL;
    
    	while (que.size())
    	{
        
    		CSTree node = que.front(), p = NULL;
    		que.pop();
    		if (!degree[j]){
        
    			j++;
    			continue;
    		}
    
    		for (int k = 0; k < degree[j]; k++)
    		{
        
    			CSTree cst = new CSNode();
    			cst->data = level[i++];
    			cst->first = cst->next = NULL;
    			if (!k)
    			{
        
    				node->first = cst;
    				p = cst;
    				que.push(p);
    			}
    			else
    			{
        
    				p->next = cst;
    				p = cst;
    				que.push(p);
    			}
    		}
    		j++;
    	}
    	return tree;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]: /images/20220121/fb5b8615868649a59b5e6697f2375db3.png