树型实验
实验目的和要求
实验目的
1. 熟悉二叉树的基本运算和各种遍历算法的实现
2. 熟悉二叉搜索树的概念和相关算法的实现。
3. 熟悉堆的概念和相关算法的实现。
实验要求：
编程实现如下功能：
二叉树的遍历
本题要求给定二叉树的4种遍历。
函数接口定义：
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};
要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};
BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Inorder:"); InorderTraversal(BT); printf("\n");printf("Preorder:"); PreorderTraversal(BT); printf("\n");printf("Postorder:"); PostorderTraversal(BT); printf("\n");printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");return 0;
}
输出样例（对于图中给出的树）：
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H
是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes
No
No
堆中的路径
将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3
输出样例:
24 23 10
46 23 10
26 10
哈夫曼编码
对于给定的文本内容，要求采用哈夫曼编码并输出编码后的内容。文本内容由英文字母构成，这里约定不区分字母的大小写。注意，这里约定构造哈夫曼树时，任一结点的左孩子权值不大于右孩子权值，哈夫曼编码时，左分支写'0'右分支写'1'；若两个字母的权值相等，则字典序小的字母优先；对于相等的权值，按出现的先后顺序处理。
例如，对于样例1，因不区分大小写，若按大写字母处理，则字母A、B、C、D的出现次数为4、1、2、1，则B对应的1为左孩子，D对应的1为右孩子，得到的父结点权值为2，比原有的2晚出现，因此原来的2为左孩子，新得到的2作为右孩子，对于两个权值4也类似处理。构造所得的哈夫曼树如下图所示。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据在一行上输入一个字符串（仅由大小写英文字母构成且长度不超过360，至少包含2种字母）表示文本内容。
输出格式:
对于每组测试数据，输出哈夫曼编码后的内容。
输入样例:
AcBDaCAA
eAbCDaAAA
输出样例:
01011011101000
01110000010101111
实验过程与结果
二叉树的遍历
void InorderTraversal( BinTree BT )
{if(BT){InorderTraversal(BT->Left);printf(" %c",BT->Data);InorderTraversal(BT->Right);}
}void PreorderTraversal( BinTree BT )
{if(BT){printf(" %c",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);}
}void PostorderTraversal( BinTree BT )
{if(BT){PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c",BT->Data);}
}void LevelorderTraversal( BinTree BT )
{if(BT){int i,j;BinTree p[100];i=j=0;p[j++]=BT;while(i<j){printf(" %c",p[i]->Data);if(p[i]->Left)p[j++]=p[i]->Left;if(p[i]->Right)p[j++]=p[i]->Right;i++;}}
}是否同一棵二叉搜索树
#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode *Tree;
struct TreeNode
{int v;Tree Left, Right;int flag; /*判别一个序列是否与树一致，结点访问标记*/
};Tree NewNode(int V)
{Tree T = (Tree)malloc(sizeof(struct TreeNode));T->v = V;T->Left = T->Right = NULL;T->flag = 0; //没被访问过的结点flag = 0,被访问过的结点flag = 1return T;
}Tree Insert(Tree T, int V)
{if(!T)T = NewNode(V);else{if (V > T->v)T->Right = Insert(T->Right, V);elseT->Left = Insert(T->Left, V);}return T;
}Tree MakeTree(int N)
{Tree T;int i, V;scanf("%d",&V); //读入第一个数T = NewNode(V); //为这个数构造一个结点，T中只包含了一个结点for(i = 1; i < N; i++){scanf("%d", &V);T = Insert(T, V); //当前读入的数插入到结点中}return T;
}int check(Tree T, int V)
{if(T->flag){if(V < T->v)return check(T->Left, V);else if ( V > T->v)return check(T->Right, V);elsereturn 0; //序列中有重复出现的数，也作为不一致处理}else{if ( V == T->v){T->flag = 1;return 1;}elsereturn 0;}
}int Judge(Tree T, int N)
{int i, V, flag = 0; /*flag：0表示目前还一致，1表示已经不一致*/scanf("%d", &V);if (V != T->v) //判断树根是否相同flag = 1;elseT->flag = 1; //标记该结点已经访问过for(i = 1; i < N; i++){scanf("%d", &V);if((!flag) && (!check(T, V))) //如果flag = 1，即已经不一致了，就不用check了，直接继续读下一个flag = 1;}if(flag)return 0;elsereturn 1;
}void ResetT(Tree T) /*清除T中各结点的flag标记*/
{if(T->Left)ResetT(T->Left);if(T->Right)ResetT(T->Right);T->flag = 0;
}void FreeTree(Tree T) /*释放T的空间*/
{if (T->Left)FreeTree(T->Left);if(T->Right)FreeTree(T->Right);free(T);
}int main()
{int N,L,i;Tree T;scanf("%d", &N);while(N){scanf("%d", &L);T = MakeTree(N);for(i = 0; i < L;i++){if(Judge(T, N))printf("Yes\n");elseprintf("No\n");ResetT(T);}FreeTree(T); //一组数据处理完，要进入下一组数据前，要把当前的树Freescanf("%d", &N); //第二组输入}return 0;
}堆中的路径
//法1：通过插入建立最小堆
#include <iostream>
#define MAXN 1010
#define MINDATA -10001
using namespace std;int H_size=0;
int H_capacity=MAXN;
int* H;bool IsFull(){return (H_size==H_capacity);
}void InsertH(int x){if(IsFull()) return;H_size++;int i;for(i=H_size;H[i/2]>x;i=i/2){ H[i]=H[i/2];}
//保证退出来最小下标为1 H[i]=x;
}void CreateH(){
//建立哨兵H[0]=MINDATA;int tmp;for(int i=1;i<=H_capacity;i++){cin>>tmp;InsertH(tmp);}
}void PrintL(int index){int flag=0;for(int i=index;i>0;i=i/2){if(flag) printf(" %d",H[i]);else{printf("%d",H[i]);flag=1;}}
}int main(){int M;cin>>H_capacity>>M;H=new int[H_capacity+1];CreateH();int tmp;for(int i=0;i<M;i++){cin>>tmp;PrintL(tmp);cout<<endl;}return 0;
}哈夫曼编码
#include<bits/stdc++.h>
using namespace std;
int n;//节点个数
struct Weight {int weight = 0;char ch;
};
//Weight num[26];//储存初始数据的权重
struct hufnode {int quan;//节点权重int parent, left, right;int where;//作为左子树还是右子树int time;//出现次数char val;//储存的字符是谁
};
//hufnode tree[1000];//整个哈夫曼树void creattree(Weight num[],hufnode tree[])
{int m1, m2;int x1, x2;int j = 0, i = 0;for (i = 0; i < 2 * n - 1; i++)//初始化{tree[i].quan = 0;tree[i].parent = -1;tree[i].left = -1;tree[i].right = -1;tree[i].where = -1;}for (i = 0; i < 26; i++)//叶子节点数据导入{if (num[i].weight != 0){tree[j].quan = num[i].weight;tree[j].val = num[i].ch;tree[j].time = 0;j++;}}for (i = 0; i < n - 1; i++)//建树{m1 = m2 = 100000;x1 = x2 = -10;for (j = 0; j < n + i; j++){if (tree[j].quan < m1 && tree[j].parent == -1){m2 = m1;x2 = x1;m1 = tree[j].quan;x1 = j;}else if (tree[j].quan < m2 && tree[j].parent == -1){m2 = tree[j].quan;x2 = j;}}tree[x1].parent = n + i;tree[x2].parent = n + i;tree[n + i].quan = m1 + m2;tree[n + i].time = i;if (m1 == m2 && tree[x1].left == -1 && tree[x1].right == -1 && tree[x2].left == -1 && tree[x2].right == -1)//两个叶子节点分左右{if (tree[x1].val > tree[x2].val){tree[x1].where = 1;tree[x2].where = 0;tree[n + i].left = x2;tree[n + i].right = x1;}else{tree[x1].where = 0;tree[x2].where = 1;tree[n + i].left = x1;tree[n + i].right = x2;}}else if (m1 == m2){if (tree[x1].time > tree[x2].time){tree[x1].where = 1;tree[x2].where = 0;tree[n + i].left = x2;tree[n + i].right = x1;}else{tree[x1].where = 0;tree[x2].where = 1;tree[n + i].left = x1;tree[n + i].right = x2;}}else{tree[x1].where = 0;tree[x2].where = 1;tree[n + i].left = x1;tree[n + i].right = x2;}// cout<<tree[n + i].quan<<"+ "<<endl;//cout<<"zuo:"<<tree[tree[n+i].left].val<<endl;// cout<<"you:"<<tree[tree[n+i].right].val<<endl;}
}
void huffcode(char key,hufnode tree[])//编码
{int pos;hufnode temp;int a[100] = { 0 };int i = 0, j = 0;for (i = 0; i < 26; i++){if (tree[i].val == key || tree[i].val - key == 32 || key - tree[i].val == 32){pos = i;break;}}temp = tree[pos];while (1){if (temp.parent == -1)break;a[j++] = temp.where;temp = tree[temp.parent];}for (i = j - 1; i >= 0; i--)cout << a[i];
}
int main()
{char str[1001];while (scanf("%s", str)!= EOF){n=0;hufnode tree[1000];Weight num[26];for (int i = 0; i < strlen(str); i++){if (str[i] >= 'A' && str[i] <= 'Z'){num[str[i] - 65].weight++;num[str[i] - 65].ch = str[i];}if (str[i] >= 'a' && str[i] <= 'z'){num[str[i] - 97].weight++;num[str[i] - 97].ch = str[i];}}for (int i = 0; i < 26; i++){if (num[i].weight != 0){n++;if (num[i].ch >= 'A' && num[i].ch <= 'Z')//大写全部改小写num[i].ch += 32;}}creattree(num,tree);for (int i = 0; i < strlen(str); i++)huffcode(str[i],tree);cout << endl;}return 0;
}