(3) 时间复杂度：O(n)
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## (3) 时间复杂度：O(n)
<!-- code-audit: false_positive -->
> [!info] 已人工审读：这是正文思考题及答案说明，被错误放入代码围栏。
请大家思考,如果根结点下标为0应该怎么写？
这种情况下,根结点下标为0,i号结点左孩子下标为2×i+1,右孩子下标为2×i+2
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; // 访问当前结点visit(p)
return depth;
}
typedef struct node{
int data;
struct node *firstchild, *nextbro;
}TNode;
(2)根据设计思想,采用C或C++; // 语言描述算法,关键之处给出注释。
int degree=0;
int Post(TNode* p)
{
if (p==NULL)
return 0;
Post(p->firstchild);
int d=1+Post(p->nextbro);
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 1ast=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;
}
(3) // 时间复杂度：O(n) 空间复杂度：O(n)
原资料配图 · 转写内容请回源核验
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明所设计算法的时间复杂度。
【解析】本题采用先序/中序/后序遍历都可以，设置两个指针p、q访问即可。
【答案】（1）按照先序遍历，在遍历的时候设置两个指针p、q，分别指向当前访问结点和它对称的位置，每次比较p和q的值是否相同。当p递归左（右）孩子的时候，q递归右（左）孩子，这样可以保证p和q一直是对称位置，如果发现p 和 q的值不一样则返回0。
(2) 代码如下:
int PreOrder(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 (Preorder(p->lchild, q->rchild)==0)
return 0;
if (Preorder(p->rchild, q->lchild)==0)
return 0;
return 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; // 若当前结点等于p或q，直接返回
BTree* left = PostOrder(root->left, p, q); //在左子树查找
BTree* right = PostOrder(root->right, p, q); // 在右子树查找
if (left != NULL && right != NULL)
return root; //左右子树都找到，当前root即为最近公
共祖先
//如果只在一个子树找到则返回该子树
if (left == NULL) return right;
else return left;
}
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)
return;
if (p->left==NULL && p->right==NULL) // p是叶结点
wPL+=depth*p->weight;
Preorder(p->left, depth+1); //递归调用左孩子
Preorder(p->right, depth+1); // 递归调用右孩子
}
typedef struct BTNode{
int weight;
struct BTNode *left, *right;
}BTNode;
int WPL = 0;
int PostOrder(BTNode *p)
{
if (p == NULL) return 0;
int L = PostOrder(p->left);
int R = PostOrder(p->right);
if (p->left == NULL && p->right == NULL) return p->weight;
WPL += L + R;
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 || p->right!=NULL) && (p!=root))
printf("(");
Inorder(p->left, root); //递归调用左子树
printf("%s", p->data); //输出操作数
Inorder(p->right, root); // 递归调用右子树
if ((p->left!=NULL || p->right!=NULL) && (p!=root))
} printf(")");
typedef struct {
int SqBiTNode[MAX_SIZE];
int ElemNum;
} SqBiTree;
//MAX_SIZE为已定义常量
//保存二叉树结点值的数组
//实际占用的数组元素个数
int pre=0; //全局变量pre保存中序前驱的权值，初值0
bool InOrder(SqBiTree *T, int i)
{
/*指针bt指向二叉树的结构体,i是当前访问的下标*/
if (i>=T->ElemNum |I T->SqBiTNode[i]==-1) // 当前结点为空
return true;
if (Inorder(T, 2*i+1) != true) // 递归调用左子树
return false; // 左子树不符合定义
if (pre>T->SqBiTNode[i])
return false;
pre=T->SqBiTNode[i];
if (Inorder(T, 2*i+2) != true)
return false;
return true;
}