1用遞迴實現二叉樹的先序 中序 後序三種遍歷。2哈夫曼樹問題

時間 2021-08-11 17:17:12

1樓:匿名使用者

//在嗎? 我給你。另外我有自己的實驗報告。

//裡面有遞迴遍歷,有迭代遍歷。可以寫檔案,可以壓縮編碼。可以讀檔案。

//你不需要什麼功能的話就刪去相應的函式就行了。

//希望加分。

#include

#include

#include

#include

using namespace std;

const int maxlen = 10000; //結點最大數目

const int maxlen2 = 260; //字元最大數目,葉節點最大數目

const int maxchar = 260; //字元最大數目

#define intmax 10000000; //大數,大於任意一個權值

struct charset //程式初始化時儲存字元和結點的結構體。

;struct haffnode //哈夫曼樹結點結構

};struct haffcode //哈夫曼樹字元編碼資訊結構

haffcode& operator=(haffcode & obj) //過載賦值符號

};class haffmansystem

void haffman(); //哈夫曼樹生成函式。

void initislization(); //初始化,呼叫haffman();

void encoding(); //對檔案"tobetran"進行編碼。

void decoding(); //對檔案"codefile"譯碼。

void print(); //印**至螢幕。

static void treeprinting(int pos,int i,int child_flag,haffmansystem * p,ofstream & fop);

void treeprinting(); //輸出哈夫曼樹圖形到螢幕和檔案,其中要呼叫靜態例項函式完成遞迴功能。

void treefromfile(); //從檔案中獲取哈夫曼樹。

};void haffmansystem::initislization()

cout<<"最後輸入空格的權值(小於等於0表示空格不存在): "<>cs[n].weight;

cs[n].ch=' ';

if(cs[n].weight>0) n++;

this->haffman(); //呼叫哈夫曼樹生成函式。

}//哈夫曼樹生成函式。

void haffmansystem::haffman()

else

if(m2>hn[j].weight && hn[j].parent==-1)

}hn[k1].parent = n+i; hn[k2].parent = n+i;

hn[n+i].weight = hn[k1].weight+hn[k2].weight;

hn[n+i].lchild = k1; hn[n+i].rchild = k2;

head = n+i;

}int child,parent;

for(i=0;i>choice;

if(choice=='y'||choice=='y') //把生成的哈弗曼樹儲存在檔案hfmtree.dat中。

//譯碼和編碼一樣,同樣飄逸的位運算處理,可以節省時間和空間。

flag=(1<>ch)

if(child_flag==-1)

else if(child_flag== 1)

if(p->hn[pos].ch=='\n')

}void haffmansystem::treefromfile()

case '2':

case '3':

case '4':

case '5':

default :break;}}

return 0;}

2樓:匿名使用者

民安國泰逢盛世 風調雨順頌華年 橫批:民泰國安

3樓:匿名使用者

一乾二淨除舊習 五講四美樹新風 橫批:辭舊迎春

1、建立二叉樹,並進行先序、中序和後序遍歷。 2、求二叉樹的深度及葉子結點的個數。 3、構造哈夫曼樹及哈

4樓:匿名使用者

0是初始節點數

輸入時請一次性輸完abcффdeфgффfффф在按enter鍵 不要輸入一個按一下

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#define max 20 //結點的最大個數

typedef struct nodebintnode; //自定義二叉樹的結點型別

typedef bintnode *bintree; //定義二叉樹的指標

int nodenum,leaf; //nodenum為結點數,leaf為葉子數

//**********基於先序遍歷演算法建立二叉樹**********====

//*****要求輸入先序序列,其中加入虛結點"#"以示空指標的位置**********

bintree creatbintree(void) }

//*****===nlr 先序遍歷**********===

void preorder(bintree t) }

//*****===lnr 中序遍歷***************

void inorder(bintree t) }

//**********lrn 後序遍歷**********==

void postorder(bintree t) }

//*****採用後序遍歷求二叉樹的深度、結點數及葉子數的遞迴演算法*****===

int treedepth(bintree t)

else return(0);

} //====利用"先進先出"(fifo)佇列,按層次遍歷二叉樹**********

void levelorder(bintree t)

if(p->rchild!=null)

} }//**********主函式***************==

void main()

printf("\n");

} while(i!=0);}

5樓:匿名使用者

這個資料結構課本上都有啊,你可以看看課本

為什麼 哈夫曼樹的度只能為0或者2 不能為1?

6樓:您輸入了違法字

因為哈夫曼樹的定義是構造一棵最短的帶權路徑樹,所以這種樹為最優二叉樹。最優二叉樹的度只有0或者2。

給定n個權值作為n個葉子結點,構造一棵二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也稱為哈夫曼樹(huffman tree)。哈夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近。

7樓:匿名使用者

對啊,樓主說的對。哈夫曼樹的度不能為0或2,絕對不可能為1的。這和度的定義及哈夫曼樹的定義有關。

結點的度是指該結點所具有的非空子樹數。一棵樹的度是指該樹中結點的最大度樹。例如:

a b c則a結點度為2.而哈夫曼樹是最優二叉數,二叉數的度數且每個結點必有二個度除根結點外。樓主把哈夫曼樹的定義認真讀一下就知道了。

某二叉樹的前序遍歷是abdgcefh,中序遍歷是dgbaechf,則起後序遍歷的結點訪問順序是什麼,為什麼

不太記得了,應該是 g d b a e h f c 二叉樹的3中遍歷,知道任何其中2種,就可以建立這個二叉樹。自然就可以得到第3中的遍歷了。具體方法可以翻書或網上查詢相關資料。 前序是 根左右 由此可判斷a為根節點,再看中序 由於a為根,所以在中序中根據 左根右 原則a前的即為a的左子樹 dgb 右...

已知二叉樹後序遍歷序列是dabec,中序遍歷序列是debac

第六位面壁者 選d首先看後續遍歷,最後的c是二叉樹的根節點,然後看中序遍歷,最後一個又是c,所以這個二叉樹根節點沒有右子樹。c的位置得到後,再看後續遍歷,e在c前面,所以e是c的左孩子節點,e的位置得到。然後再看中序遍歷,e前面只有一個d,所以d是e的左孩子節點,d的位置得到 剩下的b和a就在e的右...

某二叉樹的前序序列與中序序列正好相反,則該二叉樹具有

如果是多選的話b應該也可以選,但如果單選則不能選b。b中描述的二叉樹包括c和d,更準確的說應該是每個節點都只有一個孩子的二叉樹,其中只有c中描述的二叉樹才滿足題目要求的中序和後續相反。簡單分析如下 對任意一個節點a,其左右孩子分別為bc 可能為空 則其中續為bac,後續為bca,要bca與bac相反...