树

树的表示方法

双亲表示法

用一组地址连续的存储单元来存放树中的各个节点，每一个节点中有一个数据域和一个指针域，数据域用来存储树中该节点本身的值；另一个指针域用来存储该节点的双亲节点在存储结构中的位置信息。

采用双亲链表存储方式实现查找一个指定节点的双亲节点比较方便，但难以实现查找一个指定节点的孩子节点。

孩子表示法

用一组地址连续的存储单元来存放树中的各个节点，每一个节点有一个数据域和一个指针域，数据域用来存储树中该节点的值；另一个指针域用来存放该节点的孩子链表的头指针。形式上有点像存储图的领接表。

采用孩子表示法便于实现查找树中指定节点的孩子节点，但难以实现查找树中指定节点的双亲节点。

孩子兄弟表示法

孩子兄弟表示法是用一种链式的结构存储一颗树的方式。每个节点含有孩子指针域和兄弟指针域。我们分别用 firstchild 和 nextsibling 表示。
其中孩子指针域，表示指向当前结点的第一个孩子结点，兄弟结点表示指向当前结点的下一个兄弟结点。其本质是先将一棵树转换为二叉树后存储在二叉链式结构之中。

孩子兄弟表示法能够将对一棵树的操作转换成对二叉树的操作，这种表示方法在实际运用中比较广泛。

故在这里给出孩子兄弟表示法创建树的代码，在后文中也都是使用这种表示方法。

孩子兄弟表示法创建树

typedef char Elemtype; //树 (孩子兄弟表示法) typedef struct CSNode{      Elemtype data;     struct CSNode *firstchild;      //第一个孩子     struct CSNode *nextsibling;     //下一个兄弟  }CSNode, *CSTree;  //创建 树 CSTree Create_CSTree(){     Elemtype data;     CSTree T;     scanf("%c", &data);                       //输入节点数据     getchar();      if(data == '#')        //输入 - 以停止创建子树         return NULL;     T = (CSTree)malloc(sizeof(CSNode));     T->data = data;      printf("输入 %c 的第一个孩子数据(#停止): ", data);  //递归创建     T->firstchild = Create_CSTree();     printf("输入 %c 的下一个兄弟数据(#停止): ", data);       T->nextsibling = Create_CSTree();       return T; } 

二叉树

二叉树是节点度数不大于 2 的有序树，是简单而又广泛运用的重要数据结构。

二叉树基本结构

//二叉树 结构体 typedef struct BiNode{      Elemtype data;     struct BiNode *leftchild;       //左儿子     struct BiNode *rightchild;      //右儿子  }BiNode, *BinaryTree;                

森林

森林很好理解，就是多个树组成的集合。

森林基本结构

//森林 结构体 typedef struct {      CSTree ct[MAX];     int n;   //树的个数 	 }forest, *Forest; 

树、二叉树和森林的转换

树 转换为 二叉树

树 --> 二叉树步骤

（1）将树中每个相邻的兄弟进行连线；
（2）将每个节点除第一个孩子以外，断开其他兄弟与其双亲节点的连线；
（3）适当旋转处理完后的树，使其呈现二叉树的形式。

树 --> 二叉树图解

（1）加线、（2）断线