二叉树

在電腦科學中，二元樹（英語：Binary tree）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構。通常分支被稱作“左子樹”或“右子樹”。二元樹的分支具有左右次序，不能随意顛倒。 二元樹的第層至多擁有個節點；深度為的二元樹至多總共有個節點（定义根节点所在深度 ），而總計擁有節點數符合的，稱為「滿二元樹」；深度為有個節點的二元樹，當且僅當其中的每一節點，都可以和深度的滿二元樹，序號1到的節點一對一對應時，稱為完全二元樹。對任何一棵非空的二元樹，如果其葉片（終端節點）數為，分支度為2的節點數為，則。 與普通樹不同，普通樹的節點個數至少為1，而二元樹的節點個數可以為0；普通樹節點的最大分支度沒有限制，而二元樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二元樹的節點有左、右次序之分。 二元樹通常作為資料結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關聯。這樣標記的二元樹就可以實現二元搜尋樹和二元堆積，並應用於高效率的搜索和排序。