【数据结构周周练】017 利用递归算法及孩子兄弟表示法创建森林、遍历森林并求森林的叶子结点个数

Myth丶恋晨 2021-06-11 15:13 353阅读 0赞

#  一、前言 #

从昨天起，就给大家分享一些树和森林的代码啦，昨天分享的是求树的深度，今天要给大家分享的是森林的遍历以及求叶子的个数。

对于森林，大家可以做这样的理解，**一个深度大于1，根节点子树个数大于1的树去掉根节点，就是森林**。**森林中每棵树的根节点再创建一个共同的双亲结点，就成为了一棵树**。所以森林转化为二叉树和树转化为二叉树原理是一样的，采用的方法依然是**孩子兄弟表示法**，转化规律如下：

**森林中第一颗树的根作为生成二叉树的根，每个结点左指针指向第一个孩子结点，右指针指向它在森林中的相邻兄弟结点**。通过这种方法构造的二叉树至少包括数据域，第一个孩子指针和右兄弟指针。

typedef struct CSNode {
    	int data;
    	struct CSNode *firstChild, *nextSibling;
    }CSNode, *CSTree;

# 二、题目 #

利用递归算法及孩子兄弟表示法存入下图的森林，遍历访问每个结点的编号，数据及所有的兄弟及孩子结点。其中圆角矩形内为结点数据，旁边数字为结点编号，箭头指向的结点为箭尾的孩子结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70][] 森林

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1][] 森林转化为二叉树

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct CSNode {
    	int data;
    	int number;
    	struct CSNode *firstChild, *nextSibling;
    }CSNode,*CSTree;
    
    int number = 0;
    int yon = 0;
    int yesOrNo[] = { 1,1,0,1,1,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0 };
    int numData[] = { 1,2,4,5,6,3,7,8,9,10,11,12,13 };
    int leafNumber = 0;
    
    //Operation the node to creat the forest
    int OperationNode(CSTree &T) {
    	T = (CSTree)malloc(sizeof(CSNode));
    	if (!T)
    	{
    		cout << "空间分配失败(Allocate space failure.)" << endl;
    		exit(OVERFLOW);
    	}
    	T->data = numData[number];
    	T->number = number;
    	number++;
    	T->firstChild = NULL;
    	T->nextSibling = NULL;
    	return 1;
    }
    
    //Eatablish the fotest by the method of child and sibling  
    void EstablishTree(CSTree &T) {
    	OperationNode(T);
    	if (yesOrNo[yon++])
    		EstablishTree(T->firstChild);
    	if (yesOrNo[yon++])
    		EstablishTree(T->nextSibling);
    }
    
    void VisitForest(CSTree T) {
    	CSTree p = T;
    	cout << "【" << p->number + 1 << "】The number of present node is ：" << p->number << ",";
    	cout << "and the data is ：" << p->data << ".";
    	if (p->nextSibling) {
    		cout << "\n\tThis node has sibling and the number is :" << p->nextSibling->number;
    		p = p->nextSibling;
    		while (p->nextSibling) {
    			cout << " , " << p->nextSibling->number;
    			p = p->nextSibling;
    		}
    	}	
    	if (T->firstChild) {
    		cout << "\n\tThis node has child and the number is :" << T->firstChild->number;
    		CSTree q = T->firstChild;
    		while (q->nextSibling) {
    			cout << " , " << q->nextSibling->number;
    			q = q->nextSibling;
    		}
    	}
    	cout << endl << endl;
    }
    
    void PreOrderVisitForest(CSTree T) {
    	VisitForest(T);
    	if (T->firstChild)
    		PreOrderVisitForest(T->firstChild);
    	else
    		leafNumber++;
    	if (T->nextSibling)
    		PreOrderVisitForest(T->nextSibling);
    }
    
    void main() {
    	CSTree T;
    	cout << "********【遍历刚刚创建的森林。Traverse forest just establish】********" << endl;
    	EstablishTree(T);
    	PreOrderVisitForest(T);
    	cout << "The number of leaf of Forest is : " << leafNumber << endl;
    }

# 四、实现效果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70]: /images/20210516/e81c525f6b754843bbb55dffedb5125c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1]: /images/20210516/27a34caa7f0d4dc3addb6ded611f7e08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 2]: /images/20210516/0cf4c469f2204582958d654cf0fb08b8.png