6. 设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树。
【答】
数据结构
采用5.1.3节中二叉树的链接表示。 思路
二叉树的先根序列和对称序序列，用两个数组preorder和inorder存放。先根序列的第一个元素的值preorder[0]应为二叉树的根上的元素值，在另一个数组中查到此值，设为inorder[k]。此时，数组preorder中从preorder[1]到preorder[k]的序列（长度为k）和数组inorder中从inorder[0]到inorder[k?1]（长度为k）的序列，恰好分别是根结点左子树（k个结点）的先根序列和对称序序列。数组preorder中从preorder[k+1]到preorder[n?1]的序列（长度为n?k?1）和数组inorder中从inorder[k+1]到inorder[n?1]（长度为n?k?1）的序列，恰好分别是根结点左子树（n?k?1个结点）的先根序列和对称序序列。
根据上述分析，算法先创建根结点，再递归调用自己两次来分别创建左右子树。 算法
int create_BTree(PBinTree pbtree, DataType * preorder, DataType * inorder, int n){
/*根据先根序列preorder和对称序序列inorder（长度为n）创建二叉树pbtree。对于正确的先根序列和对称序序列，算法返回TRUE，否则返回FALSE。*/
int i, k; int tag1, tag2; if (n = = 0) {
*pbtree = NULL; return TRUE; }
for (i = 0; i < n; i++)
if (inorder[i] = = preorder[0])
break; if (i = = n) { *pbtree = NULL; return FALSE; } k = i;
*pbtree = (PBinTreeNode)malloc(sizeof(struct BinTreeNode)); (*pbtree)->info = preorder[0];
tag1 = create_BTree(&(*pbtree)->llink, preorder + 1, inorder, k);
/*递归调用本算法创建左子树*/ /*递归调用本算法创建右子树*/
/*二叉树创建成功当且仅当其左右子树都创建成功*/
tag2 = create_BTree(&(*pbtree)->rlink, preorder + k + 1, inorder + k + 1, n ? k ? 1); if (tag1 = = TRUE && tag2 = = TRUE) return TRUE; return FALSE; }
/*输入的先根序列或对称序序列有误，创建失败*/
代价分析
最坏的情况是，每个非叶结点只有左子树。这时两个数组之间需要比较n+(n-1)+…+1=O(n2)次。所以，该算法的时间代价为O(n2)。空间代价主要包括：存放二叉树的空间O(n)和用于递归调用的栈空间（不超过O(n)）。
7. 试设计树的子表表示法的存储结构，并给出在这种表示基础上主要运算的实现算法。 【答】 数据结构
struct EdgeNode
{
int nodeposition;
struct EdgeNode * link;
};
struct ChiTreeNode
{
DataType info;
struct EdgeNode * children;
};
struct ChiTree
{
struct ChiTreeNode nodelist[MAXNUM]; int root; int n;
};
typedef struct ChiTree * PChiTree;
算法 创建空树
PChiTree CreateNullTree_chitree(void) {
PChiTree p;
p = (PChiTree)malloc(sizeof(struct ChiTree)); if (p = = NULL)
printf(\else { p->n=0;
p->root = ?1; } return p; }
判断树是否为空
int isNull_chitree (PChiTree t) {
return t->n = = 0; }
返回非空树的根结点的下标
DataType root_chitree (PChiTree t) {
/*边表中结点的定义*/
/*子结点位置*/ /*下一个边的指针*/
/*结点的定义*/
/*结点本身信息*/ /*到子结点的边表*/
/*树的定义*/
/*结点表*/ /*根的位置*/ /*结点的个数*/
return t->root; }
返回下标为p的结点的父结点的下标
int parent_chitree (PChiTree t, int p) {
int i;
struct EdgeNode * v;
if (p < 0 || p >= t->n) return ?1; for (i = 0; i < t->n; i++) {
v = t->nodelist[i].children; while (v != NULL) } return ?1; }
if (v->nodeposition = = p)
return i; v = v->link; else
返回下标为p的结点的最左子结点的下标
int leftChild_chitree(PParTree t, int p) {
struct EdgeNode * v;
if (p < 0 || p >= t->n) return ?1; v = t->nodelist[i].children; if (v = = NULL) return ?1; return v->nodeposition; }
返回下标为p的结点的右兄弟结点的下标
int rightSibling_chitree(PParTree t, int p) {
int i;
struct EdgeNode * v;
if (p < 0 || p >= t->n) return ?1; for (i = 0; i < t->n; i++) {
v = t->nodelist[i].children; while (v != NULL)
/*每次循环检查结点i的边表中的一个元素*/
if (v->nodeposition = = p)
if(v->link = = NULL) else
return v->link->nodeposition;
/*返回右兄弟结点在结点表中的位置*/
return ?1;
/*没有右兄弟结点*/
/*没有下标为p的结点*/
/*for循环每次检查结点下标中一个元素*/
}
else
v=v->link;
/*没有右兄弟结点*/
return ?1; }
代价分析
这是一个两重循环程序，外层循环最多执行n次，内层循环对每个结点的子结点进行检查，子结点的个数最大可能与n接近，所以表面看来这是一个n2阶的时间代价；但是，仔细分析内层的循环体，可以看出内层循环最多对树中的每条边执行一次，由于树中边的个数与结点的个数成正比，所以时间代价仍然是O(n)。
补充题：
1. 试设计完全二叉树的顺序表示法的存储结构，并给出在这种表示基础上主要运算的实现算法。 【答】 数据结构
struct SeqBTree {
DataType nodelist[MAXNODE]; int n; };
typedef struct SeqBTree * PSeqBTree;
/*完全二叉树的结点个数*/
算法
判断二叉树是否为空
int isNull_seq(PSeqBTree t) {
return t->n = = 0; }
返回非空二叉树的根结点的下标
int root_seq(PSeqBTree t) {
return 0; }
返回下标为p的结点的父结点的下标
int parent_seq(PSeqBTree t, int p) {
if (p < 0 || p >= t->n) return ?1; return (p ? 1) / 2; }
返回下标为p的结点的左子结点的下标
int leftChild_seq(PSeqBTree t, int p) {
if (p < 0 || p >= t->n) return ?1; return 2*p + 1; }
返回下标为p的结点的右子结点的下标
int rightChild_seqbtree(PSeqBTree t, int p) {
if (p < 0 || p >= t->n) return ?1; return 2 * (p + 1); }
2. 试设计二叉树的左右指针表示法的存储结构，并给出在这种表示基础上主要运算的实现算法。 【答】 数据结构
struct BinTreeNode;
typedef struct BinTreeNode * PBinTreeNode; struct BinTreeNode {
int info;
PBinTreeNode llink; PBinTreeNode rlink; };
typedef struct BinTreeNode * BinTree;
算法
判断二叉树是否为空
int isNull_btree(BinTree t) {
return t = = NULL; }
返回非空二叉树的根结点的地址
PBinTreeNode root_btree(BinTree t) {
return t; }
返回二叉树t中结点p的父结点的地址
PBinTreeNode parent_btree(PBinTreeNode p, BinTree t) {
PBinTreeNode r;
if (p = = NULL) return NULL; if (p = = t || t = = NULL) return NULL; if (t->llink = = p || t->rlink = = p) return t; r = parent_btree(p, t->llink);
/*递归调用*/
if (r != NULL) return r; r = parent_btree(p, t->rlink); if (r != NULL) return r; return NULL; }
/*递归调用*/
返回结点p的左子结点的地址
PBinTreeNode leftChild_btree(PBinTreeNode p) {
if (p = = NULL) return NULL; return p->llink; }
返回结点p的右子结点的地址
PBinTreeNode rightChild_btree(PBinTreeNode p) {
if (p = = NULL) return NULL; return p->rlink; }