第一题：二叉树的基础算法
题目
先根据二叉树的先序、中序遍历序列还原该二叉树，求出这棵二叉树的高度和宽度，以及其叶节点的个数。再将这棵二叉树在内存当中镜像克隆一份，输出克隆的这棵树的层次遍历序列，最后再释放掉这两棵树所占的内存空间。
你需要实现以下几个函数：
-
Node* createTree(int preOrder[], int inOrder[], int N);- 二叉树的先序、中序遍历序列分别存放在
preOrder、inOrder数组当中，这两个数组存放元素的个数都为N。 - 函数返回创建好的二叉树的根节点指针
- 二叉树的先序、中序遍历序列分别存放在
-
int getTreeHeight(Node* root);- 约定：空树的高度为0，一棵树如果只有1个节点（根节点）其高度为1
-
int getTreeWidth(Node* root);- 树的宽度是指：拥有节点数最多的那一层的节点数。
-
int countLeafNode(Node* root);- 返回二叉树中叶节点的个数，这个没什么好解释的。
-
Node* mirrorCloneTree(Node* root);-
镜像克隆的含义是你需要在内存中新创建一颗二叉树（不修改原来的树），新创建的树与原来的树为镜像关系。例如：
原来的树 镜像克隆的树 1 1 / \ / \ 2 5 5 2 / \ / \ 3 4 4 3 函数返回新创建树的根节点指针
-
-
void lavelOrderTraversal(Node* root);- 输出其层次遍历序列，以空格分割，行末应输出一个换行符
\n
- 输出其层次遍历序列，以空格分割，行末应输出一个换行符
-
void destoryTree(Node* root);- 释放树所占的内存空间
代码框架如下：
允许你对框架进行适量修改，比如你想使用全局数组。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
Node *lchild, *rchild;
}Node;
Node* createNode(int data) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->lchild = temp->rchild = NULL;
return temp;
}
Node* createTree(int preOrder[], int inOrder[], int N);
int getTreeHeight(Node* root);
int getTreeWidth(Node* root);
int countLeafNode(Node* root);
Node* mirrorCloneTree(Node* root);
void lavelOrderTraversal(Node* root);
void destoryTree(Node* root);
int main() {
int N;
scanf("%d", &N);
int* preOrder = (int*)malloc(N * sizeof(int));
int* inOrder = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++) {
scanf("%d", &preOrder[i]);
}
for (int i = 0; i < N; i++) {
scanf("%d", &inOrder[i]);
}
Node* root = createTree(preOrder, inOrder, N);
printf("该树的高度是: %d\n", getTreeHeight(root));
printf("该树的宽度是: %d\n", getTreeWidth(root));
printf("该树的叶节点个数是: %d\n", countLeafNode(root));
Node* newTreeRoot = mirrorCloneTree(root);
printf("该树的镜像树的层次遍历序列为:\n");
lavelOrderTraversal(newTreeRoot);
destoryTree(root);
destoryTree(newTreeRoot);
return 0;
}
样例输入：
7
4 1 3 2 6 5 7
1 2 3 4 5 6 7
其对应的二叉树为:
4
/ \
1 6
\ / \
3 5 7
/
2
样例输出：
该树的高度是: 4
该树的宽度是: 3
该树的叶节点个数是: 3
该树的镜像树的层次遍历序列为:
4 6 1 7 5 3 2
温馨提示：
- 函数的接口不允许修改，如果你觉得实现起来不方便，你可以自己重新写一个函数，然后直接调用你自己写的函数。比如
createTree函数你想使用递归来实现，但我给你的函数接口很难写成递归函数，那么你可以自己另外写一个递归函数，然后在createTree函数中直接调用你写的递归函数。
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
Node *lchild, *rchild;
}Node;
Node* createNode(int data) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->lchild = temp->rchild = NULL;
return temp;
}
Node* createTree(int preOrder[], int inOrder[], int N);
int getTreeHeight(Node* root);
int getTreeWidth(Node* root);
int countLeafNode(Node* root);
Node* mirrorCloneTree(Node* root);
void lavelOrderTraversal(Node* root);
void destoryTree(Node* root);
Node* _createTree(int preOrder[], int inOrder[], int preL, int preR, int inL, int inR);
void traverseTreeForWidth(Node* root, int currentlayerNum, int layerNodeCount[]);
int main() {
int N;
scanf("%d", &N);
int* preOrder = (int*)malloc(N * sizeof(int));
int* inOrder = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++) {
scanf("%d", &preOrder[i]);
}
for (int i = 0; i < N; i++) {
scanf("%d", &inOrder[i]);
}
Node* root = createTree(preOrder, inOrder, N);
printf("该树的高度是: %d\n", getTreeHeight(root));
printf("该树的宽度是: %d\n", getTreeWidth(root));
printf("该树的叶节点个数是: %d\n", countLeafNode(root));
Node* newTreeRoot = mirrorCloneTree(root);
printf("该树的镜像树的层次遍历序列为:\n");
lavelOrderTraversal(newTreeRoot);
destoryTree(root);
destoryTree(newTreeRoot);
return 0;
}
Node* createTree(int preOrder[], int inOrder[], int N) {
return _createTree(preOrder, inOrder, 0, N - 1, 0, N - 1);
}
Node* _createTree(int preOrder[], int inOrder[], int preL, int preR, int inL, int inR) {
if (preL > preR) return NULL;
Node* root = createNode(preOrder[preL]);
int k = inL;
while (inOrder[k] != preOrder[preL]) k++;
int leftTreeNum = k - inL;
root->lchild = _createTree(preOrder, inOrder, preL + 1, preL + leftTreeNum, inL, k - 1);
root->rchild = _createTree(preOrder, inOrder, preL + leftTreeNum + 1, preR, k + 1, inR);
return root;
}
int getTreeHeight(Node* root) {
if (root == NULL) return 0;
int left_high = getTreeHeight(root->lchild);
int right_high = getTreeHeight(root->rchild);
return __max(left_high, right_high) + 1;
}
int getTreeWidth(Node* root) {
int treeHeight = getTreeHeight(root);
int* layerNodeCount = (int*)malloc(treeHeight * sizeof(int));
memset(layerNodeCount, 0, treeHeight * sizeof(int));
traverseTreeForWidth(root, 0, layerNodeCount);
int maxWidth = -1;
for (int i = 0; i < treeHeight; i++) {
if (layerNodeCount[i] > maxWidth) maxWidth = layerNodeCount[i];
}
return maxWidth;
}
void traverseTreeForWidth(Node* root, int currentlayerNum, int layerNodeCount[]) {
if (root == NULL) return;
layerNodeCount[currentlayerNum]++;
traverseTreeForWidth(root->lchild, currentlayerNum + 1, layerNodeCount);
traverseTreeForWidth(root->rchild, currentlayerNum + 1, layerNodeCount);
}
int countLeafNode(Node* root) {
if (root == NULL) return 0;
if (root->lchild == NULL && root->rchild == NULL) return 1;
int left = countLeafNode(root->lchild);
int right = countLeafNode(root->rchild);
return left + right;
}
Node* mirrorCloneTree(Node* root) {
if (root == NULL) return NULL;
Node* temp = createNode(root->data);
temp->lchild = mirrorCloneTree(root->rchild);
temp->rchild = mirrorCloneTree(root->lchild);
return temp;
}
void lavelOrderTraversal(Node* root) {
if (root == NULL) return;
Node* Queue[1000];
int front = 0, rear = 0;
Queue[rear++] = root; //根节点入队
while (rear != front) { //只要队列不为空
Node* t = Queue[front++]; //出队
printf("%d ", t->data);
if (t->lchild != NULL) Queue[rear++] = t->lchild; //入队
if (t->rchild != NULL) Queue[rear++] = t->rchild;
}
printf("\n");
}
void destoryTree(Node* root) {
if (root == NULL) return;
destoryTree(root->lchild);
destoryTree(root->rchild);
free(root);
}
对于求树的宽度，还可以借助层次遍历
该代码用了C++ STL容器，可参考：https://www.cnblogs.com/skyfsm/p/6934246.html、https://www.cnblogs.com/mfryf/archive/2012/08/09/2629992.html
//该方法不需要对Node结构体修改，也不需要额外的数组记录每一层的节点数
int getTreeWidth_2(Node* root) {
if (root == NULL) return 0;
queue<Node*> Q;
Q.push(root);
int currentLayerWidth = 1; //根节点入队，此时当前这一层（第0层）的宽度是1
int treeWidth; //记录整棵树的宽度
while (Q.empty() == false) { //只要队列不为空
treeWidth = max(currentLayerWidth, treeWidth); //更新这棵树的最大宽度
while (currentLayerWidth--) { //把当前这一层的节点全部弹出
Node* p = Q.front(); Q.pop(); //弹出队首元素
if (p->lchild != NULL) {
Q.push(p->lchild);
}
if (p->rchild != NULL) {
Q.push(p->rchild);
}
}
//现在队列中存放的节点全部都是下一层的节点
currentLayerWidth = Q.size(); //进入下一层时更新该变量
}
return treeWidth;
}
第二题：后序遍历的第k个节点
题目
（这道题是清华大学的考研真题）
假设二叉树的节点定义如下：
其中节点的size成员表示：当前节点以及其孩子节点的总数，也可以理解为以该节点为根的子树当中，所有的节点个数。
struct BinNode{
int size; //当前节点以及其孩子节点的总数
BinNode *lchild,*rchild;
};
编写一个算法：返回后序遍历的第 K 个（K从1开始计数）节点的<u>指针</u>(该节点记为x)，要求时间复杂度不超过该节点的深度，即Ο(depth(x))
BinNode *rank(BinNode* t,int k){
//有效代码行数不超过12行
//不要尝试模拟后序遍历，时间复杂度会超时（按照清华的评分标准这题直接得0分）
}
这道题的代码的框架如下：
你<u>只需要实现</u>rankInPostorder 和generateEachNodeSize这两个函数。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* lchild, * rchild;
int size;
}Node;
Node* createNode(int data) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->lchild = temp->rchild = NULL;
return temp;
}
void setNodeChild(Node* root, Node* lchild, Node* rchild) {
root->lchild = lchild;
root->rchild = rchild;
}
//返回后序遍历的第K个（K从1开始计数）节点的指针
Node* rankInPostorder(Node* t, int k) {
}
//计算每个节点的size的值
//需要的话你可以把该函数的返回值改为int类型
void generateEachNodeSize(Node* root) {
}
int main() {
Node* root = createNode(1);
Node* node2 = createNode(2);
Node* node3 = createNode(3);
Node* node4 = createNode(4);
Node* node5 = createNode(5);
Node* node6 = createNode(6);
Node* node7 = createNode(7);
Node* node8 = createNode(8);
setNodeChild(root, node2, node3);
setNodeChild(node2, node4, node5);
setNodeChild(node3, NULL, node7);
setNodeChild(node5, node6, NULL);
setNodeChild(node4, NULL, node8);
generateEachNodeSize(root);
for (int i = 1; i <= 8; i++) {
Node* p = rankInPostorder(root, i);
printf("%d ", p->data);
}
printf("\n");
return 0;
}
如果你写的算法正确，程序应当输出：
8 4 6 5 2 7 3 1
该二叉树的结构为：
1
/ \
2 3
/ \ \
4 5 7
\ /
8 6
参考代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* lchild, * rchild;
int size;
}Node;
Node* createNode(int data) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->lchild = temp->rchild = NULL;
return temp;
}
void setNodeChild(Node* root, Node* lchild, Node* rchild) {
root->lchild = lchild;
root->rchild = rchild;
}
//返回后序遍历的第K个（K从1开始计数）节点的指针
Node* rankInPostorder(Node* root, int k) {
//检查参数是否合法
if (root == NULL || root->size < k) return NULL;
if (root->size == k) return root;
if (root->lchild == NULL) {
//如果没有左子树，则直接进入右子树搜索
return rankInPostorder(root->rchild, k);
}
int leftSize = root->lchild->size;
if (k <= leftSize) {
//左子树不为空，且根据左子树的size判断出目标在左子树，则进入左子树搜索
return rankInPostorder(root->lchild, k);
}
else {
//否则进入右子树，且需要更新k
return rankInPostorder(root->rchild, k - leftSize);
}
}
//计算每个节点的size的值
//需要的话你可以把该函数的返回值改为int类型
int generateEachNodeSize(Node* root) {
if (root == NULL) return 0;
int l = generateEachNodeSize(root->lchild);
int r = generateEachNodeSize(root->rchild);
root->size = l + r + 1;
return root->size;
}
int main() {
Node* root = createNode(1);
Node* node2 = createNode(2);
Node* node3 = createNode(3);
Node* node4 = createNode(4);
Node* node5 = createNode(5);
Node* node6 = createNode(6);
Node* node7 = createNode(7);
Node* node8 = createNode(8);
setNodeChild(root, node2, node3);
setNodeChild(node2, node4, node5);
setNodeChild(node3, NULL, node7);
setNodeChild(node5, node6, NULL);
setNodeChild(node4, NULL, node8);
generateEachNodeSize(root);
for (int i = 1; i <= 8; i++) {
Node* p = rankInPostorder(root, i);
printf("%d ", p->data);
}
printf("\n");
return 0;
}
参考资料
（请先将该代码弄懂再做作业）
C语言实现二叉树的遍历算法，参考代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
typedef struct Node {
int data;
struct Node* lchild, * rchild;
}Node;
Node* createNode(int data) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->lchild = temp->rchild = NULL;
return temp;
}
void setNodeChild(Node* root, Node* lchild, Node* rchild) {
root->lchild = lchild;
root->rchild = rchild;
}
void preorderTrav(Node* root) { //先序遍历
if (root == NULL) return;
printf("%d ", root->data); //最先访问根节点
preorderTrav(root->lchild);
preorderTrav(root->rchild);
}
void inorderTrav(Node * root) { //中序遍历
if (root == NULL) return;
inorderTrav(root->lchild);
printf("%d ", root->data); //中间的时候访问根节点
inorderTrav(root->rchild);
}
void postorderTrav(Node * root) { //后序遍历
if (root == NULL) return;
postorderTrav(root->lchild);
postorderTrav(root->rchild);
printf("%d ", root->data); //最后访问根节点
}
void levelTrav(Node * root) { //层次遍历
if (root == NULL) return;
Node * Queue[MAXN];
int front = 0, rear = 0;
Queue[rear++] = root; //根节点入队
while (rear != front) { //只要队列不为空
Node* t = Queue[front++]; //出队
printf("%d ", t->data);
if (t->lchild != NULL) Queue[rear++] = t->lchild; //入队
if (t->rchild != NULL) Queue[rear++] = t->rchild;
}
printf("\n");
}
int getTreeHeight(Node * root) {
if (root == NULL) return 0;
int left_high = getTreeHeight(root->lchild);
int right_high = getTreeHeight(root->rchild);
return max(left_high, right_high) + 1;
}
int main() {
Node* root = createNode(1);
Node* node2 = createNode(2);
Node* node3 = createNode(3);
Node* node4 = createNode(4);
Node* node5 = createNode(5);
Node* node6 = createNode(6);
Node* node7 = createNode(7);
Node* node8 = createNode(8);
setNodeChild(root, node2, node3);
setNodeChild(node2, node4, node5);
setNodeChild(node3, NULL, node7);
setNodeChild(node5, node6, NULL);
setNodeChild(node4, NULL, node8);
preorderTrav(root);
printf("\n");
inorderTrav(root);
printf("\n");
postorderTrav(root);
printf("\n");
levelTrav(root);
printf("Tree Height: %d\n", getTreeHeight(root));
return 0;
}
