一、概念
二叉樹是n(n>=0)個元素的有限集合，改集合或者為空，或者由一個根及兩棵互不相交的左子樹和右子樹組成，其中左子樹和右子樹也均為二叉樹，
二叉樹的任一結點都有兩棵子樹（它們中的任何一個都可以是空子樹），并且這兩棵樹之間 有次序關系，及交換位置后就成為一顆不同的二叉樹，二叉樹上任意左子樹、右子樹分別稱該結點的左孩子和右孩子，
二叉樹的 五種形態，
二、型別分類
按型別分 為 完全二叉樹、滿二叉樹，
完全二叉樹的 樣子就是， 按順序排列 每一層 從左到右 按次序排， 順序不對的不能稱為完全二叉樹，
滿二叉樹是， 每一層 的分支都有兩個孩子， 除非是葉子結點，（葉子結點就是 沒有分支的結點）
滿二叉樹一定是完全二叉樹，，
三、二叉樹性質
性質1：二叉樹的第i層上至多有2i-1（i≥1）個節點 [6] ，
性質2：深度為h的二叉樹中至多含有2h-1個節點 [6] ，
性質3：若在任意一棵二叉樹中，有n0個葉子節點，有n2個度為2的節點，則必有n0=n2+1 [6] ，
性質4：具有n個節點的完全二叉樹深為log2x+1（其中x表示不大于n的最大整數） [6] ，
性質5：若對一棵有n個節點的完全二叉樹進行順序編號（1≤i≤n），那么，對于編號為i（i≥1）的節點： [6]
當i=1時，該節點為根，它無雙親節點 [6] ，
當i>1時，該節點的雙親節點的編號為i/2 [6] ，
若2i≤n，則有編號為2的左葉子，否則沒有左葉子 [6] ，
若2+1≤n，則有編號為2i+1的右葉子，否則沒有右葉子 [6] ，
四、二叉樹的遍歷
二叉樹的遍歷有 先序遍歷、 中序遍歷、后序遍歷
先序遍歷就是 先訪問根結點，再訪問左子樹，最后訪問右子樹， 根→左→右
中序遍歷就是 先訪問左子樹， 在訪問根節點，最后訪問右子樹， 左→根→右
后序遍歷 就是 先訪問 左子樹，在訪問右子樹，最后訪問根結點， 左→右→根
還有就是層次 遍歷， 就是從上到下、從左到右， 遍歷，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/142078.html
標籤：其他
上一篇：MySQL系列講義
下一篇：QWebKit 網址鏈接打不開