数据结构第三次作业

作者: XXX_f47c | 来源:发表于2019-05-24 14:19 被阅读0次

数据结构第三次作业
赵浚皓思维导图
第三次作业
LDZ4+274+花卉作业补交
#橙子创意思维训练营#思维导图练习之三
#知识萃取实验室#
【创意思维第三章】第三次作业
2017-12-08
【凯乐恩首届思维导图管理师认证班】第二周作业绘制规则
第三次课后作业

第一题：二叉树的基础算法

题目

先根据二叉树的先序、中序遍历序列还原该二叉树，求出这棵二叉树的高度和宽度，以及其叶节点的个数。再将这棵二叉树在内存当中镜像克隆一份，输出克隆的这棵树的层次遍历序列，最后再释放掉这两棵树所占的内存空间。

你需要实现以下几个函数：

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;
}