一、前言
从今天起，就给大家分享一些树的代码啦，不仅仅是二叉树，我们要弄明白，普通的树用数据结构怎么存储，它有哪些操作，它可以实现哪些功能？
可能大家要问了，二叉树不是还没有写完吗，线索二叉树呢？二叉排序树呢？平衡二叉树呢？大家不要急，我们通过二叉树来入门树的算法及代码实现，然后学习树的基本操作，当大家对树的了解比较深入，操作比较熟练的时候，我们再学深入的东西。
线索二叉树可以使用创建的空指针，来加速前驱和后继的访问速度；
二叉排序树是按照一定规律排序的数据存储在树中，例如从小到大的数据按照中序创建二叉树即可得到二叉排序树，二叉排序树与后面的排序查找算法联系也比较广泛；
平衡二叉树是为了防止树的高度增长过快，降低二叉排序树的性能而设计的一种结构，要保证的是任意结点的左右子树高度差的绝对值不超过1。
树要比二叉树难，二叉树作为树的特例，每个结点只有两个子树（存在或空），但是一棵普通的树孩子数量不一定，所以在构图过程中，没有左右孩子之说，所以就涉及到二叉树与最多有两个叉的树的区别。
如下图中，如果当成一棵普通的树来看，编号为1的结点有一个孩子结点，画在右侧，但是这个孩子是编号1的第一个孩子结点，而不是右孩子结点。如果看作一个二叉树，那就是编号为1的右孩子结点。这块大家一定要注意。
首先要给大家说一下树转换为二叉树，转化规律如下：
结点左指针指向第一个孩子结点，右指针指向它在树中的相邻兄弟结点。这种表示树的方法叫孩子兄弟表示法，通过这种方法构造的二叉树至少包括数据域，第一个孩子指针和右兄弟指针。
typedef struct CSNode {
int data;
struct CSNode *firstChild, *nextSibling;
}CSNode, *CSTree;
二、题目
利用递归算法及孩子兄弟表示法存入下图的树，求出每个结点的编号，数据及所有的孩子结点。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。
普通树
原树对应的二叉树
三、代码
#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;
}
四、实现效果
水亦心
认证博客专家
神经网络
算法
视觉/OpenCV
