Icoding平台第五次作业解析-树二叉树

T1

先序遍历
已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法：

void pre_order(BiTree root);

在遍历过程中，pre_order函数需要调用 visit_node 函数来实现对结点的访问，该函数声明如下：

void visit_node(BiTNode *node);

二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
DataType data;
struct Node* left;
struct Node* right;
}BiTNode, *BiTree;

遍历所使用栈的相关操作如下：

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
ElemType elem[Stack_Size];
int top;
}Stack;

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-05-10, Sun, 17:50:25
    * 最高分数：100
    */
   
   
   #include "bitree.h" //请不要删除，否则检查不通过
   #include <stdio.h>
   #include <stdlib.h>
   
   void pre_order(BiTree root)
   {
       BiTNode* p;
       Stack s;
       p = root;
       init_stack(&s);
       while (p || !is_empty(&s)) {
           if (p != NULL) {
               visit_node(p);
               push(&s, p);
               p = p->left;
           } else {
               pop(&s, &p);
               p = p->right;
           }
       }
   }

---

T2

路径
假设二叉树采用二叉链表方式存储， root指向根结点，node 指向二叉树中的一个结点，编写函数 path，计算root到 node 之间的路径，（该路径包括root结点和 node 结点）。path 函数声明如下：

bool path(BiTNode* root, BiTNode* node, Stack* s);

其中，root指向二叉树的根结点，node指向二叉树中的另一结点，s 为已经初始化好的栈，该栈用来保存函数所计算的路径，如正确找出路径，则函数返回 true，此时root在栈底，node在栈顶；如未找到，则函数返回 false, 二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
DataType data;
struct Node* left;
struct Node* right;
}BiTNode, *BiTree;

栈的相关定义及操作如下：

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
ElemType elem[Stack_Size];
int top;
}Stack;

void init_stack(Stack S); // 初始化栈
bool push(Stack S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack S, ElemType px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack S); // 栈为空时返回 true，否则返回 false

在提示中，树用缩进的形式展示，如二叉树【pic】，其缩进形式为：【pic】

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-05-10, Sun, 18:00:41
    * 最高分数：100
    */
   
   
   #include "bitree.h" //请不要删除，否则检查不通过
   #include <stdio.h>
   #include <stdlib.h>
   
   bool path(BiTNode* root, BiTNode* node, Stack* s)
   {
       BiTree Tr = root, p = NULL;
       if (Tr == NULL || node == NULL || !is_empty(s))
           return false;
       while (Tr || !is_empty(s)) {
           while (Tr) {
               push(s, Tr);
               if (Tr == node)
                   return true;
               Tr = Tr->left;
           }
           top(s, &Tr);
           if (!Tr->right || Tr->right == p) {
               p = Tr;
               pop(s, &Tr);
               Tr = NULL;
           } else
               Tr = Tr->right;
       }
       return false;
   }

---

T3

共同祖先
假设二叉树采用二叉链表方式存储， root指向根结点，p所指结点和q所指结点为二叉树中的两个结点，编写一个计算它们的最近的共同祖先，函数定义如下：

BiTNode * nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q);

其中 root 指向二叉树的根结点，p 和 q 分别指向二叉树中的两个结点。
提示：在完成本题时，可利用 path 函数获取p和q两个结点到根结点之间的路径，之后再计算两条公共路径得出最近的共同祖先。path函数及栈相关定义如下：

bool path(BiTNode* root, BiTNode* node, Stack* s);

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
ElemType elem[Stack_Size];
int top;
}Stack;

void init_stack(Stack S); // 初始化栈
bool push(Stack S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack S, ElemType px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack S); // 栈为空时返回 true，否则返回 false

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-05-10, Sun, 17:54:08
    * 最高分数：100
    */
   
   
   #include "bitree.h" //请不要删除，否则检查不通过
   #include <stdio.h>
   #include <stdlib.h>
   
   BiTNode* nearest_ancestor(BiTree root, BiTNode* p, BiTNode* q)
   {
       Stack *pl, *ql;
       pl = malloc(sizeof(Stack));
       ql = malloc(sizeof(Stack));
       init_stack(pl);
       init_stack(ql);
       if (path(root, p, pl) == false || path(root, q, ql) == false)
           return NULL;
   
       ElemType temp;
       for (int i = 0; i <= pl->top && i < ql->top; i++) {
           if (pl->elem[i] != ql->elem[i])
               break;
           else
               temp = pl->elem[i];
       }
       return temp;
   }

---

T4

树转二叉树
使用队列，编写transfrom函数，将普通树转换成对应的二叉树。二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
DataType data;
struct Node* left;
struct Node* right;
}BiTNode, *BiTree;

普通树节点的定义如下：

#define MAX_CHILDREN_NUM 5
struct _CSNode
{
DataType data;
struct _CSNode *children[MAX_CHILDREN_NUM];
};
typedef struct _CSNode CSNode;

其中，子树的根节点的指针存放在children数组的前k个元素中，即如果children[i]的值为NULL，而children[i-1]不为NULL，则表明该结点只有i棵子树，子树根结点分别保存在children[0]至children[i-1]中。
队列相关定义及操作如下：

struct __Queue
{
int i, j; //指向数组内元素的游标
void **array;
};
typedef struct __Queue Queue;

Queue* create_queue(); //创建队列
bool is_empty_queue(Queue tree); //队为空返回true,不为空时返回false
void del_queue(Queue *tree); //结点指针出队
void add_queue(Queue *tree, void *node); //结点指针入队
void free_queue(Queue *tree); //释放队列

transform函数定义如下：

BiTNode* transform(CSNode *root);

其中 root 为普通树的根结点，函数返回该树对应二叉树的根结点。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-05-10, Sun, 17:57:54
    * 最高分数：100
    */
   
   
   #include "bitree.h" //请不要删除，否则检查不通过
   #include <stdio.h>
   #include <stdlib.h>
   
   BiTNode* transform(CSNode* root)
   {
       if (root == NULL)
           return NULL;
   
       BiTree broot = (BiTree)malloc(sizeof(struct Node));
       broot->data = root->data;
       broot->left = broot->right = NULL;
   
       Queue* queue = create_queue();
       Queue* bqueue = create_queue();
       add_queue(queue, root);
       add_queue(bqueue, broot);
       while (!is_empty_queue(queue)) {
           CSNode* node = del_queue(queue);
           BiTree bTreeNode = del_queue(bqueue);
           int i;
           BiTree former = NULL;
           for (i = 0; i < MAX_CHILDREN_NUM; i++) {
               if (node->children[i]) {
                   BiTree bnode = (BiTree)malloc(sizeof(struct Node));
                   bnode->left = bnode->right = NULL;
                   bnode->data = node->children[i]->data;
                   if (i == 0)
                       bTreeNode->left = bnode;
                   else
                       former->right = bnode;
                   former = bnode;
   
                   add_queue(queue, node->children[i]);
                   add_queue(bqueue, bnode);
               }
           }
       }
       free(queue->array);
       free(queue);
       free(bqueue->array);
       free(bqueue);
       return broot;
   }

---