用链表构造树的结构.doc

文档介绍：大作业案例三
先对树进行定义：
#include<>
#include<>
#include <>
#define size 10
typedef char DataType大作业案例三
先对树进行定义：
#include<>
#include<>
#include <>
#define size 10
typedef char DataType;
typedef struct CSNode {
DataType data;
struct CSNode *lchild, * rsibling;
} *CSTree;
4-36 设一棵树存储表示为子女-兄弟链表，编写一个算法计算书的深度。
算法设计：
兄弟处在同一层，所以不算入深度，首先定义两个变量来保存树的子树高度和最大高度，将它们进行比较。遍历一棵子树时，同时遍历该子树的兄弟的子树，取最大值保存。
int CST_Height(CSNode* CST)
{
if (CST == NULL) return 0;
if ( CST->lchild == NULL ) return 1;
CSNode *p = CST->lchild; //根的第一课子树
int m, n = 0; //n 为数的高度，m 为子树的高度
while ( p != NULL ) {
m = CST_Height(p);
if ( m > n ) n = m;
p = p->rsibling; //一次遍历所有兄弟
}
return n+1;
}
4-40 已知一棵数的层次序序列以及每个节点的度，编写一个算法，构造此树的子女-兄弟链表。
算法设计：
第一个孩子的位置是该节点父节点前面的节点所有的度的总和再加上根节点的值，兄弟的构造依靠父节点的度来判断。输入所有节点，使它们的指针都为空，最后去将它们连接。
int createCSTree_Degree ( CSNode *& t, DataType e[], int degree[],int n ) {
if ( n == 0 ) { t = NULL; return 1; };
int i, k = 0;
CSTree *Q = new CSTree[size]; //创建队列Q(存放结点地址)
if ( Q == NULL ) {cout << "存储分配失败！\n"; exit(1); }
for ( i = 0; i < n; i++ ) { //输入所有节点数据
Q[i] = new CSNode;
Q[i]->data = e[i];
Q[i]->lchild = Q[i]->rsibling = NULL;
}
int sum = 1;
for (i=0;i<n;i++)
{
if (i>0)
{
sum += degree[