什么是樹？

樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由(n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有
層次關(guān)系的集合，把它叫做"樹"把它們叫做“樹”是因?yàn)樗雌饋?lái)像一顆倒掛的樹,也就是說(shuō)它是根朝上，而葉朝下的它具有這些特點(diǎn);
每個(gè)節(jié)點(diǎn)都有零個(gè)或多個(gè)子節(jié)點(diǎn)；沒(méi)有父節(jié)點(diǎn)的稱為根節(jié)點(diǎn)；除了根節(jié)點(diǎn)外,每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹；

圖片.png

樹是包含n(n>0)個(gè)節(jié)點(diǎn)的有窮集,其中；

• 每個(gè)元素稱為節(jié)點(diǎn)
• 有一個(gè)特定的結(jié)點(diǎn)被稱為根或者樹根
• 除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m≥0）個(gè)互不相交的集合T1，T2，……Tm-1，其中每一個(gè)集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree).

相關(guān)術(shù)語(yǔ)

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有子數(shù)，子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度;
• 葉節(jié)點(diǎn)或者終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)；
• 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)；
• 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
• 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；
• 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；
• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

二叉樹

什么是二叉樹？
二叉樹，就是度不差過(guò)2的樹（節(jié)點(diǎn)最多有兩個(gè)叉）

圖片.png

三.兩種特殊的二叉樹

1.滿二叉樹
一個(gè)二叉樹，如果每一個(gè)層的節(jié)點(diǎn)數(shù)都到達(dá)最大值，則這個(gè)二叉樹就
是滿二叉樹.
2.完全二叉樹
葉節(jié)點(diǎn)只能出現(xiàn)在最下層,并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的
若干位置的二叉樹

圖片.png

滿二叉樹一定是完全二叉樹,但是完全二叉樹不一定是滿二叉樹

三.二叉樹的存儲(chǔ)方式

1鏈?zhǔn)酱鎯?chǔ)方式

二叉樹的鏈?zhǔn)酱鎯?chǔ)：將二叉樹的節(jié)點(diǎn)定義為一個(gè)對(duì)象，節(jié)點(diǎn)之間通過(guò)類似鏈表的鏈接方式來(lái)連接.

from collections import deque   #雙向隊(duì)列
from queue import Queue    #單向隊(duì)列

# import queue
# q = queue.Queue()
# q.put('ggg')
# q.get()
class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None
        self.rchild = None

    @classmethod
    def pre_order(self,root):
        '''前序遍歷(根左右)'''
        if root: #如果有根節(jié)點(diǎn)
            print(root.data,end='')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    @classmethod
    def in_order(self,root):
        '''中序遍歷(左根右)'''
        if root:
            self.in_order(root.lchild)
            print(root.data,end='')
            self.in_order(root.rchild)

    @classmethod
    def out_order(self, root):
        '''后序遍歷(左右根)'''
        if root:
            self.out_order(root.lchild)
            self.out_order(root.rchild)
            print(root.data, end='')

    @classmethod
    def level_order(self,root):
        '''層次遍歷(第一層，第二層，第三層...借助隊(duì)列來(lái)實(shí)現(xiàn))'''
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            node = queue.popleft()
            print(node.data,end='')
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)



#創(chuàng)建二叉樹
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e

#查看前序遍歷的結(jié)果
BiTreeNode.pre_order(root)   #EACBDGF
print('')
BiTreeNode.in_order(root)    #ABCDEGF
print('')
BiTreeNode.out_order(root)  #BDCAFGE
print('')
BiTreeNode.level_order(root)  #EAGCFBD

2順序存儲(chǔ)方式

圖片.png

1.父節(jié)點(diǎn)和左孩子節(jié)點(diǎn)編號(hào)下標(biāo)有什么關(guān)系？
如果已知父親節(jié)點(diǎn)為i，那么他的左孩子節(jié)點(diǎn)為2i+1

圖片.png

2.父節(jié)點(diǎn)和右孩子節(jié)點(diǎn)的編號(hào)下標(biāo)有什么關(guān)系？

圖片.png

(n-1）/2=i
(n-2)  /2=i

四.二叉搜索樹

1.定義

二叉搜索樹是一顆二叉樹切滿足性質(zhì)：設(shè)x是二叉樹的一個(gè)節(jié)點(diǎn).如果y是x左子樹的一個(gè)節(jié)點(diǎn)，那么y.key<=x.key,如果y是x右子樹的一個(gè)節(jié)點(diǎn),那么y.key>=X.ky(x.ky代表x節(jié)點(diǎn)對(duì)應(yīng)的值）
通俗的說(shuō)也就是 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉搜索樹。

圖片.png

2,原理

二叉樹查找過(guò)程和次優(yōu)二叉樹類似,通常采用二叉鏈表作為二叉樹的存儲(chǔ)
結(jié)構(gòu),中序遍歷二叉樹可得到一個(gè)關(guān)鍵字的有序序列，一個(gè)無(wú)序序列，可以通過(guò)構(gòu)造一顆二叉排序樹變成一個(gè)有序序列,構(gòu)造樹的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程,每次插入的新的節(jié)點(diǎn)都是二叉樹上新的葉子節(jié)點(diǎn)，在進(jìn)行插入操作時(shí)，不必移動(dòng)其它節(jié)點(diǎn)，只需要改動(dòng)某一個(gè)節(jié)點(diǎn)的指針，由空變?yōu)榉强占瓤?，搜索，插入，刪除的復(fù)雜度等于樹高.o(log(n)

3.二叉搜索書的創(chuàng)建

可參考鏈接：https://visualgo.net/en/bst

4.二叉搜索樹的遍歷

5.二叉搜索樹的查詢,插入，刪除

插入：

圖片.png

圖片.png

圖片.png

二叉搜索樹存在問(wèn)題

存在的問(wèn)題：當(dāng)插入的是有序的時(shí)候，假如插入的數(shù)據(jù)特別多，找是能找到的，但是很浪費(fèi)時(shí)間
可以有一下解決方法：

• 隨機(jī)化的二叉樹搜索樹（打亂順序插入）
• AVL樹
  查找方法：二分查找,二叉搜素樹,哈西查找，順序查找,斐波那契查找

五.avc樹----擴(kuò)展（了解）

1.AVL樹：AVL樹是一顆平衡的二叉搜索樹
2.AVL樹具有一下性質(zhì)：

• 根的左右子樹的高度只差的絕對(duì)值不能超過(guò)1

• 根的左右子樹都是平衡的二叉樹
  3.AVL的實(shí)現(xiàn)方式:旋轉(zhuǎn)

  
  
  圖片.png

六.b樹

1.b樹：b樹是一顆自平衡的多路搜索樹,常用于數(shù)據(jù)庫(kù)的索引

圖片.png

七,其他

圖片.png