二叉樹(shù)的主要性質(zhì)
性質(zhì)1：非空二叉樹(shù)上葉子節(jié)點(diǎn)數(shù)等于雙分支節(jié)點(diǎn)數(shù)加1。（使用總分支數(shù)=總節(jié)點(diǎn)數(shù)-1證明）
性質(zhì)2：二叉樹(shù)的第i層上最多有2^(i-1)個(gè)節(jié)點(diǎn)（i>=1）。
性質(zhì)3：高度為k的二叉樹(shù)最多有2^(i-1)個(gè)節(jié)點(diǎn)。
性質(zhì)4：高度為k的二叉樹(shù)最多有2^k-1個(gè)節(jié)點(diǎn)。
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
（1）順序存儲(chǔ)結(jié)構(gòu)：就是采用數(shù)組來(lái)存儲(chǔ)一個(gè)二叉樹(shù)。
（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：就是采用鏈表來(lái)存儲(chǔ)一個(gè)二叉樹(shù)。
二叉樹(shù)的遍歷
（1）先序遍歷：根左右。
（2）中序遍歷：左根右。
（3）后序遍歷：左右根。
（4）層序遍歷：從上到下，從左到右，開(kāi)始遍歷。
二叉樹(shù)的實(shí)現(xiàn)
二叉樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)類：
class Node{
private Object data =;
private Node lchild =;
private Node rchild =;
public Node(){}
public Node(Object data) {
super();
this.data = data;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getLchild() {
return lchild;
}
public void setLchild(Node lchild) {
this.lchild = lchild;
}
public Node getRchild() {
return rchild;
}
public void setRchild(Node rchild) {
this.rchild = rchild;
}
}
使用輸入的數(shù)組來(lái)構(gòu)造二叉樹(shù)：
思想：
首先將輸入的數(shù)組數(shù)據(jù)轉(zhuǎn)換成Node節(jié)點(diǎn)，并使用List存儲(chǔ)。然后構(gòu)造完了一堆節(jié)點(diǎn)，需要對(duì)節(jié)點(diǎn)之間建立關(guān)系。而關(guān)系可以根據(jù)自身定義，我的定義是輸入數(shù)組中的數(shù)據(jù)下標(biāo)為奇數(shù)做為左孩子節(jié)點(diǎn)，偶數(shù)為右孩子節(jié)點(diǎn)。然后對(duì)邊界的定義如2i+2，無(wú)論當(dāng)總節(jié)點(diǎn)為偶數(shù)時(shí)，二叉樹(shù)本身的結(jié)構(gòu)是沒(méi)有最右邊的葉子節(jié)點(diǎn)的，也就是說(shuō)此樹(shù)非滿二叉樹(shù)，那么我們使用2i+2來(lái)計(jì)算不存在的最右邊葉子節(jié)點(diǎn)的右孩子節(jié)點(diǎn)時(shí)會(huì)報(bào)下標(biāo)越界的異常。
實(shí)現(xiàn)：
/*構(gòu)造樹(shù)
* 使用數(shù)組構(gòu)造二叉樹(shù)
* 定義的規(guī)則：奇數(shù)作為左孩子，偶數(shù)的時(shí)候作為右孩子
*
* */
public static List<Node> createBt(Object[] objArr){
List<Node> retList =new ArrayList<Node>();
for(Object obj :objArr){
retList.add(new Node(obj));
}
if(retList.size() !=0){
for(int i=0;i<retList.size()/2;i++){
//奇數(shù)情況下
if(retList.get(2*i+1) !=null){
retList.get(i).setLchild(retList.get(2*i+1));
}
//偶數(shù)情況下
if(2*i+2 <=retList.size()-1 && retList.get(2*i+2) !=null){
retList.get(i).setRchild(retList.get(2*i+2));
}
}
}
return retList;
}
先序遍歷，遞歸方式遍歷二叉樹(shù)
/* 先序遍歷
* 根左右
* 遞歸方式
* */
public static void preBtByRecursion(Node n){
if(n !=null){
System.out.println("值："+n.getData());
preBtByRecursion(n.getLchild());
preBtByRecursion(n.getRchild());
}else{
return;
}
}
中序遍歷，遞歸方式遍歷二叉樹(shù)：
public static void orderBtByRecursion(Node n){
if(n !=null){
orderBtByRecursion(n.getLchild());
System.out.println("值："+n.getData());
orderBtByRecursion(n.getRchild());
}else{
return;
}
}
后序遍歷，遞歸方式遍歷二叉樹(shù)：
/* 后序遍歷
* 左右根
* 遞歸方式
* */
public static void postBtByRecursion(Node n){
if(n !=null){
postBtByRecursion(n.getLchild());
postBtByRecursion(n.getRchild());
System.out.println("值："+n.getData());
}else{
return;
}
}
先序遍歷，非遞歸方式遍歷二叉樹(shù)：
思想：
遍歷二叉樹(shù)采用當(dāng)前遍歷路徑盡可能深的去遍歷二叉樹(shù)，如果當(dāng)前路徑走到了盡頭就需要往回走，那么就需要回溯了。為了對(duì)之前走過(guò)的路徑進(jìn)行回溯，那么就需要使用一個(gè)輔助的結(jié)構(gòu)來(lái)記錄之前走過(guò)的節(jié)點(diǎn)。而我們從頭到尾的存入遍歷過(guò)的節(jié)點(diǎn)，然后從尾到頭的彈出節(jié)點(diǎn)。這種結(jié)構(gòu)恰好符合棧的結(jié)構(gòu)。所以就采用輔助棧來(lái)存儲(chǔ)遍歷過(guò)的節(jié)點(diǎn)。從而達(dá)到回溯的目得。
實(shí)現(xiàn)：
/* 先序遍歷
* 根左右
* 非遞歸方式
* */
public static void preBt(List<Node> list){
Stack<Node> stack =new Stack<Node>();
Node root =list.get(0);
while(root !=null || !stack.isEmpty()){
System.out.println("值："+root.getData());
stack.push(root);
root =root.getLchild();
while(root ==null && !stack.isEmpty()){
root =stack.pop();
root =root.getRchild();
}
}
}
中序遍歷，非遞歸方式遍歷二叉樹(shù)：
思想：
和前面的前序遍歷二叉樹(shù)的思想差不多，都是采用輔助棧來(lái)實(shí)現(xiàn)回溯。
實(shí)現(xiàn)：
/* 中序遍歷
* 左根右
* 非遞歸方式
* */
public static void orderBt(List<Node> list){
Stack<Node> stack =new Stack<Node>();
Node n =list.get(0);
while(n !=null || !stack.isEmpty()){
stack.push(n);
n =n.getLchild();
while(n ==null && !stack.isEmpty()){
n =stack.pop();
System.out.println("值："+n.getData());
n =n.getRchild();
}
}
}
后序遍歷，非遞歸方式遍歷二叉樹(shù)：
思想：
采用雙輔助棧的方式來(lái)實(shí)現(xiàn)遍歷的。后序遍歷是左右根，為了調(diào)整遍歷出來(lái)的節(jié)點(diǎn)的順序，其實(shí)除了樹(shù)最頂上的節(jié)點(diǎn)作為根外，剩下的節(jié)點(diǎn)，對(duì)于孩子節(jié)點(diǎn)父節(jié)點(diǎn)，對(duì)于同層的點(diǎn)來(lái)說(shuō)就是兄弟節(jié)點(diǎn)。所以剩下的點(diǎn)都可以當(dāng)作左右節(jié)點(diǎn)來(lái)看待了。樹(shù)最頂上的點(diǎn)在進(jìn)行操作前，先將其存入棧s1中，在從棧s1中彈出存入棧s2中。（肯定有人會(huì)問(wèn)，直接放入棧s2中不就完事了，這樣做，當(dāng)棧s1都沒(méi)有根節(jié)點(diǎn)，那么它從哪開(kāi)始遍歷都不知道）。其他節(jié)點(diǎn)就是同樣的套路了。壓入棧s1的順序左右，彈出棧的順序是右左，在壓入到棧s2的順序是右左，那么彈出棧的順序就是左右了，加上之前特殊處理的根在s2最底下，s2的整體順序就是左右根，符合后序遍歷的規(guī)則了。
實(shí)現(xiàn)：
/* 后序遍歷
* 左右根
* 非遞歸方式
* */
public static void postBt(List<Node> list){
Stack<Node> stack1 =new Stack<Node>();
Stack<Node> stack2 =new Stack<Node>();
Node n =list.get(0);
stack1.push(n);
while(!stack1.isEmpty()){
n =stack1.pop();
stack2.push(n);
if(n.getLchild() !=null){
stack1.push(n.getLchild());
}
if(n.getRchild() !=null){
stack1.push(n.getRchild());
}
}
while (!stack2.isEmpty()) {
System.out.println(stack2.pop().getData());
}
}
測(cè)試
public static void main(String[] args) {
String[] str ={"1","2","3","4","5","6"};
List<Node> list =createBt(str);
postBt(list);
}
