本文共 2380 字，大约阅读时间需要 7 分钟。

 一、前言

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

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

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

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

二、题目

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

 三、代码

#include
   
    #include
    
     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 forestint 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;}
    
   

四、实现效果

转载地址：http://sdyni.baihongyu.com/