本文针对[数据结构基础系列(6)：树和二叉树]第1-6, 8-10课时
1 树结构导学
2 树的基本概念
3 树的基本术语
4 树的性质
5 树的存储结构
6 二叉树概念和性质
8 二叉树的存储结构
9 二叉树的基本运算及其实现
10 二叉树的遍历
【项目1 - 二叉树算法库】
定义二叉树的链式存储结构，实现其基本运算，并完成测试。
要求：
1、头文件btree.h中定义数据结构并声明用于完成基本运算的函数。对应基本运算的函数包括：
void CreateBTNode(BTNode *&b,char *str); //由str串创建二叉链
BTNode *FindNode(BTNode *b,ElemType x); //返回data域为x的节点指针
BTNode *LchildNode(BTNode *p); //返回*p节点的左孩子节点指针
BTNode *RchildNode(BTNode *p); //返回*p节点的右孩子节点指针
int BTNodeDepth(BTNode *b); //求二叉树b的深度
void DispBTNode(BTNode *b); //以括号表示法输出二叉树
void DestroyBTNode(BTNode *&b); //销毁二叉树 2、在btree.cpp中实现这些函数
3、在main函数中完成测试，包括如下内容：
（1）用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建如图的二叉树用于测试。
（2）输出二叉树
（3）查找值为’H’的节点，若找到，输出值为’H’的节点的左、右孩子的值
（4）求高度二叉树高度
（5）销毁二叉树
［参考解答］
【项目2 - 二叉树遍历的递归算法】
实现二叉树的先序、中序、后序遍历的递归算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。
请利用二叉树算法库。
［参考解答］
【项目3 - 利用二叉树遍历思想解决问题】
假设二叉树采用二叉链存储结构存储，分别实现以下算法，并在程序中完成测试：
（1）计算二叉树节点个数；
（2）输出所有叶子节点；
（3）求二叉树b的叶子节点个数；
（4）设计一个算法Level(b,x,h)，返回二叉链b中data值为x的节点的层数。
（5）判断二叉树是否相似（关于二叉树t1和t2相似的判断：①t1和t2都是空的二叉树，相似；②t1和t2之一为空，另一不为空，则不相似；③t1的左子树和t2的左子树是相似的，且t1的右子树与t2的右子树是相似的，则t1和t2相似。）
请利用二叉树算法库。
［参考解答］
纸上谈兵：“知原理”检验题目
1、某树，用括号表示法描述为：A(B(E),C(F,G(I,J),H(K)),D)
（1）请用树形表示法，画出这个树
（2）双亲表示法的数据结构定义为
typedef struct
{
ElemType data;
int parent;
} PTree[MaxSize];请描述这个树利用双亲表示法时的存储
（3）用孩子链存储时，每个节点定义下面的类型
typedef struct node
{
ElemType data;
struct node *sons[MaxSons];
} TSonNode;请描述这个树利用孩子链表示法时的存储
（4）孩子兄弟链存储结构中的节点定义为
typedef struct tnode
{
ElemType data; //节点的值
struct tnode *hp; //指向兄弟
struct tnode *vp; //指向孩子节点
} TSBNode;请描述这个树利用孩子兄弟链表示法时的存储
（5）树结构还可以用一种孩子链表示法
//定义孩子节点，将形成一个单链表
typedef struct node
{
Int no; //孩子节点编号
struct node *next; //指向下一个孩子
} NodeType;
//定义树节点类型，各节点组成顺序存储的线性表，若节点要作为孩子节点，“孩子节点编号（no)”即为在顺序表中的序号
typedef struct
{
ElemType data; //元素值
NodeType *firstChild; //指向第一个孩子
} CTree[MaxSize];请描述这个树利用孩子兄弟链表示法时的存储。
2、某二叉树的顺序存储结构如下所示：
（1）请用树形表示法，画出二叉树的结构
（2）请用括号表示法，给出这个二叉树的表示
（3）请写出这个二叉树的先序、中序、后序遍历序列
3、二叉树还可以采用一种“伪”链式存储结构，如下所示
其中，lchild和rchild分别为节点左右孩子的指针域（在这里，使用节点编号作为指针域值，0表示指针域为空），data为节点的数据域。请画出这个二叉树的树形表示。
4、一棵二叉树的先序、中序和后序序列分别如下所示，其中有一部分未显示出来：
先序：_B_F_ICEH_G
中序：D_KFIA_EJC_
后序：_K_FBHJ_G_A
请求出空格处的内容，并画出二叉树。
