I use a data structrue to description a tree.
struct Node{
char *name;
int value;
//标志位，1说明该节点在数组中无效了，0则有效
int isNull;
struct Node *leftNode;
struct Node *rightNode;
struct Node *parentNode;
int isLastNode;
}.
I want to reckon a Haffman code.
this is my code:
include
include
include
struct Node{
char *name;
int value;
//标志位，1说明该节点在数组中无效了，0则有效
int isNull;
struct Node *leftNode;
struct Node *rightNode;
struct Node *parentNode;
int isLastNode;
} nodes[5],sigleNode;
//声明定义的初始化节点的方法
void initNodes();
//声明获取节点数组的长度的方法
int getNodesSize();
//声明获得哈夫曼树节点的方法
Node getHaffTree();
//声明获取值最小的节点的方法
Node getMinValueNode();
//声明获取非空节点数量的方法
int getNotNullNodesSize();
//声明判断是否是空节点的方法
int isNullNode(Node n);
//声明获取第几个有效节点的方法,i从0开始
Node getValidNode(int i);
//声明将节点插入到数组节点中无效节点的方法
void addNodetoList(Node n);
//声明检索树的方法
void viewTree(Node *n);
//主方法
int main(){
//初始化节点
initNodes();
Node mainNode = getHaffTree();
//printf("根节点值 %d \n",mainNode.value);
viewTree(&mainNode);
return 0;
}
//检索树结构
void viewTree(Node *mainNode){
Node *leftNodeP = mainNode->leftNode;
if( leftNodeP->isLastNode == 1){
//计算哈夫曼码.to do
printf("权值为[%d]的节点[%s]哈夫曼码是: \n",leftNodeP->value,leftNodeP->name);
}else{
viewTree(leftNodeP->leftNode);
}
Node *rightNodeP = mainNode->rightNode;
if( rightNodeP->isLastNode == 1){
//计算哈夫曼码.to do
printf("权值为[%d]的节点[%s]哈夫曼码是: \n",rightNodeP->value,rightNodeP->name);
}else{
viewTree(rightNodeP->rightNode);
}
/*
if(NULL != mainNode.rightNode){
Node rightNode = *mainNode.rightNode;
Node rlNode = *rightNode.leftNode;
Node rrNode = *rightNode.rightNode;
char *rlName = rlNode.name;
char *rrName = rrNode.name;
if(strcmp(empName,rlName) ==0 && strcmp(empName,rrName) == 0){
printf("权值为[%d]的节点[%s]哈夫曼码是: \n",rightNode.value,rightNode.name);
}else{
viewTree(rightNode);
}
}
*/
//viewTree(leftNode);
/*
if(!leftNode==NULL){
if(leftNode.leftNode == NULL && leftNode.rightNode == NULL){
//String haffCode = getHaffCode(leftNode,"");
printf("权值为[%d]的节点[%s]哈夫曼码是: \n",leftNode.value,leftNode.name);
}else{
viewTree(leftNode);
}
}*/
//Node rightNode = *mainNode.rightNode;
//printf("右 value %d \n",rightNode.value);
//viewTree(rightNode);
/*
if(!rightNode==NULL){
if(leftNode.leftNode == NULL && leftNode.rightNode == NULL){
//String haffCode = getHaffCode(rightNode,"");
printf("权值为[%d]的节点[%s]哈夫曼码是:\n",rightNode.value,rightNode.name);
}else{
viewTree(rightNode);
}
}
*/
}
//递归方法组件树形数据结构
Node getHaffTree(){
int size = getNotNullNodesSize();
printf("length = %d \n",size);
if(size > 2){
printf("before size %d \n",getNotNullNodesSize());
Node minNode1 = getMinValueNode();
Node minNode2 = getMinValueNode();
printf("value1 %d \n",minNode1.value);
printf("value2 %d \n",minNode2.value);
printf("after size %d \n",getNotNullNodesSize());
//声明2个节点生产的父节点对象
Node mainNode;
//将子节点的值相加赋给父节点
mainNode.value = minNode1.value+minNode2.value;
mainNode.isNull = 0;
mainNode.isLastNode = 0;
//将小值节点地址赋给左节点的指针变量
mainNode.leftNode = &minNode1;
mainNode.rightNode = &minNode2;
minNode1.parentNode = &mainNode;
minNode2.parentNode = &mainNode;
//将父节点插入到数组中的无效节点位置
addNodetoList(mainNode);
return getHaffTree();
}else if(size = 2){
Node minNode1 = getMinValueNode();
Node minNode2 = getMinValueNode();
//声明2个节点生产的父节点对象
Node mainNode;
//将子节点的值相加赋给父节点
mainNode.value = minNode1.value+minNode2.value;
mainNode.isNull = 0;
mainNode.isLastNode = 0;
//将小值节点地址赋给左节点的指针变量
mainNode.leftNode = &minNode1;
mainNode.rightNode = &minNode2;
minNode1.parentNode = &mainNode;
minNode2.parentNode = &mainNode;
return mainNode;
}
Node n;
return n;
}
//定义声明的初始化节点方法
void initNodes(){
nodes[0].name="A";
nodes[0].value=5;
nodes[0].isNull=0;
nodes[0].isLastNode = 1;
nodes[1].name="B";
nodes[1].value=4;
nodes[1].isNull=0;
nodes[1].isLastNode = 1;
nodes[2].name="C";
nodes[2].value=3;
nodes[2].isNull=0;
nodes[2].isLastNode = 1;
nodes[3].name="D";
nodes[3].value=2;
nodes[3].isNull=0;
nodes[3].isLastNode = 1;
nodes[4].name="E";
nodes[4].value=1;
nodes[4].isNull=0;
nodes[4].isLastNode = 1;
}
//定义计算节点数量的方法
int getNodesSize(){
return sizeof(nodes)/sizeof(sigleNode);
}
int getNotNullNodesSize(){
int size = getNodesSize();
int reallSize=0;
for(int i = 0;i<size;i++){
if(isNullNode(nodes[i]) ==0){
reallSize++;
}
}
return reallSize;
}
//判断是否是空节点
int isNullNode(Node n){
if(n.isNull == 1){
return 1;
}else{
return 0;
}
}
//定义获取值最小的节点方法
Node getMinValueNode(){
int size = getNodesSize();
Node minNode = getValidNode(0);
int index = 0;
for(int i=0;i<size;i++){
Node n = nodes[i];
//空值节点不判断
if(isNullNode(n)==0 && n.value <= minNode.value){
minNode = n;
index = i;
}
}
Node empNode;
empNode.isNull = 1;
nodes[index] = empNode;
return minNode;
}
//定义获取第几个有效节点的方法
Node getValidNode(int index){
int size = getNodesSize();
int continueNum = index;
Node rs;
for(int i=0;i<size;i++){
Node n = nodes[i];
//空值节点不判断
if(isNullNode(n)==0 && continueNum ==0){
rs = n;
break;
}
if(isNullNode(n) == 0){
continueNum--;
}
}
return rs;
}
//定义将节点插入到数组节点中无效节点的方法
void addNodetoList(Node insertN){
int size = getNodesSize();
for(int i=0;i<size;i++){
Node n = nodes[i];
//如果是空白节点则，更新该位置为要插入的节点
if(isNullNode(n)==1){
nodes[i] = insertN;
break;
}
}
}
I debug for the main method, before into the viewTree(Node *N) method,the mainNode like pic1:
but when I debug into the viewTree(Node *n) method.
thie mainNode like pic2?!
who can help me to explain such problem?
Thanks !
