1-8 最宽层次结点数

分数 4

作者 DS课程组

单位临沂大学

本题要求实现一个函数，返回给定的二叉树的中最宽层次的结点数，这里最宽层次指的是该层上的结点最多。

函数接口定义：

int MaxWidth(BiTree T);

T是二叉树树根指针，MaxWidth函数统计T中每层结点数并返回最大值，空树返回0。

其中BinTree结构定义如下：

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode
{
   ElemType data;
   struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree Create();/* 细节在此不表 */

int MaxWidth(BiTree T);

int main()
{
   BiTree T = Create();
   printf("The max-width of the tree is %d.\n",MaxWidth(T)); 
   return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

输入为由字母和’#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据：

AB#DF##G##C##

输出样例（对于图中给出的树）：

二叉树.png

The max-width of the tree is 2.

解析

int MaxWidth(BiTree T) {
	if (T == NULL) {
		return 0;
	}
	BiTree queue[100];
	int front = 0;
	int rear = 0;
	int maxWidth = 0;
	
	queue[rear++] = T;
	while (front < rear) {
		int levelSize = rear - front;
		if (levelSize > maxWidth) {
			maxWidth = levelSize;
		}
		for (int i = 0; i < levelSize; i++) {
			BiTree node = queue[front];
			front++;
			// 左孩子入队
			if (node->lchild != NULL) {
				queue[rear++] = node->lchild;
			}
			// 右孩子入队
			if (node->rchild != NULL) {
				queue[rear++] = node->rchild;
			}
		}
	}
	return maxWidth;
}

1-9 确定二叉树（先序序列+中序序列）

分数 3

作者黄龙军

单位绍兴文理学院

要求实现函数，根据二叉树的先序序列和中序序列确定二叉树并返回指向二叉树根结点的指针。二叉树采用二叉链表存储，结点结构如下：

struct BiTNode {                                  // 结点结构 
    int data;                                     // 数据域 
    BiTNode *lchild,*rchild;                      // 左右孩子指针 
    BiTNode(int d,BiTNode *left,BiTNode *right) { // 构造函数 
        data=d;
        lchild=left;
        rchild=right;
    }
};

函数接口定义：

BiTNode* CreateBT(int* pre, int *in, int n);

其中参数 pre是指向先序序列数组首元素的指针， in是指向中序序列数组首元素的指针，n是结点总数。

裁判测试程序样例：

#include<iostream>
using namespace std;

struct BiTNode {                                  // 结点结构 
    int data;                                     // 数据域 
    BiTNode *lchild,*rchild;                      // 左右孩子指针 
    BiTNode(int d,BiTNode *left,BiTNode *right) { // 构造函数 
        data=d;
        lchild=left;
        rchild=right;
    }
};

void PostOrder(BiTNode* p, int &cnt)    // 后序遍历
//  根据先序序列和中序序列确定二叉树，pre是指向后序序列数组首元素的指针，in是指向中序序列数组首元素的指针 ，n是结点总数
BiTNode* CreateBT(int* pre, int *in, int n);  

// 根据先序序列和中序序列创建二叉树并后序遍历之
int main() {
    int n;
    while(cin>>n) {
        int pre[n], in[n], cnt=0;
        for(int i=0; i<n; i++) cin>>pre[i];
        for(int i=0; i<n; i++) cin>>in[i];
        BiTNode* root=CreateBT(pre,in,n);
        PostOrder(root, cnt);
        cout<<endl;
    }
    return 0;
}

//请在此处填写答案

void PostOrder(BiTNode* p, int &cnt) {                 // 后序遍历
    if(!p) return;
    PostOrder(p->lchild, cnt);
    PostOrder(p->rchild, cnt);
    cnt++;
    if (cnt>1) cout<<" ";
    cout<<p->data;
}

输入样例：

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

输出样例：

7 4 2 8 9 5 6 3 1

解析

BiTNode* CreateBT(int* pre, int* in, int n) {
    if (n <= 0) {
        return NULL;
    }
    int rootVal = pre[0];
    int rootIndex = 0;

    for (; rootIndex < n; rootIndex++) {
        if (in[rootIndex] == rootVal) {
            break;
        }
    }
    int leftSize = rootIndex;  // 左子树结点数
    BiTNode* leftChild = CreateBT(pre + 1, in, leftSize);

    // 递归构建右子树
    int rightSize = n - leftSize - 1;  // 右子树结点数
    BiTNode* rightChild = CreateBT(pre + 1 + leftSize, in + leftSize + 1, rightSize);

    return new BiTNode(rootVal, leftChild, rightChild);
}