1.有人可以帮我注释一段关于用c语言实现哈夫曼树的叉树叉树代码吗？
2.用C语言定义二叉树的二叉链表存储结构，完成二叉树的源码源代建立，先序中序后序遍历的叉树叉树操作，求所有叶子结点总数
3.哪位大侠能帮我解决"用c/c++编写二叉树先序遍历非递归算法"啊?源码源代急急急!!!谢谢啦!!
有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗？
在一般的数据结构的书中，树的叉树叉树那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。源码源代小程序实战项目源码哈夫曼编码是叉树叉树哈夫曼树的一个应用。哈夫曼编码应用广泛，源码源代如JPEG中就应用了哈夫曼编码。叉树叉树 首先介绍什么是源码源代哈夫曼树。哈夫曼树又称最优二叉树，叉树叉树是源码源代一种带权路径长度最短的二叉树。所谓树的叉树叉树带权路径长度，就是源码源代树中所有的叶结点
的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的叉树叉树路径长度为叶结点的层数）。
树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，N个权值Wi(i=1,星河源码分享2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明哈夫曼树的WPL是最小的。
哈夫曼编码步骤：
一、对给定的n个权值{ W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= { T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的excel转源码 table权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，印钞机主图源码直到集合F中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
请点击输入描述
虚线为新生成的java养宠物源码结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{ 5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：
请点击输入描述
再依次建立哈夫曼树，如下图：
请点击输入描述
其中各个权值替换对应的字符即为下图：
请点击输入描述
所以各字符对应的编码为：A->,B->,C->,D->,E->
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
C语言代码实现：
/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* Date: ..
* Author: Jeffrey Hill+Jezze(解码部分)
* 在 Win-TC 下测试通过
* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
* 父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT
#define MAXVALUE
#define MAXLEAF
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 结点结构体 */
/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //实际值，可根据情况替换为字母
} /* end for */
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d: \n", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */
/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
printf ("\n");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
} /* end HuffmanTree */
//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[];
int m=2*Num-1;
char *nump;
char num[];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{ tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[];
printf ("Please input n:\n");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
for (i=0; i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while (p != -1) /* 父结点存在 */
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求编码的低一位 */
c=p;
p=HuffNode[c].parent; /* 设置下一循环条件 */
} /* end while */
/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);
printf ("\n");
}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf("\n");
}*/
printf("Decoding?Please Enter code:\n");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}
用C语言定义二叉树的二叉链表存储结构，完成二叉树的建立，先序中序后序遍历的操作，求所有叶子结点总数
#include<stdio.h>#include<malloc.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *lchild,*rchild;
}LNode,*TLNode;
void create(TLNode * Tree){ //创建
ElemType e;
scanf("%d",&e);
if(e==0)
*Tree=NULL;
else{
(*Tree)=(TLNode)malloc(sizeof(LNode));
(*Tree)->data=e;
printf("input %d lchild: ",e);
create(&(*Tree)->lchild);
printf("input %d rchild: ",e);
create(&(*Tree)->rchild);
}
}
void print1(TLNode Tree){ //先序遍历
if(Tree!=NULL){
printf("%d-",Tree->data);
print1(Tree->lchild);
print1(Tree->rchild);
}
}
void print2(TLNode Tree){ //中序遍历
if(Tree!=NULL){
print2(Tree->lchild);
printf("%d-",Tree->data);
print2(Tree->rchild);
}
}
void print3(TLNode Tree){ //后序遍历
if(Tree!=NULL){
print3(Tree->lchild);
print3(Tree->rchild);
printf("%d-",Tree->data);
}
}
int leaf=0; //求叶子节点数
int depth(TLNode Tree){ //深度
int s1,s2;
if(Tree==NULL)
return 0;
else{
s1=depth(Tree->lchild);
s2=depth(Tree->rchild);
if(s1==0 && s2==0) leaf++;
return (s1>s2?s1:s2)+1;
}
}
int Cnode(TLNode Tree){ //总结点
int s1,s2;
if(Tree==NULL)
return 0;
else{
s1=Cnode(Tree->lchild);
s2=Cnode(Tree->rchild);
return s1+s2+1;
}
}
void main(){
TLNode Tree;
printf("input 根节点: ");
create(&Tree);
printf("先序遍历:");
print1(Tree);
printf("中序遍历");
print2(Tree);
printf("后序遍历");
print3(Tree);
printf("\n深 度:%d \n",depth(Tree));
printf("总结点数:%d \n",Cnode(Tree));
printf("叶子结点数:%d\n",leaf);
}
哪位大侠能帮我解决"用c/c++编写二叉树先序遍历非递归算法"啊?急急急!!!谢谢啦!!
[源程序]
#include <iostream.h>
#include <conio.h>
typedef int ElemType;
struct NodeType //定义结点 结构体
{ ElemType data;
NodeType *lch，*rch;
};
class BiTree //定义 二叉树类 class
{ public:
BiTree(){ root=NULL;}; //构造函数
~BiTree(){ destroy(root) ;} //析构函数
void inorder() //中序遍历
{ inorder(root); }
void preordertswap() //利用先序遍历方法交换左右子树
{ preorderswap(root); }
int theight() //求二叉树高度
{ return height(root); }
void creat0();
private:
NodeType *root; //数据成员，树根
NodeType *creat(); //建立二叉树递归方法
void inorder(NodeType *p); //中序遍历
void preorderswap(NodeType *p); //利用先序遍历方法交换左右子树
int height(NodeType *p); //求二叉树高度递归算法
void destroy(NodeType* &p); //删除二叉树所有结点
};
void BiTree::creat0() //建立树函数，
{ cout<<"请按照树的先序遍历顺序组织数据"<<endl;
cout<<"若结点信息是int，把每个结点的空孩子以0输入;"<<endl;
cout<<"一个结点的二叉树，输入： 0 0;"<<endl;
root=creat(); //调用私有creat();
}
NodeType * BiTree::creat() //递归建立二叉树算法
{ NodeType *p; ElemType x;
cout<<"\n 输入数据："; cin>>x;
if( x==0) p=NULL;
else { p=new NodeType; p->data=x;
p->lch=creat(); //递归调用自身
p->rch=creat();
}
return p;
}
void BiTree::inorder(NodeType *p) //中序遍历
{ if(p != NULL)
{ inorder(p->lch);
cout<<p->data<<" ";
inorder(p->rch);
}
}
void BiTree::preorderswap(NodeType *p) //利用先序遍历方法交换左右子树
{ if(p != NULL)
{ NodeType *r; r=p->lch;
p->lch=p->rch; p->rch=r;
//上面几条语句可以认为对结点的访问（交换左右孩子）
//替换了原来的： cout<<p->data<<" "; 语句
preorderswap(p->lch);
preorderswap(p->rch);
}
}
void BiTree::destroy(NodeType* &p) //删除二叉树所有结点
{ if(p != NULL)
{ destroy(p->lch);
destroy(p->rch);
delete p;
p = NULL;
}
}
int BiTree::height(NodeType *p) //求二叉树高度递归
{ if(p == NULL) return 0;
else{ int hl=height(p->lch);
int hr=height(p->rch);
return 1 + (hl>hr?hl:hr); //1加上hl和hr的较大值
}
}
//---------------------------------------------------------------------------
int main()
{ int k; BiTree root0; //声明创建二叉树对象，调用构造函数
do{ cout<<"\n\n";
cout<<"\n\n 1. 建立二叉树";
cout<<"\n\n 2. 交换左右子树 ";
cout<<"\n\n 3. 求二叉树深度 ";
cout<<"\n\n 4. 结束程序运行";
cout<<"\n======================================";
cout<<"\n 请输入您的选择 (0,1,2,3,4):"; cin>>k;
switch(k)
{ case 1:{ cout<<"\n s输入（0 0）结束：";
root0.creat0();
cout<<"\n 中先根遍历结果："; root0.inorder();
} break;
case 2:{ cout<<"\n 交换左右子树结果：";
root0.preordertswap();
cout<<"\n 中先根遍历结果：";
root0.inorder();
} break;
case 3:{ int deep;//=root0.theight();
deep=root0.theight();
cout<<"\n 树的深度是："<<deep;
} break;
case 4: exit(0);
} // switch
cout<<"\n ----------------";
} while(k>=0 && k<4);
_getch(); return 0;
}//-------------------------------------------------------
2024-11-06 12:56
2024-11-06 12:47
2024-11-06 12:33
2024-11-06 12:29
2024-11-06 11:42
2024-11-06 11:36
