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

2021-08-06 01:17:39 字數 3756 閱讀 9222

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.而哈夫曼樹是最優二叉數,二叉數的度數且每個結點必有二個度除根結點外。樓主把哈夫曼樹的定義認真讀一下就知道了。

非遞迴中序遍歷二叉樹 要求從鍵盤輸入二叉樹各結點的值,並使用二叉連結串列來儲存二叉樹使用非遞迴演算法遍

void mytree preprintf treenode lpcurnode,typefun lpfun lpcurnode lpcurnode m lpleft if stack.pop lpcurnode lpcurnode lpcurnode m lpright void mytree m...

已知二叉樹的先序遍歷和中序遍歷序列如下,構造相應的二叉樹

已知二叉樹的先序遍歷和中序遍歷序列如下,構造相應的二叉樹。1 2.3 4.5.6 7 根結點為1,則左為42,右5736,再看先根序列24 3576 左邊42在先根序列中以2為先,則1的下一層為2,再看中根序列42,所以4在2的右邊 右邊5736在先根序列中以3為先,則3的左邊是57,右邊是6 在先...

二叉樹先序序列和中序序列相同的條件是什麼

二叉樹先序來遍歷就是先訪問自己,然自後左子樹,然後右bai子樹。二叉樹的du中序遍歷zhi 是先訪問左子樹,然後訪問自dao己,最後右子樹。所以要讓上述兩個過程一樣,唯一的辦法就是左子樹不存在,也就是對於二叉樹上的任意節點,他的左子節點為空。每一層上的結點數都是最大結點數。而在一棵二叉樹中,除最後一...