8606 二叉树的构建及遍历操作【有手就行】
Description
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），’#'字符表示空树，构造二叉链表表示的二叉树T；再输出三种遍历序列。本题只给出部分代码,请补全内容。
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // 生成根结点
_______________________ // 构造左子树
_________________________ // 构造右子树
}
return OK;
} // CreateBiTree
Status PreOrderTraverse( BiTree T) {
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // PreOrderTraverse
Status InOrderTraverse( BiTree T) {
// 中序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // InOrderTraverse
Status PostOrderTraverse( BiTree T) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // PostOrderTraverse
int main() //主函数
{
//补充代码
}//main
输入格式
第一行：输入一棵二叉树的先序遍历序列
输出格式
第一行：二叉树的先序遍历序列
第二行：二叉树的中序遍历序列
第三行：二叉树的后序遍历序列
输入样例
AB##C##
输出样例
ABC
BAC
BCA
代码实现
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c", &ch);
if (ch == '#') T = NULL;
else {
if (!(T = (BiTNode *) malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree
Status PreOrderTraverse(BiTree T) {
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (T == NULL)return ERROR;
cout << T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
} // PreOrderTraverse
Status InOrderTraverse(BiTree T) {
// 中序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (!T)return ERROR;
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
} // InOrderTraverse
Status PostOrderTraverse(BiTree T) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (!T)return ERROR;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data;
} // PostOrderTraverse
int main() //主函数
{
//补充代码
BiTree P;
CreateBiTree(P);
PreOrderTraverse(P);cout<<endl;
InOrderTraverse(P);cout<<endl;
PostOrderTraverse(P);cout<<endl;
}//main
17121 求二叉树各种节点数【背关系】
Description
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），’#'字符表示空树，构造二叉链表表示的二叉树T,并求此二叉树中度为2的节点总数，度为1的节点总数，度为0的节点总数
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // 生成根结点
_______________________ // 构造左子树
_________________________ // 构造右子树
}
return OK;
} // CreateBiTree
int main() //主函数
{
//补充代码
}//main
输入格式
第一行输入先序次序二叉树中结点
输出格式
第一行输出度为2的节点数
第二行输出度为1的节点数
第三行输出度为0的节点数
输入样例
ABC###D##
输出样例
1
1
2
代码实现
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
int n0=0,n=0;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data=ch; // 生成根结点
n++;
CreateBiTree(T->lchild);// 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree
void f(BiTree &T){
if(!T)return;
if(!T->lchild&&!T->rchild)n0++;
f(T->lchild);
f(T->rchild);
}
int main() //主函数
{
//补充代码
BiTree T;
CreateBiTree(T);
f(T);
printf("%d\n%d\n%d\n",n0-1,n-2*n0+1,n0);
//n0为叶子节点数
//叶子节点数=度2节点数+1
//所有节点树-叶子节点树-度2节点数=度1节点数
}//main
18924 二叉树的宽度【可偷懒】
Description
二叉树的宽度指的是具有节点数目最多的那一层的节点个数。
1
/
2 3
/
4
答案为2, 第二层节点数最多，为2个节点。
输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n,结点1为树根。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的宽度。
输入样例
5
1 2
1 3
2 4
2 5
输出样例
2
代码实现【二维数组偷懒法】
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> array(50);
array[0].push_back(1);
int n;
cin >> n;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
for(int j=0;j<50;j++){
if(array[j].back()>=x){
array[j+1].push_back(y);
break;
}
}
}
int max=0;
for(int i=0;i<50;i++){
if(max<array[i].size())max=array[i].size();
}
cout << max<<endl;
return 0;
}
18724 二叉树的遍历运算【值得一看★】
Description
二叉树的三种遍历都可以通过递归实现。
如果我们知道一棵二叉树的先序和中序序列，可以用递归的方法求后序遍历序列。
输入格式
两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。
输出格式
一个字符串，树的后序序列。
输入样例
abcde
bcade
输出样例
cbeda
代码实现
#include <iostream>
#include <cstring>
using namespace std;
char pre[1000],mid[1000],res[1000];
void cut(char pre[],char mid[],int len,int loc){
if(len<=0)return;
int i=0;
while(pre[0]!=mid[i])i++;//找到中序中的根节点
cut(pre+1,mid,i,loc-(len-i-1)-1);//loc - 右子树长度 - 1 = 左子树根节点该在的位置，也就是根节点左边的字符
cut(pre+i+1,mid+i+1,len-i-1, loc - 1);//loc - 1 = 右子树根节点该在的位置，也就是
res[loc]=pre[0];//loc 为 根节点在后序序列中该在位置
}
int main() {
cin>>pre>>mid;
int len=strlen(mid);
cut(pre,mid,len,len-1);
cout<<res<<endl;
return 0;
}
18923 二叉树的直径【值得一看★】
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
1
/
2 3
/ \
4 5
答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n。
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的直径。
输入样例
5
1 2
1 3
2 4
2 5
输出样例
3
代码实现
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
//插入数据到指定树下
void insertData(BiTree &T, ElemType data) {
BiTree P = new BiTNode;//P是一个新子树指针
P->data = data;
P->lchild = NULL;
P->rchild = NULL;
if (T == NULL) {
T = P;
}
//先左后右
else {
if (T->lchild == NULL) {
T->lchild = P;
} else {
T->rchild = P;
}
}
}
//先序查找父元素
void preOrderSearch(BiTree T, ElemType x, BiTree &result) {
if (T) {
//cout <<"CMP "<< T->data <<" AND "<<x<<endl;
if (T->data == x){
result = T;
}
preOrderSearch(T->lchild, x, result);
preOrderSearch(T->rchild, x, result);
}
} // PreOrder
//递归求最大深度
int maxDiameter = 0;
int MaxDepth(BiTree &T) {
if (T == NULL) return 0;
int leftDepth = MaxDepth(T->lchild);
int rightDepth = MaxDepth(T->rchild);
int diameter = leftDepth + rightDepth;
maxDiameter = diameter > maxDiameter ? diameter : maxDiameter;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() //主函数
{
BiTree P = NULL;
int n;
cin >> n;
n--;
insertData(P, 1);//第一个节点，手动插入（待优化）
// PreOrderShow(P);
while (n--) {
ElemType f, z;
cin >> f >> z;
BiTree res = NULL;
preOrderSearch(P, f, res);//查找到要插入的子树
insertData(res, z);
//PreOrderShow(res);
}
MaxDepth(P);
cout << maxDiameter;
}//main
8609 哈夫曼树【值得一看★★★】
Description
利用静态链表建立赫夫曼树，建树过程中要求左子树权值小于右子树权值，求各结点的编码。要求：叶子结点的个数n及结点值由键盘录入。本题给出程序代码,要求修改以满足测试要求.
#include "stdio.h"
#include "malloc.h"
#include "string.h"
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//在HT[1..n]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
{
int i;
s1=-1;s2=-1;
for (i=1;i<=n;i++) {
if (HT[i].parent==0)
if (s1==-1) s1=i;
else
if (s2==-1 )
if (HT[i].weight0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
unsigned int c, f;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getch();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getch();
}
//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); //释放工作空间
} //HuffmanCoding
void main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
printf("Node Number:");
scanf("%d",&n); //权值个数
w=(int *)malloc(n*sizeof(int));
printf("Input weights:");
for ( i=0;i<n;i++) //录入权值
scanf("%d",&w[i]);
HC=(char **)malloc((n+1)*sizeof(char*)); //0空间未用
HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));//0空间未用
HuffmanCoding(HT, HC, w, n);
printf("\n");
for (i = 1; i<n+1; i++){
puts(HC[i]); //输出哈夫曼编码
free(HC[i]); //释放空间
}
free(HC);
free(HT);
}//main
输入格式
第一行：权值个数
第二行：输入n个权值，用空格分隔
输出格式
输出n行
每行表示各权值对应的哈夫曼编码
输入样例
8
5 29 7 8 14 23 3 11
输出样例
0001
10
1110
1111
110
01
0000
001
代码实现
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include <iostream>
using namespace std;
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//在HT[1..n]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
{
s1 = 0;//0单元不用
s2 = 0;
//找第一个
for (int i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (s1 == 0) s1 = i;//假设当前节点最小（初始）
else if (HT[i].weight < HT[s1].weight)s1 = i;
}
}
for (int i = 1; i <= n; i++) {
//跳过s1找s2，如果找不到s2将=0
if (HT[i].parent == 0&& i != s1) {
if (s2 == 0)s2 = i;//假设当前节点最小（初始）
if (HT[i].weight < HT[s2].weight )s2 = i;
}
}
}
void createHuffmanTree(HuffmanTree &HT, int n) {
if (n <= 1) return;
int m = 2 * n - 1;//从权值节点数目推树的节点个数
HT = new HTNode[m + 1]; // 0号单元未用，实际大小需+1
for (int i = 0; i <= m; i++) { //初始化所有节点
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) { //输入权值节点（下标1到n）
cin >> HT[i].weight;
}
for (int i = n + 1; i <= m; i++) { // 即将合成的树放在i 一直往后退
int s1, s2;
Select(HT, i - 1, s1, s2);//在新树前（i前）选两颗权值最小的
//新树生成
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int n) {
HC = new char*[n + 1];//二级指针，储存每个节点的编码
char *tmp = new char[n];//每个节点逆推得到的编码临时储存（定长）
tmp[n - 1] = '\0';// 编码结束符
for (int i = 1; i <= n; i++) {// 逐个节点求哈夫曼编码,这里1-n的节点全为初始节点
int start = n - 1;// 编码结束符位置（倒推用）
//一直回溯
int child = i, par = HT[i].parent;//子节点，双亲节点下标
while(par != 0){
if (HT[par].lchild == child) tmp[--start] = '0';//在父母的左边
else tmp[--start] = '1';//在父母的右边
child = par;
par = HT[par].parent;
}
HC[i] = new char[n-start];// 为第i个字符编码分配空间,变长编码实现
strcpy(HC[i], &tmp[start]); //缩短
}
delete tmp; //释放工作空间
} //HuffmanCoding
int main() {
int i, n;
HuffmanTree HT;
HuffmanCode HC;
cin>>n; //权值个数
//创建哈夫曼树
createHuffmanTree(HT, n);
//获取编码
HuffmanCoding(HT, HC, n);
//输出哈夫曼编码
for (i = 1; i < n + 1; i++)cout <<HC[i]<<endl;
//释放
delete HC;
delete HT;
}//main