熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

二叉樹的定義

2013-11-15 15:32:17  來源: 數據結構 

  二叉樹是樹形結構的一個重要類型許多實際問題抽象出來的數據結構往往是二叉樹的形式即使是一般的樹也能簡單地轉換為二叉樹而且二叉樹的存儲結構及其算法都較為簡單因此二叉樹顯得特別重要

二叉樹的定義

二叉樹的遞歸定義
  二叉樹(BinaryTree)是n(n≥)個結點的有限集它或者是空集(n=)或者由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成

.二叉樹的五種基本形態
   二叉樹可以是空集根可以有空的左子樹或右子樹或者左右子樹皆為空
  二叉樹的五種基本形態如下圖所示
 
.二叉樹不是樹的特例
)二叉樹與無序樹不同
   二叉樹中每個結點最多只能有兩棵子樹並且有左右之分
  二叉樹並非是樹的特殊情形它們是兩種不同的數據結構

)二叉樹與度數為的有序樹不同
  在有序樹中雖然一個結點的孩子之間是有左右次序的但是若該結點只有一個孩子就無須區分其左右次序而在二叉樹中即使是一個孩子也有左右之分
  【例】下圖中(a)和(b)是兩棵不同的二叉樹它們同右圖中的普通樹(作為有序樹或無序樹)很相似但卻不等同於這棵普通樹若將這三棵樹均看做普通樹則它們就是相同的了
      
  二叉樹並非是樹的特殊情形它們是兩種不同的數據結構


From:http://tw.wingwit.com/Article/program/sjjg/201311/23572.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.