1.树的存储结构
1.1.双亲表示法（顺序存储）
- 采用数组存储每个结点，同时为每个结点定义一个指针（伪指针，指示该元素在数组的下标）
- data域存放数据，parent域存放其双亲结点的数组下标
- 下标0存放根节点，根节点的指针域为-1
#define MAXSIZE 100 //定义结点 typedef struct PTNode{ elemtype data; //存放数据 int parent; //伪指针，指向其双亲结点 }PTNode; typedef struct PTree{ PTNode nodes[MAXSIZE]; //申明一个足够大的数组，存放树中结点 int n; //树中结点个数 }PTree;
优点：查找双亲很方便
缺点：查找孩子需要从头遍历
1.2.孩子表示法（顺序+链式）
该存储方式便于找孩子结点，但是找双亲结点麻烦
//链式存储，存放该结点的每个孩子结点的信息（非孩子结点数据） typedef struct CTNode{ int child; //存放该结点的孩子结点在数组中的下标 struct CTNode *next; //指向下一个孩子 }CTNode; //定义结点，存放结点数据，并且存放该元素的第一个孩子结点 typedef struct CTBox{ elemtype data; //存放数据 CTNode *firstChild; //指向第一个孩子结点 }CTBox; //顺序存储 typedef struct CTree{ CTBox nodes[MAXSIZE]; int n, r; //n为结点个数，r为根节点的数组下标 }CTree;
1.3.孩子兄弟表示法（森林和树的相互转化）
typedef struct CSNode{ elemtype data; //存放数据 struct CSNode *firstChild, *nextsibling; //第一个孩子和右兄弟指针 }CSNode, *CSTree;
孩子兄弟表示法的本质就是森林和树的相互转换：
森林和树的转化中，左指针指向的是孩子，右指针指向的是树
2.树和森林的遍历
2.1.树的先根遍历
ABCD→A（BEF）（CG）（DHIJ）→A（B（EK）F）（CG）（DHIJ）
树的先根遍历序列和这棵树对应的二叉树的先序序列相同
2.2.树的后根遍历
BCDA→（EFB）（GC）（HIJD）A→（KEFB）（GC）（HIJD）A
树的后根遍历序列和这棵树对应的二叉树的中序序列相同
2.3.森林的先序遍历
BCD→（BEF）（CG）（DHIJ）→（B（EKL）F）（CG）（D（HM）IJ）
依次对每个树进行先序遍历
2.4.森林的中序遍历
BCD→（EFB）（GC）（HIJD）→（（KLE）FB）（GC）（（MH）IJD）
依次对每个树进行后根遍历
2.5.树和森林的遍历小结
3.王道课后题
先序遍历
typedef struct TNode{ struct TNode *firstChild, *nextSilbing; elemtype value; }TNode, *Tree; int InOrder(Tree T) { int count = 0; if (!T) return count; count++; if (T->firstChild) count += InOrder(T->firstChild); if (T->nextSilbing) count += InOrder(T->nextSilbing); return count; }
typedef struct ThreadNode{ struct ThreadNode *firstChild, *nextSibling; elemtype data; }ThreadNode, *ThreadTree; int GetDepth(ThreadNode T) { int ldepth = 0, rdepth = 0; if (!T) return 0; else { if (T->firstChild) ldepth = GetDepth(T->firstChild; if (T->nextSibling) rdepth = GetDepth(T->nextSibling); } return (firstChild > nextSibling ? firstChild : nextSibling) + 1; }
