实验五 根据先序和中序构造二叉树、二叉树的层序遍历
一、实验描述
- 给出一棵二叉树的先序（或后序）遍历结果，以及中序遍历结果，如何构造这棵树？假定遍历结果以数组方式输入，请写出相应函数，判断是否存在生成同样遍历结果的树，如果存在，构造这棵树。
- 二叉树的层序遍历。使用队列作为辅助存储，按树的结点的深度，从根开始依次访问所有结点。
二、问题分析与算法设计
1、根据先序和中序构造二叉树
1.1、分析
二叉树前序遍历的顺序为：
- 先遍历根节点；
- 随后递归地遍历左子树；
- 最后递归地遍历右子树。
二叉树中序遍历的顺序为：
- 先递归地遍历左子树；
- 随后遍历根节点；
- 最后递归地遍历右子树。
在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出根据前序和中序遍历构造二叉树的做法。
1.2、思路
对于任意一颗树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样一来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
2、二叉树的层序遍历
2.1、分析
二叉树的遍历的核心问题：二维结构的线性化
- 从节点访问器左右儿子节点
- 访问左儿子后，右儿子节点怎么办？
- 使用队列作为辅助存储，按树的结点的深度，从根开始依次访问所有结点。
2.2、思路
遍历从根节点开始，首先将根节点入队，然后开始执行循环：节点出队、访问该节点、其左右儿子入队。
层序基本过程：先根节点入队，然后：
Ⅰ从队列中取出一个元素；Ⅱ访问该元素所指节点Ⅲ若该元素所指节点的左、右孩子节点非空，则将其左、右孩子的指针顺序入队三、算法实现
1、构造二叉树
struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;};typedef struct TreeNode *BinTree;struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){ struct TreeNode *newNode; int p = 0; int i = 0; // 去除输入不合理的情况 if (preorder == NULL || inorder == NULL) { return NULL; } if (preorderSize <= 0 || inorderSize <= 0) { return NULL; } newNode = (struct TreeNode *) malloc(sizeof(struct TreeNode)); newNode->val = preorder[p]; // 根据前序取出根节点 newNode->left = NULL; newNode->right = NULL; for (i = 0; i < inorderSize; i ) { // 在中序中找到根节点，然后递归 if (inorder[i] == newNode->val) { newNode->left = buildTree(&preorder[p 1], i, inorder, i); // 递归构造左子树 newNode->right = buildTree(&preorder[p i 1], preorderSize - i - 1, &inorder[i 1], inorderSize - i - 1); // 递归构造右子树 break; } } return newNode;}2、层序遍历
// 层序void LevelOrderTraversal(SearchTree T) { Queue Q; SearchTree ST; if (!T) return; /* 如果是空树就直接返回 */ Q = CreateQueue(); Enqueue(T, Q); /* 将根节点入队 */ while (!IsEmpty(Q)) { ST = FrontAndDequeue(Q); printf("%d ", ST->Element); /* 访问取出队列的节点 */ if (ST->Left) Enqueue(ST->Left, Q); if (ST->Right) Enqueue(ST->Right, Q); }}四、实验结果
1、构造二叉树
测试代码：
// 测试int main(){ int preorder[5] = {3, 9, 20, 15, 7}; int inorder[5] = {9, 3, 15, 20, 7}; BinTree buildedTree = buildTree(preorder, 5, inorder, 5); printf("前序遍历："); PreOrderTraversal(buildedTree); printf("\n"); printf("中序遍历："); InOrderTraversal(buildedTree); printf("\n"); printf("后序遍历："); PostOrderTraversal(buildedTree); return 0;}输出结果：
即：
3 / 9 20 / 15 72、层序遍历
测试代码：
int main( ){ SearchTree T; Position P; int i; int j = 15; T = MakeEmpty( NULL ); // 创建一棵空树 for( i = 0; i < 50; i , j = ( j 7 ) % 50 ) // 将 50 个数插入树中 T = Insert( j, T ); for( i = 0; i < 50; i ) if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i ) // 测试查找函数 printf( "Error at %d\n", i ); /* 测试遍历 */ printf("先序遍历 \n"); PreOrderTraversal(T); printf("\n"); printf("中序遍历 \n"); InOrderTraversal(T); printf("\n"); printf("后序遍历 \n"); PostOrderTraversal(T); printf("\n"); printf("层序遍历 \n"); LevelOrderTraversal(T); printf("\n"); /* 测试遍历 */ return 0;}输出结果：
五、实验结论
1、构造二叉树
由于上面的算法使用的是线性查找，所以在二叉树平衡的情况下，其时间复杂度为 \(O(NlogN)\)，如果二叉树不平衡，则最坏情况下的时间复杂度为 \(O(N^2)\)。我们这里为了方便，就采取了简单的线性扫描。
如果想提高查找的效率，我们可以考虑使用哈希映射（HashMap）来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 \(O(1)\) 的时间对根节点进行定位了。
2、层序遍历
显然，对于二叉树中的每一个节点，我们仅访问了一次，因此，时间复杂度为 \(O(N)\)。
六、附：完整代码
1、构造二叉树
#include <stdio.h>#include <malloc.h>// Definition for a binary tree node.struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;};typedef struct TreeNode *BinTree;struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){ struct TreeNode *newNode; int p = 0; int i = 0; // 去除输入不合理的情况 if (preorder == NULL || inorder == NULL) { return NULL; } if (preorderSize <= 0 || inorderSize <= 0) { return NULL; } newNode = (struct TreeNode *) malloc(sizeof(struct TreeNode)); newNode->val = preorder[p]; // 根据前序取出根节点 newNode->left = NULL; newNode->right = NULL; for (i = 0; i < inorderSize; i ) { // 在中序中找到根节点，然后递归 if (inorder[i] == newNode->val) { newNode->left = buildTree(&preorder[p 1], i, inorder, i); // 递归构造左子树 newNode->right = buildTree(&preorder[p i 1], preorderSize - i - 1, &inorder[i 1], inorderSize - i - 1); // 递归构造右子树 break; } } return newNode;}void freeTree(struct TreeNode *T){ if (NULL == T) return; freeTree(T->left); freeTree(T->right); freeTree(T);}// 先序void PreOrderTraversal(struct TreeNode *T){ if (T) { printf("%d ", T->val); PreOrderTraversal(T->left); PreOrderTraversal(T->right); }}// 中序void InOrderTraversal(struct TreeNode *T) { if (T) { InOrderTraversal(T->left); printf("%d ", T->val); InOrderTraversal(T->right); }}// 后序void PostOrderTraversal(struct TreeNode *T) { if (T) { PostOrderTraversal(T->left); PostOrderTraversal(T->right); printf("%d ", T->val); }}// 测试int main(){ int preorder[5] = {3, 9, 20, 15, 7}; int inorder[5] = {9, 3, 15, 20, 7}; BinTree buildedTree = buildTree(preorder, 5, inorder, 5); printf("前序遍历："); PreOrderTraversal(buildedTree); printf("\n"); printf("中序遍历："); InOrderTraversal(buildedTree); printf("\n"); printf("后序遍历："); PostOrderTraversal(buildedTree); return 0;}2、层序遍历
tree.h
typedef int ElementType;#ifndef _Tree_H#define _Tree_Hstruct TreeNode; // 定义结构体节点typedef struct TreeNode *Position; // 指向节点的指针typedef struct TreeNode *SearchTree; // 搜索树的根节点SearchTree MakeEmpty( SearchTree T );Position Find( ElementType X, SearchTree T );Position FindMin( SearchTree T );Position FindMax( SearchTree T );SearchTree Insert( ElementType X, SearchTree T );SearchTree Delete( ElementType X, SearchTree T );ElementType Retrieve( Position P );/* 树的遍历方法 */void PreOrderTraversal(SearchTree T);void InOrderTraversal(SearchTree T);void PostOrderTraversal(SearchTree T);void LevelOrderTraversal(SearchTree T);/* 树的遍历方法 */#endiftree.c
#include "tree.h"#include <stdlib.h>#include "fatal.h"#include "queueli.h"struct TreeNode{ ElementType Element; // 树节点存储的元素 SearchTree Left; // 左子树 SearchTree Right; // 右子树};// 建立一棵空树SearchTreeMakeEmpty(SearchTree T){ if (T != NULL) { MakeEmpty(T->Left); // 递归删除左子树 MakeEmpty(T->Right); // 递归删除右子树 free(T); // 释放该节点 } return NULL;}// 二叉搜索树的查找操作PositionFind(ElementType X, SearchTree T){ if (T == NULL) return NULL; if (X < T->Element) // 如果待查找元素比根节点小，那么递归查找左子树 return Find(X, T->Left); else if (X > T->Element) // 如果待查找元素比根节点大，那么递归查找右子树 return Find(X, T->Right); else return T;}// 查找最小元素，即找出最左边的叶子节点PositionFindMin(SearchTree T){ if (T == NULL) return NULL; else if (T->Left == NULL) return T; else return FindMin(T->Left);}// 查找最大值PositionFindMax(SearchTree T){ if (T != NULL) while (T->Right != NULL) T = T->Right; return T;}// 插入操作SearchTreeInsert(ElementType X, SearchTree T){ if (T == NULL) { /* Create and return a one-node tree 创建并返回一个单节点树 */ T = malloc(sizeof(struct TreeNode)); if (T == NULL) FatalError("Out of space!!!"); // 空间用尽的情况 else { T->Element = X; // 赋值 T->Left = T->Right = NULL; // 左右子树置空 } } else if (X < T->Element) T->Left = Insert(X, T->Left); // 递归寻找合适的插入位置 else if (X > T->Element) T->Right = Insert(X, T->Right); /* Else X is in the tree already; we'll do nothing */ return T; /* Do not forget this line!! */}// 删除操作SearchTreeDelete(ElementType X, SearchTree T){ Position TmpCell; // 寻找节点 if (T == NULL) Error("Element not found"); else if (X < T->Element) /* Go left */ T->Left = Delete(X, T->Left); else if (X > T->Element) /* Go right */ T->Right = Delete(X, T->Right); else /* Found element to be deleted 找到了该删除的节点 */ { if (T->Left && T->Right) /* Two children 有两个孩子 */ { /* Replace with smallest in right subtree 用右子树中最小的节点进行替换 */ TmpCell = FindMin(T->Right); // 找出右子树中最小的节点 T->Element = TmpCell->Element; // 替换 T->Right = Delete(T->Element, T->Right); // 删除刚刚的那个在右子树中最小的节点 } else /* One or zero children 有 1 个或者 0 个孩子 */ { TmpCell = T; if (T->Left == NULL) /* Also handles 0 children */ T = T->Right; // 如果左子树为空，那么将 T 更新为右子树，下同 else if (T->Right == NULL) T = T->Left; free(TmpCell); // 释放原来的 T 节点 } } return T;}// 取出 Position P 中的元素ElementTypeRetrieve(Position P){ return P->Element;}// 先序void PreOrderTraversal(SearchTree T){ if (T) { printf("%d ", T->Element); PreOrderTraversal(T->Left); PreOrderTraversal(T->Right); }}// 中序void InOrderTraversal(SearchTree T) { if (T) { InOrderTraversal(T->Left); printf("%d ", T->Element); InOrderTraversal(T->Right); }}// 后序void PostOrderTraversal(SearchTree T) { if (T) { PostOrderTraversal(T->Left); PostOrderTraversal(T->Right); printf("%d ", T->Element); }}// 层序void LevelOrderTraversal(SearchTree T) { Queue Q; SearchTree ST; if (!T) return; /* 如果是空树就直接返回 */ Q = CreateQueue(); Enqueue(T, Q); /* 将根节点入队 */ while (!IsEmpty(Q)) { ST = FrontAndDequeue(Q); printf("%d ", ST->Element); /* 访问取出队列的节点 */ if (ST->Left) Enqueue(ST->Left, Q); if (ST->Right) Enqueue(ST->Right, Q); }}queueli.h
#include "tree.h"typedef Position ElementType1;#ifndef _Queueli_h#define _Queueli_hstruct Node;struct QNode;typedef struct Node *PtrToNode; // 指向Node节点的指针typedef struct QNode *Queue; // 队列头，也是指向QNode节点的指针int IsEmpty(Queue Q);Queue CreateQueue(void);void DisposeQueue(Queue Q);void MakeEmpty1(Queue Q);void Enqueue(ElementType1 X, Queue Q);ElementType1 Front(Queue Q);void Dequeue(Queue Q);ElementType1 FrontAndDequeue(Queue Q);#endifqueueli.c
#include "queueli.h"#include "fatal.h"#include <stdio.h>// #include "tree.h"// 节点struct Node{ ElementType1 Element; PtrToNode Next;};struct QNode{ PtrToNode rear; // 指向队尾节点 PtrToNode front; // 指向对头节点};// 判断队列是否为空int IsEmpty(Queue Q){ return (Q->front == NULL);}Queue CreateQueue(void){ Queue Q; Q = malloc(sizeof(struct QNode)); if (Q == NULL) FatalError("Out of space!!!"); // 空间用尽警告 Q->front = NULL; Q->rear = NULL; MakeEmpty1(Q); // 还是感觉有些多此一举 return Q;}// 创建一个空队列void MakeEmpty1(Queue Q){ if (Q == NULL) Error("Must use CreateQueue first"); else while (!IsEmpty(Q)) Dequeue(Q);}// 清除队列void DisposeQueue(Queue Q){ if (Q != NULL) { MakeEmpty1(Q); free(Q); }}// 入队操作void Enqueue(ElementType1 X, Queue Q){ PtrToNode TmpCell; TmpCell = malloc(sizeof(struct Node)); if (TmpCell == NULL) FatalError("Out of space!!!"); TmpCell->Element = X; TmpCell->Next = NULL; if (Q->rear == NULL) { // 此时队列为空 Q->rear = TmpCell; Q->front = TmpCell; } else { // 不为空 Q->rear->Next = TmpCell; // 将节点入队 Q->rear = TmpCell; // rear 仍然保持最后 }}// 取出队首元素ElementType1 Front(Queue Q){ if (!IsEmpty(Q)) return Q->front->Element; Error("Empty queue"); return NULL; // Return value used to avoid warning}// 出队操作void Dequeue(Queue Q){ PtrToNode FrontCell; if (IsEmpty(Q)) Error("Empty queue"); else { FrontCell = Q->front; if (Q->front == Q->rear) { // 只有一个元素 Q->front = Q->rear = NULL; } else { // 有多个元素时 Q->front = Q->front -> Next; // 先将front指向队首元素的下一个元素 } free(FrontCell); // 不要忘了释放出对的节点 }}// 在出队的同时返回该元素，即队首元素ElementType1 FrontAndDequeue(Queue Q){ ElementType1 X = NULL; if (IsEmpty(Q)) Error("Empty queue"); else { X = Front(Q); Dequeue(Q); } return X;}main.c
#include "tree.h"#include <stdio.h>int main( ){ SearchTree T; Position P; int i; int j = 15; T = MakeEmpty( NULL ); // 创建一棵空树 for( i = 0; i < 50; i , j = ( j 7 ) % 50 ) // 将 50 个数插入树中 T = Insert( j, T ); for( i = 0; i < 50; i ) if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i ) // 测试查找函数 printf( "Error at %d\n", i ); /* 测试遍历 */ printf("先序遍历 \n"); PreOrderTraversal(T); printf("\n"); printf("中序遍历 \n"); InOrderTraversal(T); printf("\n"); printf("后序遍历 \n"); PostOrderTraversal(T); printf("\n"); printf("层序遍历 \n"); LevelOrderTraversal(T); printf("\n"); /* 测试遍历 */ return 0;}fatal.h
#include <stdio.h>#include <stdlib.h>#define Error(Str) FatalError( Str )#define FatalError(Str) fprintf( stderr, "%s\n", Str ), exit( 1 )参考：
赞 (0)