![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/langzh-hant-640px-Binary_tree.svg.png&w=640&q=50)
二叉樹
每個節點至多有兩個小孩的樹狀資料結構 / 維基百科,自由的 encyclopedia
在電腦科學中,二元樹(英語:Binary tree)是每個節點最多只有兩個分支(即不存在分支度大於2的節點)的樹結構[1]。通常分支被稱作「左子樹」或「右子樹」。二元樹的分支具有左右次序,不能隨意顛倒。
![]() |
![]() |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/192px-Binary_tree.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Binary_tree.png/640px-Binary_tree.png)
二元樹的第層至多擁有
個節點;深度為
的二元樹至多總共有
個節點(定義根節點所在深度
),而總計擁有節點數符合的,稱為「滿二元樹」;深度為
有
個節點的二元樹,當且僅當其中的每一節點,都可以和深度
的滿二元樹,序號1到
的節點一對一對應時,稱為完全二元樹。對任何一棵非空的二元樹
,如果其葉片(終端節點)數為
,分支度為2的節點數為
,則
。
與普通樹不同,普通樹的節點個數至少為1,而二元樹的節點個數可以為0;普通樹節點的最大分支度沒有限制,而二元樹節點的最大分支度為2;普通樹的節點無左、右次序之分,而二元樹的節點有左、右次序之分。
二元樹通常作為資料結構應用,典型用法是對節點定義一個標記函數,將一些值與每個節點相關聯。這樣標記的二元樹就可以實現二元搜尋樹和二元堆積,並應用於高效率的搜索和排序。