习题4-2
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 习题4-2
设计一个算法，将一棵以二叉链表存储的二叉树T按顺序方式存储到一维数组BI]中(根结点下标为1，结点的权值>=0，数组值等于-1 表示该结点不存在)。二叉树结点的数据类型定义如下： -AX
typedef struct node{
int data;
struct node *lchild, *rchild;
}BTNode;
void PostOrder(BTNode *p, int B[], int i)
{
if (p == NULL)
{
B[i] = -1;
return;
}
PostOrder(p->lchild, B, 2 * i);
PostOrder(p->rchild, B, 2 * i + 1);
B[i] = p->data;
}
void ans(BTNode *T, int B[])
{
PostOrder(T, B, 1);
}
typedef struct node{
int data;
struct node *lchild, *rchild;
}BTNode;
int PostOrder(BTNode* p) //后序遍历
{
if (p==NULL)
return 0; //该结点不存在
int L=PostOrder(p->lchild);
int R=PostOrder(p->rchild);
int depth=max(L, R)+1; // 访问当前结点vis1t(p)
} return depth;
typedef struct node{
int data;
struct node *firstchild, *nextbro;
}TNode;
int degree=0; // 全局变量，最终输出degree
int Post(TNode* p)
{ //后序遍历 主道
if (p==NULL)
return 0; // 该结点不存在
Post(p->firstchild);
int d=1+Post(p->nextbro); //d是指到该结点为止有多少个兄弟
degree=max(degree, d);
return d;
}
原资料配图 · 转写内容请回源核验
## 习题4-5
设二叉树以二叉链表形式存放，根结点的深度为1，一棵二叉树的繁茂程度定义为各层结点数与该层深度的乘积之和。试设计算法，求二叉树的繁茂程度。数据类型定义如下：
typedef struct node{
int data;
struct node *lchild, *rchild;
}BTNode;
int ans(BTNode *T)
{
BTNode* q[MAX_SIZE];
int front=0, rear=0, depth=1;
int last=0; ///本层的最后一个结点下标
if (T!=NULL) q[rear++]=T;
BTNode *p; // 当前访问的结点p
int sum=1*1; //第一层的繁茂程度
while(front<rear)
{
p=q[front++];
if (p->lchild!=NULL)
q[rear++]=p->lchild;
if (p->rchild!=NULL)
q[rear++]=p->rchild;
if(front>last)//该层已访问完
{
depth++;
printf("%d %d %d\n", front, rear, depth);
sum+=(rear-front)*depth;
last=rear-1;
}
}
return sum;
}
原资料配图 · 转写内容请回源核验
0。例如下图所示就是镜像对称的。
(1)给出算法的基本设计思想。(2) 根据设计思想，采用C 或C++ 语言描述算法，关键之处给出注释。（3）说明所设计算法的时间复杂度。【解析】本题采用先序/中序/后序遍历都可以，设置两个指针p、q访问即可。【答案】（1）按照先序遍历，在遍历的时候设置两个指针 p、q，分别指向当前访问结点和它对称的位置，每次比较p和q的值是否相同。当p递归左（右）孩子的时候，q递归右（左）孩子，这样可以保证p和q一直是对称位置，如果发现p和 q 的值不一样则返回0。(2)代码如下：
int Pre0rder(BTNode *p,BTNode *q)
{
if (p==NULL && q==NULL)
return 1;
if (p==NULL || q==NULL)
return 0;
if (p->data!=q->data)
return 0;
if (Pre0rder(p->lchild, q->rchild)==0)
return 0;
if (Pre0rder(p->rchild,q->lchild)==0)
return 0;
return 1;
}
原资料配图 · 转写内容请回源核验
4的最低公共祖先是结点1。
二叉树结
点定义如下：
typedef struct node
{
int data;
struct node *left, *right;
}BTree;
BTree *PostOrder(BTree *root, BTree *p, BTree *q)
{
if (root == NULL) return NULL;
if (root == p || root == q) return root;
BTree *left = PostOrder(root->left, p, q);
BTree *right = PostOrder(root->right, p, q);
if (left != NULL && right != NULL) return root;
return left != NULL ? left : right;
}
typedef struct BTNode{
int weight;
struct BTNode *left, *right;
}BTNode;
int WPL=0; //WPL是全局变量
void PreOrder(BTNode *p, int depth) // 当前结点p，深度depth
{
if (p==NULL) // p是空结点
return;
if (p->left==NULL && p->right==NULL) // p是叶结点
WPL+=depth*p->weight;
Pre0rder(p->left, depth+1); // 递归调用左孩子
Pre0rder(p->right, depth+1); // 递归调用右孩子
}
typedef struct BTNode{
int weight;
struct BTNode *left, *right;
}BTNode;
int WPL=0; //WPL是全局变量
int PostOrder(BTNode *p)
{
if (p==NULL) // p是空结点
return 0;
int L=Post0rder(p->left);// 递归调用左孩子
int R=Post0rder(p->right); // 递归调用右孩子
if (p->left==NULL && p->right==NULL)
return p->weight; // p是叶结点
WPL=WPL+L+R; // p是非叶结点
return L+R;
}
原资料配图 · 转写内容请回源核验
二叉树结点定义如下：
原资料配图 · 转写内容请回源核验
typedef struct node{
char data[10]; //存储操作数或操作符
struct node *left, *right;
}BTree;
void InOrder(BTree* p, BTree* root) // 王定
{
if (p==NULL) return; // p是空结点
if ((p->left!=NULL |l p->right!=NULL) && (p!=root))
printf("(");
In0rder(p->left, root); //递归调用左子树
printf("%s", p->data); //输出操作数
In0rder(p->right,root);//递归调用右子树
if ((p->left!=NULL |l p->right!=NULL) && (p!=root))
printf(")");
}
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; //保存二叉树结点值的数组
int ElemNum;
}SqBiTree;