【bluez 源码】【centos换yum源码】【纯文字源码】二叉树源码_二叉树源代码
1.有人可以帮我注释一段关于用c语言实现哈夫曼树的叉树叉树代码吗？
2.用C语言定义二叉树的二叉链表存储结构，完成二叉树的源码源代建立，先序中序后序遍历的叉树叉树操作，求所有叶子结点总数
3.哪位大侠能帮我解决"用c/c++编写二叉树先序遍历非递归算法"啊?源码源代急急急!!!谢谢啦!!
有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗？
在一般的数据结构的书中，树的叉树叉树那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。源码源代bluez 源码哈夫曼编码是叉树叉树哈夫曼树的一个应用。哈夫曼编码应用广泛，源码源代如JPEG中就应用了哈夫曼编码。叉树叉树 首先介绍什么是源码源代哈夫曼树。哈夫曼树又称最优二叉树，叉树叉树是源码源代一种带权路径长度最短的二叉树。所谓树的叉树叉树带权路径长度，就是源码源代树中所有的叶结点
的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的叉树叉树路径长度为叶结点的层数）。
树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，N个权值Wi(i=1,centos换yum源码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的纯文字源码权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，uboot源码编译实验直到集合F中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
请点击输入描述
虚线为新生成的中国暗棋源码结点，第二步再把新生成的权值为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;
}//-------------------------------------------------------