二叉樹知識(BST) 二叉查找樹(Binary Search Tree)

二叉樹基礎(chǔ)知識總結(jié) - CSDN博客


二叉樹遍歷分析

?簡單二叉樹遍歷,可分為:先序那婉,中序详炬,后序呛谜。

?先序: 1.訪問根結(jié)點隐岛;2.訪問左子樹礼仗;3.訪問右子樹

中序:1.訪問左子樹元践; 2.訪問根結(jié)點单旁; 3.訪問右子樹

原則:1訪問左子樹饥伊。【先訪問左子樹中的左子樹愉豺,再訪問左子樹中的右子樹茫因。】直到訪問到葉子結(jié)點后輸出冻押。

2輸出根。

3訪問右子樹洛巢「遘裕【先訪問右子樹中的左子樹,再訪問右子樹中的右子樹∶灼唬】直到訪問到葉子結(jié)點后輸出。

?后序:1.訪問左子樹

    ?2.訪問右子樹

? ? ? ? ? 3.訪問根

1訪問左子樹良瞧⊙党【先訪問左子樹中的左子樹,再訪問左子樹中的右子樹】。直到訪問到葉子結(jié)點后輸出。

2訪問右子樹澜薄√幔【先訪問右子樹中的左子樹茅特,再訪問右子樹中的右子樹】。直到訪問到葉子結(jié)點后輸出妒峦。

3再返回訪問根肯骇,并輸出卤恳。

具體步驟:

? 先訪問A的左子樹。再訪問左子樹中的左子樹若债〔鹑冢【即:A的左子樹為B,再訪問B的左子樹D傲须。D沒有左右子樹趟脂,輸出D∥羝冢】,然后訪問左子樹中的右子樹累澡。【即:訪問B的右子樹F愧哟,F(xiàn)還有左子樹,再訪問F的左子樹E蕊梧,E沒有左右子樹。輸出E望几。再輸出F萤厅,再輸出B√栉叮】。

? 然后訪問A的右子樹疟羹。再訪問右子樹中的左子樹¢冢【即:A的右子樹為C救湖,再訪問C的左子樹G。G還有右子樹H力九,輸出H邑闺。再輸出G,再輸出G】陡舅,然后訪問右子樹中的右子樹≡痔浚【即:訪問C的右子樹I摊灭,I沒有左右子樹,輸出I掏缎。在輸出C。再輸出A眷蜈。】辜妓。

? 所以忌怎,后序遍歷輸出結(jié)果為:(D E F B)(H G I C)A



插入節(jié)點

插入的節(jié)點是葉子節(jié)點籍滴;

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末孽惰,一起剝皮案震驚了整個濱河市勋功,隨后出現(xiàn)的幾起案子库说,更是在濱河造成了極大的恐慌,老刑警劉巖潜的,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件夏块,死亡現(xiàn)場離奇詭異,居然都是意外死亡脐供,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門酌壕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來卵牍,“玉大人沦泌,你說我怎么就攤上這事⌒磺” “怎么了萝衩?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵猩谊,是天一觀的道長祭刚。 經(jīng)常有香客問我,道長涡驮,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任淋袖,我火速辦了婚禮锯梁,結(jié)果婚禮上陌凳,老公的妹妹穿的比我還像新娘内舟。我一直安慰自己,他們只是感情好验游,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布耕蝉。 她就那樣靜靜地躺著,像睡著了一般蒜魄。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上谈为,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天伞鲫,我揣著相機與錄音签舞,去河邊找鬼驹闰。 笑死嘹朗,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的屹培。 我是一名探鬼主播怔檩,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼薛训,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了乙埃?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤甫何,失蹤者是張志新(化名)和其女友劉穎遇伞,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體巍耗,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年娄琉,在試婚紗的時候發(fā)現(xiàn)自己被綠了吓歇。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片城看。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡测柠,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出朝扼,到底是詐尸還是另有隱情,我是刑警寧澤观游,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站搪柑,受9級特大地震影響拌屏,放射性物質(zhì)發(fā)生泄漏倚喂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望仑嗅。 院中可真熱鬧鸵贬,春花似錦、人聲如沸地沮。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽吉殃。三九已至,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間迫卢,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留眨层,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像叁征,于是被迫代替她去往敵國和親捺疼。 傳聞我的和親對象是個殘疾皇子永罚,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

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