二叉樹(哈夫曼)

特點:結(jié)合有序組和鏈表的優(yōu)點

查找

public Node find(int key) {
        Node current = root;
        while(current.iData != key) {
            if(key<current.iData)
                current = current.leftChild;
            else
                current = current.rightChild;
            if(current == null) {
                return null;
            }
        }
        return current;
    }

插入:順著查找的思路搜变,在返回前插入

public void insert(int id, double dd) {
        Node newNode = new Node();
        newNode.iData = id;
        newNode.dData = dd;
        if(root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while(true) {
                parent = current;
                if(id < current.iData) {
                    current = current.leftChild;
                    if(current == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                }else {
                    current = current.rightChild;
                    if(current == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

遍歷樹
中序遍歷:
1.調(diào)用自身來遍歷節(jié)點的左子樹
2.訪問自己節(jié)點
3....右子樹

private void inOrder(node localRoot) {
  if(localRoot != null) {
      inOrder(localRoot.leftChild);
      System.out.println(localRoot.iData + "");
      inOrder(localRoot.rightChild);
    }
}  

前序:
1.訪問自己節(jié)點
2.自身左子樹
3.自身右子樹
后序:自己想

最小值和最大值:最下最左左子樹,最下最右右子樹

刪除節(jié)點
三種情況:
1.該節(jié)點是葉節(jié)點(沒有子節(jié)點)
2.該節(jié)點有一個子節(jié)點
3.該節(jié)點有兩個子節(jié)點

public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;
        
        //和查找一樣
        while(current.iData != key) {
            parent = current;
            if(key<current.iData) {
                isLeftChild = true;
                current = current.leftChild;
            }
            else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if(current == null) {
                return null;
            }
        }
        
        //找到之后
        //第一種情況
        if(current.leftChild == null && current.rightChild == null) {
            if(current == root)
                root = null;
            else if(isLeftChild)
                parent.leftChild = null;
            else
                parent.rightChild = null;
        }
        //第二種情況:沒有左節(jié)點或沒有右節(jié)點嗽交,都要考慮被刪除節(jié)點可能是根
        else if(current.rightChild == null) {
            if(current == root)
                root = current.leftChild;
            else if(isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.rightChild;
        }
        else if(current.leftChild == null) {
            if(current == root)
                root = current.rightChild;
            else if(isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.rightChild;
        }
        
        
        //第三種情況:雙節(jié)點又分兩種情況,第一種后繼節(jié)點是delNode的右節(jié)點參考圖8.19路狮,第二種后繼節(jié)點是delNode右子節(jié)點的左后代參考圖8.20
        Node successor = getSuccessor(current);
        
        if(current == root) 
            root = successor;
        else if(isLeftChild)
            parent.leftChild = successor;
        else
            parent.rightChild = current.leftChild;
    }
    return true;
}

//查找后繼節(jié)點周蹭,參照圖8.17和8.18是兩種情況
private node getSuccessor(node delNode) {
    Node SuccessorParent = delNode;
    Node successor = delNode;
    Node current = delNode.rightChild;
        //參照圖8.17绰筛,38是需要刪除的節(jié)點
    while(current != null) {
        SuccessorParent = successor;
        successor = current;
        current = current.leftChild;
    }
    
    //參照圖8.18,假如不等于逐工,這兩句代碼是實現(xiàn)第二種情況的樹旋轉(zhuǎn)
    if(successor != delNode.rightChild){
        SuccessorParent.leftChild = successor.rightChild;
        successor.rightChild = delNode.rightChild;
    }
    return successor;
}
Paste_Image.png
Paste_Image.png
Paste_Image.png

哈夫曼
專用于壓縮文本

Paste_Image.png
Paste_Image.png
Paste_Image.png

重點解釋:用10表示S,用00表示空格后铡溪,不能再用01和11,因為它們是其它字符的前綴泪喊,不夠就用三位來組合:000棕硫,001,010袒啼,011哈扮,100,110蚓再,111. A是010滑肉,I是110,因為除去10和00開始的組合摘仅,在用四位表示其它字符靶庙,依此類推

Paste_Image.png
Paste_Image.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市娃属,隨后出現(xiàn)的幾起案子六荒,更是在濱河造成了極大的恐慌,老刑警劉巖膳犹,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件恬吕,死亡現(xiàn)場離奇詭異,居然都是意外死亡须床,警方通過查閱死者的電腦和手機铐料,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來豺旬,“玉大人钠惩,你說我怎么就攤上這事∽逶模” “怎么了篓跛?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長坦刀。 經(jīng)常有香客問我愧沟,道長蔬咬,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任沐寺,我火速辦了婚禮林艘,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘混坞。我一直安慰自己狐援,他們只是感情好,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布究孕。 她就那樣靜靜地躺著啥酱,像睡著了一般。 火紅的嫁衣襯著肌膚如雪厨诸。 梳的紋絲不亂的頭發(fā)上镶殷,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天,我揣著相機與錄音泳猬,去河邊找鬼批钠。 笑死宇植,一個胖子當著我的面吹牛得封,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播指郁,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼忙上,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了闲坎?” 一聲冷哼從身側(cè)響起疫粥,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎腰懂,沒想到半個月后梗逮,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡绣溜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年慷彤,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片怖喻。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡底哗,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出锚沸,到底是詐尸還是另有隱情跋选,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布哗蜈,位于F島的核電站前标,受9級特大地震影響坠韩,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜炼列,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一同眯、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧唯鸭,春花似錦须蜗、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至缭付,卻和暖如春柿估,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背陷猫。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工秫舌, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人绣檬。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓足陨,卻偏偏與公主長得像,于是被迫代替她去往敵國和親娇未。 傳聞我的和親對象是個殘疾皇子墨缘,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容