本篇文章將結(jié)合《算法》第4版、業(yè)界大牛的博客和自己的理解帐要，具體描述二叉樹(shù)的一些概念把敞，如有錯(cuò)誤，請(qǐng)大佬指出榨惠。如有侵權(quán)奋早，請(qǐng)聯(lián)系我刪除，謝謝赠橙。
二叉樹(shù)
1.基本概念
(1)二叉樹(shù)是一個(gè)有限的結(jié)點(diǎn)集合伸蚯，該集合或者為空，或者由一個(gè)根結(jié)點(diǎn)及其兩棵互不相交的左简烤、右二叉子樹(shù)所組成剂邮。
二叉樹(shù)具有以下特點(diǎn)：二叉樹(shù)可以為空，空的二叉樹(shù)沒(méi)有結(jié)點(diǎn)横侦，非空二叉樹(shù)有且只有一個(gè)根結(jié)點(diǎn)挥萌；每一個(gè)結(jié)點(diǎn)最多只有2棵子樹(shù)绰姻，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)；二叉樹(shù)的子樹(shù)有左引瀑、右之分狂芋，其次序不能任意顛倒。(2)滿(mǎn)二叉樹(shù)和完全二叉樹(shù)
滿(mǎn)二叉樹(shù)是指除了最后一層外憨栽，每一層上的所有結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)的二叉樹(shù)帜矾。
完全二叉樹(shù)是指除了最后一層外，每一層上的結(jié)點(diǎn)樹(shù)均達(dá)到最大值屑柔，在最后一層上只缺少右邊的若干結(jié)點(diǎn)屡萤。
滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)掸宛。
2.主要性質(zhì)(原諒我不知道怎么打上標(biāo)>.<)
- 一棵非空二叉樹(shù)的第k層上最多有(2的k-1次方)個(gè)結(jié)點(diǎn)(K≥1)死陆；
- 深度為m的滿(mǎn)二叉樹(shù)中有(2的m次方-1)個(gè)結(jié)點(diǎn)；
- 對(duì)任何一棵二叉樹(shù)而言唧瘾，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)措译；
- 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度k至少為[log?n]+1,其中[log?n]取log?n的整數(shù)部分；
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log?n]+1饰序；
- 設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)领虹。如果從根結(jié)點(diǎn)開(kāi)始，按層序(每一層從左往右)用自數(shù)1求豫，2···塌衰，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k(k=1,2···,n)的結(jié)點(diǎn)有以下結(jié)論：
若 k = 1注祖，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)均唉；
若 k > 1是晨，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為k/2;
若 2k ≤ n，則編號(hào)k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k舔箭，否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(顯然也沒(méi)有右子結(jié)點(diǎn))罩缴；
若 2k + 1 ≤ n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1层扶，否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)箫章。
3.存儲(chǔ)結(jié)構(gòu)
二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成镜会。由于每個(gè)元素可以有2個(gè)后件(即2個(gè)子結(jié)點(diǎn))檬寂，所以用于存儲(chǔ)二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的指針域有2個(gè)：一個(gè)指向該結(jié)點(diǎn)的左子節(jié)點(diǎn)的存儲(chǔ)地址，稱(chēng)為左指針域戳表；另外一個(gè)指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址桶至，稱(chēng)為右指針域昼伴。因此二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也成為二叉鏈表。二叉樹(shù)的一個(gè)存儲(chǔ)結(jié)點(diǎn)如下：
| 左指針域 | 數(shù)據(jù)域 | 右指針域 |
|---|---|---|
| L(i) | Data(i) | R(i) |
對(duì)于滿(mǎn)二叉樹(shù)和完全二叉樹(shù)镣屹，可以按層級(jí)進(jìn)行順序存儲(chǔ)圃郊。
4.二叉樹(shù)的遍歷
二叉樹(shù)的遍歷是指不重復(fù)地訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。分為前序遍歷女蜈，中序遍歷和后序遍歷持舆。
- 前序遍歷首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)伪窖，最后遍歷右子樹(shù)逸寓。
- 中序遍歷首先訪(fǎng)問(wèn)左子樹(shù)，然后遍歷根結(jié)點(diǎn)惰许，最后遍歷右子樹(shù)席覆。
- 后序遍歷首先訪(fǎng)問(wèn)左子樹(shù)，然后遍歷右子樹(shù)汹买，最后遍歷根結(jié)點(diǎn)佩伤。
下面用一個(gè)二叉樹(shù)的例子進(jìn)行說(shuō)明，
對(duì)該二叉樹(shù)進(jìn)行3種遍歷晦毙，
- 前序遍歷的結(jié)果為：A-B-D-G-E-H-C-F-I
- 中序遍歷的結(jié)果為：G-D-B-E-H-A-C-F-I
- 后序遍歷的結(jié)果為：G-D-B-E-H-I-F-C-A
總結(jié)：
- 已知前序遍歷序列和中序遍歷序列生巡，可以唯一確定這棵二叉樹(shù)；
- 已知后序遍歷序列和中序遍歷序列见妒，可以唯一確定這棵二叉樹(shù)孤荣；
- 已知前序遍歷序列和后序遍歷序列，不能確定二叉樹(shù)须揣。
這一篇講的是二叉樹(shù)的基本要點(diǎn)盐股，內(nèi)容挺多，還很重要耻卡，筆試撤柚考點(diǎn)，需要重視卵酪。下一篇講查找技術(shù)幌蚊，講應(yīng)用最廣泛的順序查找和二分法查找。敬請(qǐng)期待哦<(￣︶￣)>溃卡。
