【编程练习题】

　　本章编程练习题中的二叉树和树的二叉链表的类型定义如下：
　　struct BiTNode // 二叉树结点
　　{
　　　ElemType data ;
　　　BiTLink lchild,rchild;
　　};
　　typedef BiTLink BiTree; // 二叉树链表

　//----- 树的二叉链表(孩子-兄弟）存储表示 -----
　　typedef struct CSNode{
　　　ElemType data;
　　　struct CSNode *firstchild, *nextsibling;
　　} CSNode, *CSTree;

　1. 编写递归算法，在二叉树中求位于先序序列中第 k 个位置的结点的值。
　　bool pre_Order_K ( BiTree bt, int k, ElemType& x )
　// 已知 bt 为指向二叉链表(二叉树)的根指针，若 k>0 且不大于
　// 二叉树中的结点数，则以 x 带回该二叉树的先序序列中第 k 个
　// 数据元素并返回 true，否则返回 false

　2. 编写递归算法，将二叉树中所有结点的左、右子树相互交换。
　　void Exchange( BiTree& bt )
　// 已知 bt 为指向二叉链表(二叉树)的根指针，
　// 本函数实现该二叉树上所有结点的左、右子树互换

　3. 编写递归算法：对于二叉树中每一个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。
　　void ReleaseX( BiTree& bt, ElemType x )
　// 已知 bt 为指向二叉链表(二叉树)的根指针，若二叉树上存在其数据元素
　// 和 x 相同的结点，则均删除之。

　4. 编写按层次顺序(同一层自左至右)遍历二叉树的算法。
　　void LevelOrder( BiTree bt, char ss[], int& n )
　// bt 为指向（以二叉链表表示的）二叉树的根的指针，按层序遍历二叉树，
　// 以字符数组 ss[0..n-1] 返回遍历所得二叉树的层序序列，
　// n 为二叉树中所含结点的数目，其初值为 0

　5. 假设以如下说明的三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识，C 表示孩子结点标识，L/R 表示 C 为 F 的左孩子或右孩子)，且在输入的三元组序列中，C 是按层次顺序出现的。设结点的标识是字符类型。F='＾'时 C 为根结点标识，若 C 亦为'＾'，则表示输入结束。
　　struct Tuple // 三元组(father,child,tag)
　　{
　　　char f,c,tag;
　　};
　　typedef Tuple TupleList[32]; // 三元组序列

　　void Create_BiTree(BiTree &BT, TupleList tlist)
　// 按由 tlist 给定的三元组序列建二叉树的二叉链表存储结构

　6. 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树 T 中所有的边。输出的形式为(k1,k2),…,(ki,kj),…，其中，ki 和 kj 为树结点中的结点标识。
　　void Out_Edge(CSTree T, char str[], int& n)
　// 按先根次序输出以孩子-兄弟链表表示的树 T 中各条边，
　// 并以题集中原题约定的形式存放在字符数组 str[] 中，
　// n 为字符数组中（最后所得结果）的字符个数，其初值为 0。

　7. 假设有n个结点的树T采用了如下说明的双亲存储表示，写出由此建立树的孩子-兄弟链表的算法。
　//----- 树的双亲存储表示 -----
　　typedef struct PTNode {
　　　ElemType data;
　　　int parent; // 双亲位置域
　　} PTNode;
　　typedef struct {
　　　PTNode nodes[MAX_TREE_SIZE];
　　　int n, r; // 结点数和根结点的位置
　　} PTree;

　　CSTree CreateCSTree( PTree T )
　// 已知树 T 的双亲表示，返回树的孩子-兄弟链表(指向根结点)的根指针

　8. 已知一棵树的由根至叶子结点按层次输出的结点序列及每个结点的度（每层中自左至右输出）(如下所示定义)，试写出构造此树的孩子-兄弟链表的算法。
　　struct Dual
　　{
　　　char data; // 结点信息
　　　int deg; 　// 结点的度
　　};
　　typedef Dual DualList[64];

　　void CreateCSTree( CSTree& T, DualList tlists )
　// 由一棵树的结点和度的层序序列 tlists ，构造该树的孩子-兄弟链表，
　// T 为指向根结点的指针若根结点的信息为 '#'，则为空树

　 		 
【编程练习题】