滿二叉樹是一棵深度為k結點數為(^k)的二叉樹完全二叉樹是滿二叉樹在最下層自右向左去處部分結點
二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續的存儲單元中(存儲前先將其畫成完全二叉樹)
樹的存儲結構多用的是鏈式存儲BinTNode的結構為lchild|data|rchild把所有BinTNode類型的結點加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構稱為二叉鏈表它就是由根指針root唯一確定的共有n個指針域n+個空指針
根據訪問結點的次序不同可得三種遍歷先序遍歷(前序遍歷或先根遍歷)中序遍歷(或中根遍歷)後序遍歷(或後根遍歷)時間復雜度為O(n)
利用二叉鏈表中的n+個空指針域來存放指向某種遍歷次序下的前趨結點和後繼結點的指針這些附加的指針就稱為線索加上線索的二叉鏈表就稱為線索鏈表線索使得查找中序前趨和中序後繼變得簡單有效但對於查找指定結點的前序前趨和後序後繼並沒有什麼作用
樹和森林及二叉樹的轉換是唯一對應的
轉換方法
·樹變二叉樹兄弟相連保留長子的連線
·二叉樹變樹結點的右孩子與其雙親連
·森林變二叉樹樹變二叉樹各個樹的根相連
樹的存儲結構
·有雙親鏈表表示法結點data | parent對於求指定結點的雙親或祖先十分方便但不適於求指定結點的孩子及後代
·孩子鏈表表示法為樹中每個結點data | next設置一個孩子鏈表firstchild並將data | firstchild存放在一個向量中
·雙親孩子鏈表表示法將雙親鏈表和孩子鏈表結合
·孩子兄弟鏈表表示法結點結構leftmostchild |data | rightsibing附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域
[] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22735.html
