《算法笔记》中树与二叉树专题有哪些练习题？

本文共计1076个文字，预计阅读时间需要5分钟。

1. 复原二叉树（由前序和中序遍历求后序遍历）题目描述：小明确在数据结构的学习中，遇到了一个问题。已知一棵二叉树的前序遍历和中序遍历的结果，要求求出这棵二叉树的后序遍历结果。请你完成这个任务。具体要求：- 给定一棵二叉树的前序遍历和中序遍历结果，输出该二叉树的后序遍历结果。- 输入格式：第一行输入前序遍历结果，第二行输入中序遍历结果，用空格分隔。- 输出格式：输出后序遍历结果，用空格分隔。- 输入样例：

12 4 7 3 5 6 8

42 7 1 5 3 8 6

74 2 8 6 5 3 1

1、复原二叉树（由前序和中序求后序）

题目描述 小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。 输入 输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。 输出 对于每组输入，输出对应的二叉树的后续遍历结果。

DBACEGF ABCDEFG BCAD CBAD ACBFGED CDAB

#include <iostream> #include<cstring> using namespace std; const int maxN=1000; //分别存储前序序列、中序序列 char pre[maxN],in[maxN]; struct Node { char data; Node* lchild; Node* rchild; }; //根据前序序列和中序序列构建一棵二叉树 Node* create(int preL,int preR,int inL,int inR) { if(preL>preR)return NULL;//递归边界，前序序列长度小于等于0时结束 Node* root=new Node;//创建根节点 root->data=pre[preL];//先序序列的第一个就是根节点 int k; for(k=inL;k<=inR;k++) { if(in[k]==pre[preL])break;//找到根节点在中序序列中的位置 } int numLeft=k-inL;//左子树的节点个数 //注意区间 root->lchild=create(preL+1,preL+numLeft,inL,k-1); root->rchild=create(preL+numLeft+1,preR,k+1,inR); return root; } //二叉树的后序遍历，左右根顺序 void postOrder(Node* root) { if(root==NULL)return; postOrder(root->lchild); postOrder(root->rchild); printf("%c",root->data); } int main() { while(scanf("%s%s",pre,in)!=EOF) { int preLen=strlen(pre); int inLen=strlen(in); Node* root=create(0,preLen-1,0,inLen-1); postOrder(root); printf("\n"); } return 0; }

2、二叉树遍历

题目描述 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入

输入包括1行字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

a#b#cdef##### a## a b f e d c a

#include<iostream> #include<cstring> using namespace std; char pre[105]; int pos; struct Node { char data; Node* lchild; Node* rchild; }; //创建空节点 Node* createNode() { Node* node=new Node; node->lchild=NULL; node->rchild=NULL; return node; } //创建二叉树 Node* createTree() { int len=strlen(pre); if(len==0||pos==len)return NULL;//数据为空或已经遍历完 if(pre[pos]=='#')//空树，直接遍历下一个，然后返回空 { pos++; return NULL; } Node* root=createNode();//先创建一个根节点 root->data=pre[pos++]; //递归创建左右子树 root->lchild=createTree(); root->rchild=createTree(); return root; } //二叉树的中序遍历，左根右顺序 void inOrder(Node* root) { if(root==NULL)return; inOrder(root->lchild); printf("%c ",root->data); inOrder(root->rchild); } int main() { while(scanf("%s",pre)!=EOF) { pos=0; Node* root=createTree(); inOrder(root); printf("\n"); } return 0; }