二叉樹code

二叉樹遍歷

import java.util.Stack;

/**
 * @ author:mian
 * @ DATA:2018/5/7 16:10
 */
class Node{
    public int value;
    public Node left;
    public Node right;
    public Node(int data){
        this.value = data;
    }
}
public class 二叉樹遍歷 {
    //前序遍歷-遞歸
    public static void preOrderRecur(Node head){
        if(head==null){
            return;
        }
        System.out.println(head.value+" ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    //中序遍歷
    public static void inOrderRecur(Node head){
        if(head==null){
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value+"");
        inOrderRecur(head.right);
    }
    //后序遍歷
    public static void posOrderRecur(Node head){
        if(head==null){
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value+" ");
    }
    //前序非遞歸
    public static void preOrderUnRecur(Node head){
        System.out.println("pre-order:");
        if(head!=null){
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()){
                head=stack.pop();
                System.out.println(head.value+" ");
                if(head.right!=null){
                    stack.push(head.right);
                }
                if(head.left!=null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }
    //中序非遞歸
    public static void inOrderUnRecur(Node head){
        System.out.println("in-order");
        if(head!=null){
            Stack<Node> stack=new Stack<Node>();
            if(head!=null){
                while(!stack.isEmpty()||head!=null){
                    if(head!=null){
                        stack.push(head);
                        head = head.left;
                    }else{
                        head = stack.pop();
                        System.out.println(head.value+" ");
                        head = head.right;
                    }
                }
            }
        }
        System.out.println();
    }
}

前序呻逆,中序振诬,后序任選兩個重構(gòu)二叉樹

import java.util.HashMap;

/**
 * @ author:mian
 * @ DATA:2018/5/7 16:51
 */
public class 遍歷序列重構(gòu)二叉樹 {
    //先序和中序重構(gòu)二叉樹
    public static Node preInToTree(int[] pre,int[] in){
        if(pre==null||in==null){
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
    }
    public static Node preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,HashMap<Integer,Integer> map){
        if(pi>pj){
            return null;
        }
        Node head = new Node(p[pi]);
        int index = map.get(p[pi]);
        head.left = preIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
        head.right =preIn(p,pi+index-ni,pj,n,index+1,nj,map);
        return head;
    }

    //中序和后序
    public static Node inPosToTree(int[] in,int[] pos){
        if(in==null||pos==null){
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return inPos(in,0,in.length-1,pos,0,pos.length-1,map);
    }
    public static Node inPos(int[] n,int ni,int nj,int[] s,int si,int sj,HashMap<Integer,Integer> map){
        if(si>sj){
            return null;
        }
        Node head=new Node(s[sj]);
        int index = map.get(s[sj]);
        head.left = inPos(n,ni,index-1,s,si,si+index-ni-1,map);
        head.right=inPos(n,index+1,nj,s,si+index-ni,sj-1,map);
        return head;
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末观话,一起剝皮案震驚了整個濱河市益缠,隨后出現(xiàn)的幾起案子贬养,更是在濱河造成了極大的恐慌权烧,老刑警劉巖翠肘,帶你破解...
    沈念sama閱讀 212,816評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件檐束,死亡現(xiàn)場離奇詭異,居然都是意外死亡束倍,警方通過查閱死者的電腦和手機(jī)被丧,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,729評論 3 385
  • 文/潘曉璐 我一進(jìn)店門盟戏,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人甥桂,你說我怎么就攤上這事柿究。” “怎么了黄选?”我有些...
    開封第一講書人閱讀 158,300評論 0 348
  • 文/不壞的土叔 我叫張陵蝇摸,是天一觀的道長。 經(jīng)常有香客問我办陷,道長貌夕,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,780評論 1 285
  • 正文 為了忘掉前任民镜,我火速辦了婚禮啡专,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘制圈。我一直安慰自己们童,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,890評論 6 385
  • 文/花漫 我一把揭開白布离唐。 她就那樣靜靜地躺著病附,像睡著了一般问窃。 火紅的嫁衣襯著肌膚如雪亥鬓。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 50,084評論 1 291
  • 那天域庇,我揣著相機(jī)與錄音嵌戈,去河邊找鬼。 笑死听皿,一個胖子當(dāng)著我的面吹牛熟呛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播尉姨,決...
    沈念sama閱讀 39,151評論 3 410
  • 文/蒼蘭香墨 我猛地睜開眼庵朝,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了又厉?” 一聲冷哼從身側(cè)響起九府,我...
    開封第一講書人閱讀 37,912評論 0 268
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎覆致,沒想到半個月后侄旬,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,355評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡煌妈,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,666評論 2 327
  • 正文 我和宋清朗相戀三年儡羔,在試婚紗的時候發(fā)現(xiàn)自己被綠了宣羊。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,809評論 1 341
  • 序言:一個原本活蹦亂跳的男人離奇死亡汰蜘,死狀恐怖仇冯,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情族操,我是刑警寧澤赞枕,帶...
    沈念sama閱讀 34,504評論 4 334
  • 正文 年R本政府宣布,位于F島的核電站坪创,受9級特大地震影響炕婶,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜莱预,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,150評論 3 317
  • 文/蒙蒙 一柠掂、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧依沮,春花似錦涯贞、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,882評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至辜限,卻和暖如春皇拣,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背薄嫡。 一陣腳步聲響...
    開封第一講書人閱讀 32,121評論 1 267
  • 我被黑心中介騙來泰國打工氧急, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人毫深。 一個月前我還...
    沈念sama閱讀 46,628評論 2 362
  • 正文 我出身青樓吩坝,卻偏偏與公主長得像,于是被迫代替她去往敵國和親哑蔫。 傳聞我的和親對象是個殘疾皇子钉寝,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,724評論 2 351

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