考研真题数据结构

【2019年山西大学真题】求二叉树的深度。

（1）给出算法的设计思想。

（2）根据设计的思想，给出描述算法。

（3）分析所给算法的时间复杂度

（1）算法设计思想：
1.?二叉树的深度可以通过递归的方式来求解。
2.?如果树为空，则深度为0。
3.?如果树不为空，则树的深度等于其左子树和右子树深度的较大值加1。

（2）根据上述设计思想，可以用?C?语言编写以下算法：

```c
#include?<stdio.h>
#include?<stdlib.h>

//?定义二叉树结点的数据结构
typedef?struct?TreeNode?{
????int?data;???????????????//?结点存储的数据
????struct?TreeNode*?left;??//?左子树指针
????struct?TreeNode*?right;?//?右子树指针
}?TreeNode;

//?创建一个新结点
TreeNode*?createNode(int?data)?{
????TreeNode*?newNode?=?(TreeNode*)malloc(sizeof(TreeNode));
????if?(newNode?==?NULL)?{
????????printf("内存分配失败！\n");
????????exit(1);
????}
????newNode->data?=?data;
????newNode->left?=?NULL;
????newNode->right?=?NULL;
????return?newNode;
}

//?求二叉树的深度
int?getTreeDepth(TreeNode*?root)?{
????if?(root?==?NULL)?{
????????return?0;??//?树为空，深度为0
????}?else?{
????????int?leftDepth?=?getTreeDepth(root->left);????//?求左子树深度
????????int?rightDepth?=?getTreeDepth(root->right);??//?求右子树深度
????????return?(leftDepth?>?rightDepth)???(leftDepth?+?1)?:?(rightDepth?+?1);??//?返回左右子树深度的较大值加1
????}
}

int?main()?{
????//?创建一个二叉树
????TreeNode*?root?=?createNode(1);
????root->left?=?createNode(2);
????root->right?=?createNode(3);
????root->left->left?=?createNode(4);
????root->left->right?=?createNode(5);
????root->right->left?=?createNode(6);
????root->right->right?=?createNode(7);

????//?求二叉树的深度
????int?depth?=?getTreeDepth(root);

????printf("二叉树的深度为：%d\n",?depth);

????return?0;
}
```

在上述代码中，首先定义了二叉树结点的数据结构?`TreeNode`，以及创建新结点?`createNode`?的函数。然后定义了递归函数?`getTreeDepth`，根据设计思想实现了求二叉树深度的算法。
在?`main`?函数中，创建了一个二叉树并求其深度，并将结果打印出来。输出结果为：

```
二叉树的深度为：3
```

（3）分析时间复杂度：
在二叉树的深度求解算法中，每个结点都只会被访问一次，所以该算法的时间复杂度为?O(n)，其中?n?是二叉树中的结点个数。
?