Tree

Tree

1.二叉樹的性質(zhì)

二叉樹第i層(i>=1)上最多有2^(k-1)個(gè)元素凡怎。

高度為k的兒茶素最多有2^k-1 個(gè)元素

2.二叉樹的存儲(chǔ)

分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)

ps: 從1開始算的是 這里面备埃。

二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)

3.二叉樹的遍歷

重點(diǎn)掌握昼榛。

  • 前序遍歷(前中后是對(duì)根結(jié)點(diǎn)來(lái)說(shuō)的)
  • 中序遍歷
  • 后序遍歷
  • 廣度遍歷(層次遍歷刘莹,隊(duì)列)
  • s形遍歷(第一列從左到右罢艾,第二列從右到左)

前中后遍歷

根據(jù)根結(jié)點(diǎn)的位置來(lái)說(shuō)的抚恒。

層次遍歷

在進(jìn)行層次遍歷的時(shí)候拄衰,對(duì)一層節(jié)點(diǎn)訪問(wèn)完后,在按照他們的訪問(wèn)次序?qū)Ω鱾€(gè)節(jié)點(diǎn)的左右孩子做順序便利鬼癣。就完成了對(duì)下一層從左到右的訪問(wèn)陶贼。在進(jìn)行層次遍歷時(shí)啤贩,需設(shè)置一個(gè)隊(duì)列。首先將根指針入隊(duì)拜秧,然后從隊(duì)列里面彈出來(lái)一個(gè)元素痹屹,每取出一個(gè)元素,執(zhí)行兩個(gè)操作枉氮,訪問(wèn)改元素所值得節(jié)點(diǎn)志衍。如果左右節(jié)點(diǎn)不為空,加入隊(duì)列聊替。此過(guò)程循環(huán)執(zhí)行楼肪,直到隊(duì)列為空。表示層次遍歷結(jié)束惹悄。

s遍歷

層次遍歷春叫。第一層從左到右,第二層從右到左俘侠,可以通過(guò)兩個(gè)queue實(shí)現(xiàn)象缀。

package tree;

import java.util.LinkedList;
import java.util.Queue;

public class Treesearch {
    static class Node{
        String value;
        Node leftNode;
        Node rightNode;
        public Node(String value,Node left,Node right){
            this.value=value;
            this.leftNode=left;
            this.rightNode=right;
        }
    }
    
    void doSth(Node root){
        System.out.print(root.value+" ");
    }
    
    void preOrder(Node root){
        if(root==null) return ;
        doSth(root);
        preOrder(root.leftNode);
        preOrder(root.rightNode);       
    }
    
    void inOrder(Node root){
        if(root==null) return ;
        inOrder(root.leftNode);
        doSth(root);        
        inOrder(root.rightNode);
    }
    
    void postOrder(Node root){
        if(root==null) return ;
        postOrder(root.leftNode);       
        postOrder(root.rightNode);
        doSth(root);
    }
    
    void breadthOrder(Node root){
        Queue<Node> queue= new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node node=queue.poll();
            doSth(node);
            if(node.leftNode!=null)
                queue.add(node.leftNode);
            if(node.rightNode!=null)
                queue.add(node.rightNode);          
        }
    }
    
    void pt(LinkedList<Node> queue,int t){
        if(t%2==0){
            for(int i=0;i<queue.size();i++){
                System.out.print(queue.get(i).value+" ");
            }
        }else{
            for(int i=queue.size()-1;i>=0;i--){
                System.out.print(queue.get(i).value+" ");
            }
        }
    }
    
    void s_order(Node root){
        LinkedList<Node> queue1= new LinkedList<>();
        LinkedList<Node> queue2= new LinkedList<>();
        queue1.add(root);
        int i=0;
        while(queue1.size()!=0){
            pt(queue1, i);
            i++;
            while(!queue1.isEmpty()){
                Node node=queue1.poll();
                //doSth(node);//如果s打印。那么控制一下參數(shù)就好爷速。
                if(node.leftNode!=null)
                    queue2.add(node.leftNode);
                if(node.rightNode!=null)
                    queue2.add(node.rightNode);
            }
            LinkedList<Node> tmp=queue1;
            queue1=queue2;      
            queue2=tmp;
        }
    }
    
    Node create(){
        Node d=new Node("d", null, null);
        Node e=new Node("e", null, null);
        Node g=new Node("g", null, null);
        Node b=new Node("b", d, e);
        Node c=new Node("c", null, g);
        Node a=new Node("a", b, c);
        return a;
        
    }
    
    public static void main(String[] args) {
        Treesearch s= new Treesearch();
        Node root=s.create();
        s.preOrder(root);
        System.out.println();
        s.inOrder(root);
        System.out.println();
        s.postOrder(root);
        System.out.println();
        s.breadthOrder(root);
        System.out.println();
        s.s_order(root);    
    }
}

4.線索二叉樹

通過(guò)考察各種二叉鏈表央星,不管兒叉樹的形態(tài)如何,空鏈域的個(gè)數(shù)總是多過(guò)非空鏈域的個(gè)數(shù)惫东。準(zhǔn)確的說(shuō)莉给,n各結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域,非空鏈域?yàn)閚-1個(gè)廉沮,但其中的空鏈域卻有n+1個(gè)颓遏。如下圖所示。

因此滞时,提出了一種方法叁幢,利用原來(lái)的空鏈域存放指針,指向樹中其他結(jié)點(diǎn)坪稽。這種指針?lè)Q為線索曼玩。

? 記ptr指向二叉鏈表中的一個(gè)結(jié)點(diǎn),以下是建立線索的規(guī)則:

? (1)如果ptr->lchild為空窒百,則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)黍判。這個(gè)結(jié)點(diǎn)稱為ptr的中序前驅(qū);

? (2)如果ptr->rchild為空篙梢,則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼結(jié)點(diǎn)顷帖。這個(gè)結(jié)點(diǎn)稱為ptr的中序后繼;

? 顯然,在決定lchild是指向左孩子還是前驅(qū)贬墩,rchild是指向右孩子還是后繼榴嗅,需要一個(gè)區(qū)分標(biāo)志的。因此震糖,我們?cè)诿總€(gè)結(jié)點(diǎn)再增設(shè)兩個(gè)標(biāo)志域ltag和rtag录肯,注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量趴腋,其占用內(nèi)存空間要小于像lchild和rchild的指針變量吊说。結(jié)點(diǎn)結(jié)構(gòu)如下所示。

其中:

? (1)ltag為0時(shí)指向該結(jié)點(diǎn)的左孩子优炬,為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)颁井;

? (2)rtag為0時(shí)指向該結(jié)點(diǎn)的右孩子,為1時(shí)指向該結(jié)點(diǎn)的后繼蠢护;

? (3)因此對(duì)于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子雅宾。

package tree;

public class ThreadTree {
    static class TreeNode{
        int value;
        int ltag;
        int rtag;
        TreeNode left;
        TreeNode right;
    }
    
    private TreeNode pre = null;
    
    //1.建立一顆中序線索二叉樹
    void inThread(TreeNode root){
        if(root ==null) return ;
        inThread(root.left);
        if(root.left==null){
            root.ltag=1;
            root.left=pre;
        }
        if(pre!=null && pre.right==null){
            pre.right=root;
            pre.rtag=1;
        }
        pre=root;
        inThread(root.right);   
    }
    
    //2.查找任意節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
    TreeNode getPreNode(TreeNode node ){
        if(node.ltag==1){
            return node.left;
        }else{
            node=node.left;
            while(node.rtag!=1){
                node=node.right;
            }
            return node;
        }
    }
    
    //3.查找任意節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)
    TreeNode getLastNode(TreeNode node){
        if(node.rtag==1){
            return node.right;
        }else{
            node=node.right;
            while(node.ltag!=1){
                node=node.left;
            }
            return node;
        }
    }

    //4.查找值為x的節(jié)點(diǎn)
    TreeNode findNode(int x,TreeNode root){
        TreeNode p=root;
        if(p.value==x){
            return p;
        }
        if(p==pre){
            return null;
        }
        findNode(x, getLastNode(p));
        return null;
    }
    
    //5. insertnode
    void insert(int x){
        
    }
    
}

5.樹和二叉樹的轉(zhuǎn)換

本節(jié)主要介紹樹和二叉樹的轉(zhuǎn)換,森林和二叉樹的轉(zhuǎn)換葵硕,樹的遍歷和存儲(chǔ)眉抬。

樹和二叉樹的轉(zhuǎn)換

森林轉(zhuǎn)二叉樹

6.哈夫曼樹

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市懈凹,隨后出現(xiàn)的幾起案子蜀变,更是在濱河造成了極大的恐慌,老刑警劉巖介评,帶你破解...
    沈念sama閱讀 211,423評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件库北,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡们陆,警方通過(guò)查閱死者的電腦和手機(jī)寒瓦,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,147評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)坪仇,“玉大人杂腰,你說(shuō)我怎么就攤上這事∫挝模” “怎么了喂很?”我有些...
    開封第一講書人閱讀 157,019評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)雾袱。 經(jīng)常有香客問(wèn)我恤筛,道長(zhǎng),這世上最難降的妖魔是什么芹橡? 我笑而不...
    開封第一講書人閱讀 56,443評(píng)論 1 283
  • 正文 為了忘掉前任毒坛,我火速辦了婚禮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘煎殷。我一直安慰自己屯伞,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,535評(píng)論 6 385
  • 文/花漫 我一把揭開白布豪直。 她就那樣靜靜地躺著劣摇,像睡著了一般。 火紅的嫁衣襯著肌膚如雪弓乙。 梳的紋絲不亂的頭發(fā)上末融,一...
    開封第一講書人閱讀 49,798評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音暇韧,去河邊找鬼勾习。 笑死,一個(gè)胖子當(dāng)著我的面吹牛懈玻,可吹牛的內(nèi)容都是我干的巧婶。 我是一名探鬼主播,決...
    沈念sama閱讀 38,941評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開眼涂乌,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼艺栈!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起湾盒,我...
    開封第一講書人閱讀 37,704評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤湿右,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后历涝,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體诅需,經(jīng)...
    沈念sama閱讀 44,152評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,494評(píng)論 2 327
  • 正文 我和宋清朗相戀三年荧库,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了堰塌。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,629評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡分衫,死狀恐怖场刑,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情蚪战,我是刑警寧澤牵现,帶...
    沈念sama閱讀 34,295評(píng)論 4 329
  • 正文 年R本政府宣布,位于F島的核電站邀桑,受9級(jí)特大地震影響瞎疼,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜壁畸,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,901評(píng)論 3 313
  • 文/蒙蒙 一贼急、第九天 我趴在偏房一處隱蔽的房頂上張望茅茂。 院中可真熱鬧,春花似錦太抓、人聲如沸空闲。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,742評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)碴倾。三九已至,卻和暖如春掉丽,著一層夾襖步出監(jiān)牢的瞬間跌榔,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,978評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工机打, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留矫户,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,333評(píng)論 2 360
  • 正文 我出身青樓残邀,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親柑蛇。 傳聞我的和親對(duì)象是個(gè)殘疾皇子芥挣,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,499評(píng)論 2 348

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

  • 樹是n(n >= 0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹耻台。在任意一顆非空樹中: 1空免、有且僅有一個(gè)特定的稱為根(Roo...
    jtsky閱讀 892評(píng)論 0 0
  • 二叉樹的定義#### 二叉樹是n(n>=0)個(gè)具有相同類型的元素的有限集合,當(dāng)n=0時(shí)稱為空二叉樹盆耽,當(dāng)n>0時(shí)蹋砚,數(shù)...
    kylinxiang閱讀 1,381評(píng)論 0 2
  • 四坝咐、樹與二叉樹 1. 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 二叉樹的順序存儲(chǔ)就是用數(shù)組存儲(chǔ)二叉樹。二叉樹的每個(gè)結(jié)點(diǎn)在順序存儲(chǔ)中都有...
    MinoyJet閱讀 1,512評(píng)論 0 7
  • 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)析恢? 數(shù)據(jù)結(jié)構(gòu)的定義:數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合墨坚。 第二章...
    SeanCheney閱讀 5,755評(píng)論 0 19
  • 今天R語(yǔ)言給我?guī)土艘粋€(gè)大忙,簡(jiǎn)單的幾行代碼幾乎節(jié)省了我一天的時(shí)間映挂,小白表示R語(yǔ)言太有用了泽篮! 問(wèn)題如下: 我想獲取網(wǎng)...
    小熊貓?jiān)诔砷L(zhǎng)閱讀 7,420評(píng)論 8 17