天天看點
傳回

【二叉樹（一）】：二叉樹簡單實作

二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實作二叉查找樹和二叉堆。樹是資料結構中的重中之重，尤其以各類二叉樹為學習的難點。

1、樹的相關概念

1.1、樹

樹是一種一對多的資料結構。樹又有很多子集，比如：二叉樹、二叉搜尋樹、2-3樹、紅黑樹等等。樹的特征：

1.沒有父結點的結點叫根，一個樹有且隻有一個根;

2.每個結點有0個或多個子結點;

3.一顆樹裡也可擁有子樹，且子樹不能相交;

樹的示例：

【二叉樹（一）】：二叉樹簡單實作

圖中标紅的為上面這個樹的子樹:

【二叉樹（一）】：二叉樹簡單實作

參考連結：每天一點算法-二叉樹 (Day8)

1.2、樹的相關術語

樹的結點（node）：包含一個資料元素及若幹指向子樹的分支；

孩子結點（child node）：結點的子樹的根稱為該結點的孩子；

雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；

兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；

祖先結點: 從根到該結點的所經分支上的所有結點

子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫

結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；

樹的深度：樹中最大的結點層

結點的度：結點子樹的個數

樹的度： 樹中最大的結點度。

葉子結點：也叫終端結點，是度為 0 的結點；

分枝結點：度不為0的結點；

有序樹：子樹有序的樹，如：家族樹；

無序樹：不考慮子樹的順序；

2、二叉樹

2.1、二叉樹定義

二叉樹是n(n>=0)個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分别稱為根結點的左子樹和右子樹組成。

一棵普通二叉樹如下所示：

【二叉樹（一）】：二叉樹簡單實作

2.2、二叉樹的特性

  • 一顆二叉樹有n個元素（n>0），它有n-1條邊
  • 一棵二叉樹高度為h(h>=0),它至少有h個元素，最多有2^h-1個元素
  • 一顆二叉樹有n個元素(n>0),它的高度為n，最小高度為[log2(n+1)]
  • 完全二叉樹的一進制素編号為i(1<=i<=n)，有以下關系成立
  1. 如果i=1，該元素為二叉樹的根。若i>1,則其父節點的編号為i/2;
  2. 如果2i>n，則表示該元素無左孩子。否則，其左孩子的編号為2i;
  3. 如果2i+1>n，則其元素無右孩子。否則其右孩子的編号為2i+1。

2.3、二叉樹分類

  • 二叉樹

二叉樹是每個節點最多有兩個子樹的樹結構。

  • 滿二叉樹

一棵深度為k，且有2^k-1個節點的樹是滿二叉樹。滿二叉樹如下圖：

【二叉樹（一）】：二叉樹簡單實作

性質：

1.如果一顆樹深度為h，最大層數為k，且深度與最大層數相同，即k=h;

2.它的葉子數是： 2^(h-1)

3.第k層的結點數是： 2^(k-1)

4.總結點數是： 2^k-1 (2的k次方減一)

5.總節點數一定是奇數。

6.樹高：h=log2(n+1)。

  • 完全二叉樹

若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h 層所有 的結點都連續集中在最左邊，這就是完全二叉樹。完全二叉樹如下圖：

【二叉樹（一）】：二叉樹簡單實作

特點：

1）葉子結點隻能出現在最下層和次下層。

2）最下層的葉子結點集中在樹的左部。

3）倒數第二層若存在葉子結點，一定在右部連續位置。

4）如果結點度為1，則該結點隻有左孩子，即沒有右子樹。

5）同樣結點數目的二叉樹，完全二叉樹深度最小。

注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。

參考連結：深入學習二叉樹(一) 二叉樹基礎

3、二叉樹的實作

3.1、資料存儲結構

  • 順序存儲
二叉樹的順序存儲結構就是使用一維數組存儲二叉樹中的結點，并且結點的存儲位置，就是數組的下标索引。
【二叉樹（一）】：二叉樹簡單實作
上圖所示的一棵完全二叉樹采用順序存儲方式，如圖下表示：
【二叉樹（一）】：二叉樹簡單實作

由上圖可以看出，當二叉樹為完全二叉樹時，結點數剛好填滿數組。

那麼當二叉樹不為完全二叉樹時，采用順序存儲形式如何呢？例如：對于上圖描述的二叉樹：

【二叉樹（一）】：二叉樹簡單實作
其中淺色結點表示結點不存在。那麼圖3.8所示的二叉樹的順序存儲結構如圖所示：
【二叉樹（一）】：二叉樹簡單實作

其中，∧表示數組中此位置沒有存儲結點。此時可以發現，順序存儲結構中已經出現了空間浪費的情況。

那麼對于右斜樹極端情況對應的順序存儲結構如圖所示：

【二叉樹（一）】：二叉樹簡單實作
由圖可以看出，對于這種右斜樹極端情況，采用順序存儲的方式是十分浪費空間的。是以，順序存儲一般适用于完全二叉樹。
  • 連結清單存儲

既然順序存儲不能滿足二叉樹的存儲需求，那麼考慮采用鍊式存儲。由二叉樹定義可知，二叉樹的每個結點最多有兩個孩子。是以，可以将結點資料結構定義為一個資料和兩個指針域。

定義結點代碼：

//連結清單節點
template <class T>
class ListNode
{
public:
    ListNode():value_(NULL),front(nullptr),next(nullptr){}
    ListNode(const T &value):value_(value),front(nullptr),next(nullptr){}
    ListNode(const T &value, ListNode<T> *left, ListNode<T> *right): value_(value),
                                                                     front(left),
                                                                     next(right){}
    ListNode(const ListNode<T> &theNode): value_(theNode.value_),
                                          front(nullptr),
                                          next(nullptr){}
public:
    T value_;
    ListNode<T> *front;
    ListNode<T> *next;
};
二叉樹可以采用下表示。
【二叉樹（一）】：二叉樹簡單實作

圖中采用一種連結清單結構存儲二叉樹，這種連結清單稱為二叉連結清單。

作者：MrHorse1992

連結：https://www.jianshu.com/p/bf73c8d50dc2

來源：簡書

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

3.2、二叉樹周遊

二叉樹的根結點出發，按照某種次序依次通路二叉樹中的所有結點，使得每個結點被通路一次，且僅被通路一次。

二叉樹的通路次序可以分為四種：前序周遊、中序周遊、後序周遊和層序周遊。

【二叉樹（一）】：二叉樹簡單實作
  • 前序周遊

前序周遊通俗的說就是從二叉樹的根結點出發，當第一次到達結點時就輸出結點資料，按照先向左在向右的方向通路。

二叉樹前序周遊如下：

1）從根結點出發，則第一次到達結點A，故輸出A;

2）繼續向左通路，第一次通路結點B，故輸出B；

3）按照同樣規則，輸出D，輸出H；

4）當到達葉子結點H，傳回到D，此時已經是第二次到達D，故不在輸出D，進而向D右子樹通路，D右子樹不為空，則通路至I，第一次到達I，則輸出I；

5）I為葉子結點，則傳回到D，D左右子樹已經通路完畢，則傳回到B，進而到B右子樹，第一次到達E，故輸出E；

6）向E左子樹，故輸出J；

7）按照同樣的通路規則，繼續輸出C、F、G；

二叉樹的前序周遊輸出為：A->B->D->H->I->E->J->C->F->G。

  • 中序周遊

中序周遊就是從二叉樹的根結點出發，當第二次到達結點時就輸出結點資料，按照先向左在向右的方向通路。

二叉樹中序周遊如下：

1）從根結點出發，則第一次到達結點A，不輸出A，繼續向左通路，第一次通路結點B，不輸出B；繼續到達D，H；

2）到達H，H左子樹為空，則傳回到H，此時第二次通路H，故輸出H；

3）H右子樹為空，則傳回至D，此時第二次到達D，故輸出D；

4）由D傳回至B，第二次到達B，故輸出B；

5）按照同樣規則繼續通路，輸出J、E、A、F、C、G。

二叉樹的中序周遊輸出為：H->D->I->B->J->E->A->F->C->G。

  • 後序周遊

後序周遊就是從二叉樹的根結點出發，當第三次到達結點時就輸出結點資料，按照先向左在向右的方向通路。

二叉樹後序周遊如下：

1）從根結點出發，則第一次到達結點A，不輸出A，繼續向左通路，第一次通路結點B，不輸出B；繼續到達D，H；

2）到達H，H左子樹為空，則傳回到H，此時第二次通路H，不輸出H；

3）H右子樹為空，則傳回至H，此時第三次到達H，故輸出H；

4）由H傳回至D，第二次到達D，不輸出D；

5）繼續通路至I，I左右子樹均為空，故第三次通路I時，輸出I；

6）傳回至D，此時第三次到達D，故輸出D；

7）按照同樣規則繼續通路，輸出J、E、B、F、G、C，A；

二叉樹的中序周遊輸出為：H->I->D->J->E->B->F->G->C->A。

作者：MrHorse1992

連結：https://www.jianshu.com/p/bf73c8d50dc2

來源：簡書

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

  • 層序周遊

層次周遊就是按照樹的層次自上而下的周遊二叉樹。

二叉樹層序周遊如下：

1）把根節點A放入隊列，此時隊列為：A，隊列頭指針指向A，也就是隊列第一個元素

2、把目前隊列頭指針所指元素的左右兒子放入隊列，即将B C放入隊列，此時隊列為A B C ，隊列頭指針向下移一格，此時指向B

3、不斷重複2步驟。此時把B的左右兒子取出來放入隊尾，隊列變為A B C D E，隊列頭指針後移，指向C，把C的左右兒子取出來放入隊尾，隊列變為A B C D E F G；

4、依次類推，直到隊列頭指針和為指針重合時，輸出最後一個元素，算法結束。

隊列從頭到尾輸出一遍，就是按層周遊，這個隊列是動态的，隻要有子節點，子節點就會不停的加入隊尾，但總有子節點沒有的時候，是以，隊列尾指針肯定有不再移動的時候，而頭指針一直在一步一步向下移，總會有首尾指針重合的時候，即标志着算法結束。

二叉樹的層次周遊結果為：A->B->C->D->E->F->G->H->I->J。

參考連結：二叉樹的按層周遊法

3.3、二叉樹的算法實作

template <class T>
class BTree
{
public:
    virtual ~BTree(){}
    virtual bool empty() const =0;
    virtual size_t size() const=0;
    //前序周遊
    virtual void preOrder()=0;
    //中序周遊
    virtual void inOrder()=0;
    //後序周遊
    virtual void postOrder()=0;
    //層次周遊
    virtual void levelOrder()=0;
};
           
/*******************************************
*                二叉樹的數組實作              *
/*******************************************/
template <class T>
class ArrayBTree
{
public:
    ArrayBTree(const size_t &capacity=10);
    ~ArrayBTree(){}

    //二叉樹元素的數量
    size_t size() const{return size_;}
    //二叉樹的容量
    size_t max_size() const{return capacity_;}
    //二叉樹是否為空
    bool empty() const{return size_==0;};


    //向二叉樹中插入元素
    void insert(const T &value);

    //删除二叉樹中的元素
    void erase(const T &value);

    //修改二叉樹中的元素
    void set(const T &index,const T &value);
    //查找二叉樹中的元素
    T get(const int &index);

    //二叉樹中搜尋對應值位置的下标
    int find(const T &value);

    //列印二叉樹
    void print();

    //前序周遊
    void preOrder();
    //中序周遊
    void inOrder();
    //後序周遊
    void postOrder();
    //層次周遊
    void levelOrder();
private:
    void insert_(const T &value,int index);     //插入元素
    void erase_(const int &index);              //删除元素并重新調整二叉樹
    int find_(const T &value,int index);        //搜尋二叉樹

    void preOrder_(const int &index);           //前序周遊
    void inOrder_(const int &index);            //中序周遊
    void postOrder_(const int &index);          //後序周遊
    void levelOrder_(const int &index);         //層次周遊
private:
    shared_ptr<T> ptr_;                         //存儲二叉樹數的數組
    size_t size_;                               //二叉樹元素的大小
    size_t capacity_;                           //二叉樹的容量
};

template <class T>
ArrayBTree<T>::ArrayBTree(const size_t &capacity):capacity_(capacity),
                                                  size_(0)
{
    ptr_=shared_ptr<T>(new T[capacity_],[](T *p){delete[] p;});
    fill(ptr_.get(),ptr_.get()+capacity_,-1);
}

template <class T>
void ArrayBTree<T>::insert_(const T &value, int index)
{
    if(index>=capacity_){
        cerr<<"index out of capacity(in function insert_)"<<endl;
        exit(0);
    }

    if(ptr_.get()[index]==-1){
        ptr_.get()[index]=value;
    } else{
        if(ptr_.get()[index]>=value){
            insert_(value,index*2+1);
        }else{
            insert_(value,index*2+2);
        }
    }
}

template <class T>
void ArrayBTree<T>::insert(const T &value)
{
    if(size_+1>=capacity_){
        cerr<<"tree capacity is out of max size"<<endl;
        exit(0);
    }

    if(this->empty()){
        *ptr_.get()=value;
    }else{
        insert_(value,0);
    }

    ++size_;
}

template <class T>
void ArrayBTree<T>::erase_(const int &index)
{
    if(index*2+1>=capacity_ || (ptr_.get()[index*2+1]==-1 &&
                               ptr_.get()[index*2+2]==-1)){
        ptr_.get()[index]=-1;
        return ;
    }
    if(ptr_.get()[index*2+1]!=-1 && (ptr_.get()[index*2+2]==-1 ||
            ptr_.get()[index*2+2]>=capacity_)){
        ptr_.get()[index]=-1;
        T value=ptr_.get()[index*2+1];
        ptr_.get()[index*2+1]=-1;
        insert(value);
        return ;
    }

    ptr_.get()[index]=ptr_.get()[index*2+2];
    erase_(index*2+2);
}

template <class T>
void ArrayBTree<T>::erase(const T &value)
{
    int index=find(value);

    if(-1==index){
        cerr<<"erase id fail,"<<value<<" don't in the tree"<<endl;
        exit(0);
    }else{
        erase_(index);
        --size_;
    }
}

template <class T>
void ArrayBTree<T>::set(const T &index, const T &value)
{
    if(index<0 || index>=capacity_){
        cerr<<"index out of capacity(in function insert_)"<<endl;
        exit(0);
    }

    if(ptr_.get()[index]==-1){
        insert(value);
    }else{
        erase(ptr_.get()[index]);
        insert(value);
    }
}

template <class T>
T ArrayBTree<T>::get(const int &index)
{
    if(index<0 || index>=capacity_){
        cerr<<"index out of capacity(in function insert_)"<<endl;
        exit(0);
    }

    if(ptr_.get()[index]==-1){
        cerr<<"Don't find value in the tree"<<endl;
        return -1;
    } else{
        return ptr_.get()[index];
    }

}

template <class T>
int ArrayBTree<T>::find_(const T &value, int index)
{
    if(ptr_.get()[index]==-1 || index>=capacity_){
        cerr<<"Don't find "<<value<<" in the tree"<<endl;
        return -1;
    }

    if(ptr_.get()[index]==value){
        return index;
    }else if(ptr_.get()[index] > value){
        return find_(value,index*2+1);
    } else{
        return find_(value,index*2+2);
    }
}

template <class T>
int ArrayBTree<T>::find(const T &value)
{
    if(this->empty()){
        cerr<<"tree is empty"<<endl;
        exit(0);
    }

    return find_(value,0);
}

template <class T>
void ArrayBTree<T>::print()
{
    for(auto i=0;i<capacity_;++i){
        cout<<ptr_.get()[i]<<" ";
    }
    cout<<endl;
}


template <class T>
void ArrayBTree<T>::preOrder_(const int &index)
{
    if(index>=capacity_ || ptr_.get()[index]==-1){
        return;
    }

    cout<<ptr_.get()[index]<<" ";
    preOrder_(index*2+1);
    preOrder_(index*2+2);
}

template <class T>
void ArrayBTree<T>::preOrder()
{
    preOrder_(0);
}

template <class T>
void ArrayBTree<T>::inOrder_(const int &index)
{
    if(index>=capacity_ || ptr_.get()[index]==-1){
        return;
    }

    inOrder_(index*2+1);
    cout<<ptr_.get()[index]<<" ";
    inOrder_(index*2+2);
}

template <class T>
void ArrayBTree<T>::inOrder()
{
    inOrder_(0);
}

template <class T>
void ArrayBTree<T>::postOrder_(const int &index)
{
    if(index>=capacity_ || ptr_.get()[index]==-1){
        return;
    }



    postOrder_(index*2+1);
    postOrder_(index*2+2);
    cout<<ptr_.get()[index]<<" ";
}

template <class T>
void ArrayBTree<T>::postOrder()
{
    postOrder_(0);
}

template <class T>
void ArrayBTree<T>::levelOrder_(const int &index)
{
    if(index>=capacity_ || ptr_.get()[index]==-1){
        return;
    }

    int left=0,right=0;
    left=right=index;
    while(left<capacity_ && right<capacity_){
        for(int i=left;i<=right;++i){
            T value=ptr_.get()[i];
            if(value!=-1){
                cout<<value<<" ";
            }
        }
        cout<<endl;
        left=left*2+1;
        right=right*2+2;
    }

}

template <class T>
void ArrayBTree<T>::levelOrder()
{
    levelOrder_(0);
}
           
/*******************************************
*                二叉樹的連結清單實作              *
/*******************************************/
template <class T>
class ListBTree:public BTree<T>
{
public:
    ListBTree():phead_(nullptr),size_(0){}
    ListBTree(const ListBTree<T> &other); //拷貝構造函數，複制整棵樹
    ~ListBTree();

    //擷取二叉樹的根
    ListNode<T> *get_root(){return phead_;}
    //判斷二叉樹是否為空
    bool empty() const{return size_==0;}
    //傳回二叉樹元素的個數
    size_t size() const{return size_;}
    size_t &set_size(){return size_;}

    //插入節點
    void insert(const T &value);
    void insert(const ListNode<T> &theNode);

    //删除節點
    void erase(const T &value);

    //二叉樹中搜尋對應值位置
    ListNode<T> *find(const T &value);

    //拷貝二叉樹
    ListNode<T> *clone() const;

    //前序周遊
    void preOrder();
    //中序周遊
    void inOrder();
    //後序周遊
    void postOrder();
    //層次周遊
    void levelOrder();
private:
    void insert_(ListNode<T> *node,ListNode<T> *&cur);  //插入節點
    void erase_(const T &value,ListNode<T> *&node);     //删除節點
    void delete_(ListNode<T> *node);                    //删除整個二叉樹
    ListNode<T> *clone_(ListNode<T> *node) const;       //拷貝二叉樹

    void preOrder_(ListNode<T> *node);                  //前序周遊
    void inOrder_(ListNode<T> *node);                   //中序周遊
    void postOrder_(ListNode<T> *node);                 //後序周遊

    ListNode<T> *get_parents(ListNode<T> *node);        //擷取目前節點的父節點
private:
    ListNode<T> *phead_;
    size_t size_;
};

template <class T>
ListBTree<T>::ListBTree(const ListBTree<T> &other)
{
    if(other.empty()){
        phead_= nullptr;
    }else{
        phead_=other.clone();
    }
}

template <class T>
void ListBTree<T>::delete_(ListNode<T> *node)
{
    if(node!= nullptr){
        ListNode<T> *cur=node;
        delete_(node->front);
        delete_(node->next);
        delete cur;
        cur= nullptr;
    }
}

template <class T>
ListBTree<T>::~ListBTree()
{
    if(phead_!= nullptr){
        delete_(phead_);
    }
}

template <class T>
void ListBTree<T>::insert_(ListNode<T> *node,ListNode<T> *&cur)
{
    if(cur== nullptr) {
        cur = new ListNode<T>(node->value_);
        return ;
    }

    if(cur->value_<=node->value_){
        insert_(node,cur->next);
    } else{
        insert_(node,cur->front);
    }
}

template <class T>
void ListBTree<T>::insert(const T &value)
{
    ListNode<T> *node=new ListNode<T>(value);

    if(phead_== nullptr){
        phead_=node;
    }else{
        insert_(node,phead_);
    }

    ++size_;
}

template <class T>
void ListBTree<T>::insert(const ListNode<T> &theNode)
{
    ListNode<T> *node=new ListNode<T>(theNode);

    if(phead_== nullptr){
        phead_=node;
    }else{
        insert_(node,phead_);
    }

    ++size_;
}

template <class T>
void ListBTree<T>::erase_(const T &value, ListNode<T> *&node)
{
    if(node== nullptr){
        return ;
    }

    if(value<node->value_){
        erase_(value,node->front);
    } else if(value>node->value_){
        erase_(value,node->next);
    }else if(node->front!= nullptr && node->next!= nullptr){
        ListNode<T> *tmp=node->next;
        while(tmp->front!= nullptr){
            tmp=tmp->front;
        }

        node->value_=tmp->value_;
        erase_(node->value_,node->next);
    }else{
        ListNode<T> *tmp=node;
        node=(node->front!= nullptr)?node->front:node->next;
        delete tmp;
        tmp= nullptr;
    }
}

template <class T>
void ListBTree<T>::erase(const T &value)
{
    if(phead_== nullptr){
        return ;
    }

    erase_(value,phead_);
    --size_;
}

template <class T>
ListNode<T> *ListBTree<T>::find(const T &value)
{
    if(phead_== nullptr){
        return nullptr;
    }

    ListNode<T> *cur=phead_;
    while(cur != nullptr){
        if(cur->value_<value){
            cur=cur->next;
        } else if(cur->value_>value){
            cur=cur->front;
        }else{
            return cur;
        }
    }
    return nullptr;
}

template <class T>
ListNode<T> *ListBTree<T>::clone_(ListNode<T> *node) const
{
    if(node== nullptr){
        return nullptr;
    }

    return new ListNode<T>(node->value_,
                           clone_(node->front),
                           clone_(node->next));
}

template <class T>
ListNode<T> *ListBTree<T>::clone() const
{
    if(phead_== nullptr){
        return nullptr;
    }

    return clone_(phead_);
}

template <class T>
void ListBTree<T>::preOrder_(ListNode<T> *node)
{
    if(node== nullptr){
        return ;
    }
    cout<<node->value_<<" ";
    preOrder_(node->front);

    preOrder_(node->next);
}

template <class T>
void ListBTree<T>::preOrder()
{
    if(phead_== nullptr){
        return ;
    }

    preOrder_(phead_);
}

template <class T>
void ListBTree<T>::inOrder_(ListNode<T> *node)
{
    if(node== nullptr){
        return ;
    }

    inOrder_(node->front);
    cout<<node->value_<<" ";
    inOrder_(node->next);
}

template <class T>
void ListBTree<T>::inOrder()
{
    if(phead_== nullptr){
        return ;
    }

    inOrder_(phead_);
}

template <class T>
void ListBTree<T>::postOrder_(ListNode<T> *node)
{
    if(node== nullptr){
        return ;
    }

    postOrder_(node->front);
    postOrder_(node->next);
    cout<<node->value_<<" ";
}

template <class T>
void ListBTree<T>::postOrder()
{
    if(phead_== nullptr){
        return ;
    }

    postOrder_(phead_);
}

template <class T>
void ListBTree<T>::levelOrder()
{
    if(phead_== nullptr){
        return ;
    }

    ListQueue<ListNode<T>* > queue;
    queue.push(phead_);
    while(!queue.empty()){
        ListNode<T> *cur=queue.pop();
        cout<<cur->value_<<" ";
        if(cur->front!= nullptr){
            queue.push(cur->front);
        }
        if(cur->next!= nullptr){
            queue.push(cur->next);
        }
    }
}

詳細代碼可以參考我的github代碼:https://github.com/kingqiuol/algorithm_practice/blob/master/assignment5/binary_tree.h

資料結構和算法
上一篇: 【二叉樹（二）】：二叉搜尋樹
下一篇: 二叉樹題目一：二叉樹的先序周遊，中序周遊，後序周遊 ，層周遊。題目二：輸入一顆二叉樹的跟節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在傳回值的list中，數組長度大的數組靠前)題目三：二叉搜素樹的後序周遊題目四：求二叉樹的深度題目五：平衡二叉樹 

繼續閱讀