【数据结构】C语言实现树和森林的遍历

typedef char ElemType;
//孩子兄弟表示法
typedef struct ChildBrotherNode {
	ElemType data;//数据域
	struct ChildBrotherNode* lchild;//左孩子
	struct ChildBrotherNode* rbrother;//右兄弟
}CBNode, * CBTree;
//CBNode——孩子兄弟结点
//CBTree——孩子兄弟树
typedef struct ChildBrotherForest {
	CBTree* trees;//森林中的树
	int n;//树的个数
}CBForest;
//CBForest——孩子兄弟森林

//树
[A,B,E,0,0,C,F,0,G,0,0,D,H,0,I,0,J,0,0,0,0]
//森林
[[A,0,0],[B,E,0,0,0],[C,F,0,G,0,0,0],[D,H,0,I,0,J,0,0,0]]

//先序创建孩子兄弟树
CBTree CreateCBTree(ElemType* arr, int* pi, int len) {
	//arr——树的先序序列
	//pi——当前访问下标
	//len——先序序列长度
	assert(arr && pi);//判断数组与下标是否为空指针
	if (*pi == len || arr[*pi] == 0) {
		return NULL;
	}
	CBNode* p = (CBNode*)calloc(1, sizeof(CBNode));
	assert(p);
	//访问根结点
	p->data = arr[*pi];
	*pi += 1;
	//创建左子树
	p->lchild = CreateCBTree(arr, pi, len);
	*pi += 1;
	//创建右兄弟
	p->rbrother = CreateCBTree(arr, pi, len);
	return p;
}

//创建森林
CBForest* CreateCBForest(ElemType** arr, int* n, int len) {
	//arr——森林中各树的先序序列
	//n——森林中各树先序序列的长度
	//len——森林中树的数量
	assert(arr && n);
	CBForest* forest = (CBForest*)calloc(1, sizeof(CBForest));
	assert(forest);
	forest->n = len;//森林中树的个数
	//为树申请根结点空间
	forest->trees = (CBTree*)calloc(len, sizeof(CBTree));
	assert(forest->trees);
	//让森林中的每棵树都以孩子兄弟树的形式创建
	for (int i = 0; i < len; i++) {
		int pi = 0;
		//先序创建孩子兄弟树
		forest->trees[i] = CreateCBTree(arr[i], &pi, n[i]);
	}
	//返回创建好的森林
	return forest;
}

//森林转化孩子兄弟二叉树
CBTree Forest_to_CBTree(CBForest* forest) {
	assert(forest);
	//创建一个新的孩子兄弟树的根结点
	CBTree forest_tree = (CBTree)calloc(1, sizeof(CBNode));
	assert(forest_tree);
	//根结点中存储的值为森林中第一棵树的根结点的值
	forest_tree->data = forest->trees[0]->data;
	//根结点的左子树指向的是森林中第一棵树的左子树
	forest_tree->lchild = forest->trees[0]->lchild;
	//通过指针p来完成森林中的树的连接
	CBNode* p = forest_tree;
	for (int i = 1; i < forest->n; i++) {
		//创建新的根节点
		CBNode* root = (CBNode*)calloc(1, sizeof(CBNode));
		assert(root);
		//新的根节点记录当前根结点的信息
		root->data = forest->trees[i]->data;
		root->lchild = forest->trees[i]->lchild;
		//处理第一棵树与第二棵树之间的连接
		if (i == 1) {
			//第一棵树的根结点的右兄弟指针指向第二棵树的根结点
			forest_tree->rbrother = root;
		}
		//处理其它树之间的连接
		else {
			//当前根结点的右兄弟指针指向下一棵树的根结点
			p->rbrother = root;
		}
		//p指针移动到下一棵树
		p = root;

	}
	return forest_tree;
}

//先根遍历
void PreOrderTree(CBTree tree) {
	if (!tree) {
		return;
	}
	//访问根结点
	visit(tree->data);
	//当前结点的孩子
	CBNode* child = tree->lchild;
	while (child) {
		//当孩子存在时，继续先根遍历孩子
		PreOrderTree(child);
		//遍历下一个孩子
		child = child->rbrother;
	}
}

//先根遍历
void PreOrderTree(CBTree tree) {
	if (!tree) {
		return;
	}
	//访问根结点
	printf("%c\t", tree->data);
	//当前结点的孩子
	CBNode* child = tree->lchild;
	while (child) {
		//当孩子存在时，继续先根遍历孩子
		PreOrderTree(child);
		//遍历下一个孩子
		child = child->rbrother;
	}
}

//其转换的二叉树的遍历
void PreOrderCBTree(CBTree tree) {
	if (!tree) {
		return;
	}
	printf("%c\t", tree->data);
	PreOrderCBTree(tree->lchild);
	PreOrderCBTree(tree->rbrother);
}

//后根遍历
void PostOrderTree(CBTree tree) {
	if (!tree) {
		return;
	}
	//当前结点的孩子
	CBNode* child = tree->lchild;
	while (child) {
		//当孩子存在时，继续后根遍历孩子
		PostOrderTree(child);
		//遍历下一个孩子
		child = child->rbrother;
	}
	//访问根结点
	printf("%c\t", tree->data);
}

//其转换的二叉树的中序遍历
void InOrderCBTree(CBTree tree) {
	if (!tree) {
		return;
	}
	InOrderCBTree(tree->lchild);
	printf("%c\t", tree->data);
	InOrderCBTree(tree->rbrother);
}
//其转换的二叉树的后序遍历
void PostOrderCBTree(CBTree tree) {
	if (!tree) {
		return;
	}
	PostOrderCBTree(tree->lchild);
	PostOrderCBTree(tree->rbrother);
	printf("%c\t", tree->data);
}

//森林的遍历
//先序遍历
void PreOrderForest(CBForest* forest) {
	if (!forest) {
		return;
	}
	for (int i = 0; i < forest->n; i++) {
		PreOrderCBTree(forest->trees[i]);
	}
}
//森林生成的二叉树的先序遍历
void PreOrderCBForest(CBTree cbforest) {
	if (!cbforest) {
		return;
	}
	PreOrderCBTree(cbforest);
}

//中序遍历
void InOrderForest(CBForest* forest) {
	if (!forest) {
		return;
	}
	for (int i = 0; i < forest->n; i++) {
		PostOrderTree(forest->trees[i]);
	}
}
//森林生成的二叉树的中序遍历
void InOrderCBForest(CBTree cbforest) {
	if (!cbforest) {
		return;
	}
	InOrderCBTree(cbforest);
}
//森林生成的二叉树的后序遍历
void PostOrderCBForest(CBTree cbforest) {
	if (!cbforest) {
		return;
	}
	PostOrderCBTree(cbforest);
}

//树的销毁
void DestroyCBTree(CBTree* tree) {
	assert(tree);
	if (*tree == NULL) {
		return;
	}
	//后根遍历完成销毁
	DestroyCBTree(&(*tree)->lchild);
	DestroyCBTree(&(*tree)->rbrother);
	free(*tree);
	*tree = NULL;
}
//森林的销毁
void DestroyForest(CBForest** forest) {
	assert(forest);
	if (*forest == NULL) {
		return;
	}
	//依次销毁森林中的每一棵树
	for (int i = 0; i < (*forest)->n; i++) {
		DestroyCBTree(&((*forest)->trees[i]));
		if ((*forest)->trees[i] == NULL) {
			printf("森林中的第 %d 棵树已销毁\n", i + 1);
		}
	}
	free((*forest)->trees);
	(*forest)->trees = NULL;
	free(*forest);
	*forest = NULL;
}