创建二叉树,输入先序扩展序列:ABD##E##C#F##
中序遍历输出节点:D B E A C F
后序遍历输出节点:D E B F C A
二叉树示意图:
A
/ \
B C
/ \ / \
D E # F
/ \ / \ / \
# # # # # #
测试数据2:
创建二叉树,输入先序扩展序列:ABC##DE#G##F###
先序遍历输出节点:A B C D E G F
中序遍历输出节点:C B E G D F A
后序遍历输出节点:C G E F D B A
二叉树示意图:
A
/ \
B #
/ \
C D
/ \ / \
# # E F
/ \ / \
# G # #
/ \
# #
#include<stdio.h>
#include<stdlib.h>
typedef struct Node //二叉树的结构体
{
char data //字符
struct Node *lchild //左分支
struct Node *rchild //右分支
}Bitree
//创建二叉树: 用"先序遍历"(递归法)
void CreateBiTree(Bitree **bt)
{
char ch
scanf("%c",&ch) //输入字符
if(ch=='#') //'#'是空节点NULL
*bt=NULL
else
{
*bt=(Bitree *)malloc(sizeof(Bitree))
(*bt)->data=ch
CreateBiTree(&((*bt)->lchild))
CreateBiTree(&((*bt)->rchild))
}
}
//用"先序遍历"输出节点(递归法)
void preOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
printf("%c ",ptr->data)
preOrder(ptr->lchild)
preOrder(ptr->rchild)
}
}
//用"中序遍历"输出节点(递归法)
void inOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
inOrder(ptr->lchild)
printf("%c ",ptr->data)
inOrder(ptr->rchild)
}
}
//用"后序遍历"输出节点(递归法)
void postOrder(Bitree *ptr)
{
if(ptr!=NULL)
{
postOrder(ptr->lchild)
postOrder(ptr->rchild)
printf("%c ",ptr->data)
}
}
int main()
{
Bitree *root
printf("创建二叉树,输入先序扩展序列:")
CreateBiTree(&root)
printf("先序遍历输出节点: ")
preOrder(root)
printf("\n中序遍历输出节点: ")
inOrder(root)
printf("\n后序遍历输出节点: ")
postOrder(root)
printf("\n")
return 0
}
#include<iostream>#include<iomanip>
#include<string>
#include <windows.h>
using namespace std
typedef struct {//定义哈夫曼树个结点
int weight//权值
int parent,lchild,rchild//双亲，左右孩子结点下标
char data//储存相关的字符信息
}HTNode,*HuffmanTree//动态分配数组存储哈夫曼编码树
typedef char **HuffmanCode// 动态分配数组存储哈夫曼编码表
void statistics(char *a,int *w,char *d,int &n)//统计字符
{
int j=0
int k
for(int i=0i<100&&a[i]!='\0'i++){
for( k=0k<jk++){
if(a[i]==d[k])
{ w[k]++
break
}
}
if(k==j){
d[j]=a[i]
w[j]++
j++}
}
n=j
d[j]='\0'
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *d)//w存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
{if(n<=1)return
int m=2*n-1//m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以储存一个大小为2n-1的一维数组中
HT=new HTNode[m+1]
HuffmanTree p
int i
for(p=HT+1,i=1i<=ni++,++p) //初始化哈夫曼树
{ p->data=d[i-1]
p->lchild=p->parent=p->rchild=0
p->weight=w[i-1] }
for(i<=m++i,++p) {
p->lchild=p->parent=p->rchild=0
p->weight=0 }
for(i=n+1i<=m++i){//建立哈夫曼树
int s1,s2,u,t
for (u=1u<=i-1u++)if(HT[u].parent==0){s1=ubreak}
for(u=u+1u<=i-1u++) {
if(HT[s1].weight>HT[u].weight&&HT[u].parent==0)
s1=u }
for(t=1t<=i-1t++)
if(HT[t].parent==0&&t!=s1){s2=tbreak}
for(t=t+1t<=i-1t++)
{ if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1)
s2=t }
HT[s1].parent=iHT[s2].parent=i//parent为0且weight最小的的两个结点，一个为s1,一个为s2
HT[i].lchild=s1HT[i].rchild=s2//左孩子权值小，右孩子权值大
HT[i].weight=HT[s1].weight+HT[s2].weight }
HC=new char*[n+1] //分配n个字符编码指针
char *cd=new char[n]//分配编码的工作空间
cd[n-1]='\0'//编码结束符
int start,c,f
for(i=1i<=n++i){//逐个字符求哈夫曼编码
start=n-1 //编码在数组cd[]的最前位置
for(c=i,f=HT[i].parentf!=0c=f,f=HT[f].parent)//从叶子到树根逆向求哈夫曼编码
if(HT[f].lchild==c) cd[--start]='0'//判断是左孩子还是右孩子（左为0右为1）
else cd[--start]='1'
HC[i]=new char[n-start]//为第i个字符分配空间
strcpy(HC[i],&cd[start]) }//讲cd[]数组的start位置到n-1位置复制给HC[i]
delete(cd)}//释放空间
void main()
{
char a[100]
char d[100]char bc[1000]
int w[100],n=0
HuffmanTree HT
HuffmanCode HC
cout<<"请输入字符：\n"
cin>>a
for(int ak=0ak<100ak++)w[ak]=0
statistics (a,w,d,n) //统计
HuffmanCoding(HT,HC,w,n,d)
cout<<"霍夫曼编码为："<<endl
cout<<"原码 "<<"权值 "<<"二进制码"<<endl
system("pause")
}
请采纳，谢谢
#include<stdio.h>#include<stdlib.h>
typedef struct
{
int arr[100]
int last
}SeqList
void InitList(SeqList *L)
void IsEmpty(SeqList L)
int GetLength(SeqList L)
void DeletNum(SeqList * L,int num)
void GetEmpty(SeqList * L)
void PaiXu(SeqList * L)
int main()
{
int length,addr,num
SeqList L,*p
p=&L
printf("创建表\n")
InitList(&L)//初始化
IsEmpty(L)//判断是否为空
printf("input the length\n")
scanf("%d",&length)
L.last=length-1//数组最后下个数的下标
printf("输入表中的值\n")//输入表中的值
for(int i=0i<=L.lasti++)
scanf("%d",&L.arr[i])
length=GetLength(L)
printf("输入想输出的数在表中的位置(从1开始数)\n")//输出某个位序上的数据元素
scanf("%d",&addr)
if(addr>length)
printf("该位置不存在，超过了范围\n")
else
printf("第%d数为%d\n",addr,L.arr[addr-1])
printf("输入想得到前驱后继的结点的值\n")//输出某元素的前驱后继
scanf("%d",&num)
for(i=0i<=L.lasti++)
{
if(L.arr[i]==num)
{
printf("找到该结点，结点的位置为第%d数\n",i+1)
if((i+1)==length)
printf("该结点无后继\n")
else
printf("结点后继为%d\n",L.arr[i+1])
if((i-1)<0)
printf("该结点无前驱\n")
else
printf("结点前驱为%d\n",L.arr[i-1])
break
}
}
if(i==length)
printf("表中无此数\n")
//将奇偶排序
PaiXu(&L)
printf("输入想要删除的数\n")
scanf("%d",&num)
DeletNum(p,num)//删除该数
GetLength(L)//删除后的表长
GetEmpty(&L)//置空
IsEmpty(L)//判断是否为空
return 0
}
void InitList(SeqList * L)
{
L->last=-1
}
void IsEmpty(SeqList L)
{
if(L.last>=0)
printf("该表不为空\n")
else
printf("该表为空\n")
}
int GetLength(SeqList L)
{
printf("该表的长度为%d\n",L.last+1)
return L.last+1
}
void DeletNum(SeqList * L,int num)
{
int i,k
for(i=0i<=L->lasti++)
{
if(L->arr[i]==num)
{
k=i
break
}
}
if(i==L->last+1)
printf("表中无此数\n")
for(i=ki<L->lasti++)//删除该数后，后面的数向前移
L->arr[i]=L->arr[i+1]
L->last--//表长减一
for(i=0i<=L->lasti++)
printf("%d ",L->arr[i])
}
void GetEmpty(SeqList * L)
{
L->last=-1
}
void PaiXu(SeqList * L)
{
int i,j,t
i=0
j=L->last
while(i<j)
{
while(L->arr[i]%2!=0)
i++
while(L->arr[j]%2==0)
j--
if(i<j)
{
t=L->arr[i]
L->arr[i]=L->arr[j]
L->arr[j]=t
}
}
printf("奇偶排序后\n")
for(i=0i<=L->lasti++)
printf("%d ",L->arr[i])
}
