【数据结构周周练】016 利用递归算法及孩子兄弟表示法创建树、遍历树并求树的深度

深碍√TFBOYSˉ_ 2021-06-11 15:13 330阅读 0赞

# 一、前言 #

从今天起，就给大家分享一些树的代码啦，不仅仅是二叉树，我们要弄明白，普通的树用数据结构怎么存储，它有哪些操作，它可以实现哪些功能？

可能大家要问了，二叉树不是还没有写完吗，线索二叉树呢？二叉排序树呢？平衡二叉树呢？大家不要急，我们通过二叉树来入门树的算法及代码实现，然后学习树的基本操作，当大家对树的了解比较深入，操作比较熟练的时候，我们再学深入的东西。

**线索二叉树**可以使用创建的空指针，来加速前驱和后继的访问速度；

**二叉排序树**是按照一定规律排序的数据存储在树中，例如从小到大的数据按照中序创建二叉树即可得到二叉排序树，二叉排序树与后面的排序查找算法联系也比较广泛；

**平衡二叉树**是为了防止树的高度增长过快，降低二叉排序树的性能而设计的一种结构，要保证的是任意结点的左右子树高度差的绝对值不超过1。

树要比二叉树难，二叉树作为树的特例，每个结点只有两个子树（存在或空），但是一棵普通的树孩子数量不一定，所以在构图过程中，没有左右孩子之说，所以就涉及到**二叉树与最多有两个叉的树的区别**。

如下图中，**如果当成一棵普通的树来看，编号为1的结点有一个孩子结点，画在右侧，但是这个孩子是编号1的第一个孩子结点，而不是右孩子结点。如果看作一个二叉树，那就是编号为1的右孩子结点**。这块大家一定要注意。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70][]

首先要给大家说一下树转换为二叉树，转化规律如下：

**结点左指针指向第一个孩子结点，右指针指向它在树中的相邻兄弟结点**。这种表示树的方法叫**孩子兄弟表示法**，通过这种方法构造的二叉树至少包括数据域，第一个孩子指针和右兄弟指针。

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

# 二、题目 #

利用递归算法及孩子兄弟表示法存入下图的树，求出每个结点的编号，数据及所有的孩子结点。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。

![70][] 普通树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1][] 原树对应的二叉树

#  三、代码 #

#define MAXQUEUESIZE 10
    
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct CSNode {
    	int data;
    	int number;
    	struct CSNode *firstChild, *nextSibling, *parent;
    }CSNode, *CSTree;
    
    int number = 0;
    int yon = 0;
    int yesOrNo[] = { 1,1,0,0,1,1,1,0,1,0,0,1,0,0,0,0 };
    int numData[] = { 1,2,4,3,5,7,8,6 };
    
    CSTree treeParent = NULL;
    
    int OperationTree(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;
    	T->parent = treeParent;	
    	return 1;
    }
    
    int RecursionEstablishTree(CSTree &T) {
    	OperationTree(T);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		RecursionEstablishTree(T->firstChild);
    	treeParent = T;
    	if (yesOrNo[yon++])
    		RecursionEstablishTree(T->nextSibling);
    	return 1;
    }
    
    void VisitCSTree(CSTree T) {
    	cout << "The number of present node is ：" << T->number << ",";
    	cout << "and the data is ：" << T->data << ".";
    	if (T->firstChild) {
    		cout << "This node has child and the number is :" << T->firstChild->number;
    		CSTree p = T->firstChild;
    		while (p->nextSibling) {
    			cout << " , " << p->nextSibling->number;
    			p = p->nextSibling;
    		}
    		
    	}
    	cout << endl;
    }
    
    //Visit tree use the preorder technique. 
    void PreOrderVisitTree(CSTree T) {
    	if (T)
    	{
    		VisitCSTree(T);
    		PreOrderVisitTree(T->firstChild);
    		PreOrderVisitTree(T->nextSibling);
    	}
    }
    
    int TreeHeight(CSTree T) {
    	int hc, hs;
    	if (T == NULL)
    		return 0;
    	else
    	{
    		hc = TreeHeight(T->firstChild);
    		hs = TreeHeight(T->nextSibling);
    		if (hc + 1 > hs)
    			return (hc + 1);
    		else
    			return hs;
    	}
    }
    
    void main() {
    	CSTree T;
    	RecursionEstablishTree(T);
    	PreOrderVisitTree(T);
    	cout << "The hight of tree is :" << TreeHeight(T) << 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/bad4a41338fc46e5833bb3dcdb36ae66.png
[70]: /images/20210516/5ed988aeff984bf4bce70cf394caeec3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1]: /images/20210516/62d506fa5c274ca0bb9944767a48608a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 2]: /images/20210516/c4d0bbd0f45242b8afb519dcd9637cc3.png