二叉樹的一系列操作，二叉樹一系列操作

二叉樹的一系列操作，二叉樹一系列操作

//二叉樹學習過程中的問題和代碼集合
//按先序序列創建二叉樹
//樹的高度
//求樹的結點數
//求二叉樹第K層的節點個數
//求二叉樹中葉子節點的個數
//求二叉樹中節點的最大距離
//兩結點最低公共祖先
//判斷二叉樹是不是平衡二叉樹
//釋放樹空間

//感謝：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888#topic1
 
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

//二叉樹結點
typedef int DateType;
typedef struct BiTNode{
    DateType data;
    struct BiTNode *lchild,*rchild,*m_pLeft,*m_pRight;
}BiTNode,*BiTree;

//按先序序列創建二叉樹
int CreateBiTree(BiTree &T){

    char data;
    //‘#’表示空樹
    cin>>data;
    if(data == '#'){
        T = NULL;
    }
    else{
        T = (BiTree)malloc(sizeof(BiTNode));

        T->data = data;

        CreateBiTree(T->lchild);

        CreateBiTree(T->rchild);
    }
    return 0;
}
//輸出
void Visit(BiTree T){
    if(T->data != '#'){
        printf("%c ",T->data);
    }
}

//先序遍歷
void PreOrder(BiTree T){
    if(T != NULL){
        //訪問根節點
        Visit(T);
        //訪問左子結點
        PreOrder(T->lchild);
        //訪問右子結點
        PreOrder(T->rchild);
    }
}
//中序遍歷  
void InOrder(BiTree T){  
    if(T != NULL){  
        //訪問左子結點  
        InOrder(T->lchild);  
        //訪問根節點  
        Visit(T);  
        //訪問右子結點  
        InOrder(T->rchild);  
    }  
}  
//後序遍歷
void PostOrder(BiTree T){
    if(T != NULL){
        //訪問左子結點
        PostOrder(T->lchild);
        //訪問右子結點
        PostOrder(T->rchild);
        //訪問根節點
        Visit(T);
    }
}

//樹的高度
//Depth(t)= max( Depth(lchild),Depth(rchild) ) + 1
int BinTreeDepth(BiTree t)
{
    int h,h1,h2;
    if(t == NULL)    return 0;
    else
    {
        h1 = BinTreeDepth(t->lchild);
        h2 = BinTreeDepth(t->rchild);
        h = max(h1,h2) + 1;
        return h;
    }

}

//求樹的結點數
//樹的結點數=左子樹 + 右子樹 + 1；
int getNodeNum(BiTree t)
{
    if(t == NULL) return 0;
    return (getNodeNum(t->lchild)+getNodeNum(t->rchild)+1);
}

//求二叉樹第K層的節點個數
//NodeNum(t,k) = NodeNum(t->lchild,k-1)+NodeNum(t->rchild,k-1)
int GetNodeNumKthLevel(BiTree t, int k)
{
    if(t == NULL || k < 1)
        return 0;
    if(k == 1)
        return 1;
    // 左子樹中k-1層的節點個數
    int numLeft = GetNodeNumKthLevel(t->lchild, k-1); 
    // 右子樹中k-1層的節點個數
    int numRight = GetNodeNumKthLevel(t->rchild, k-1); 
    return (numLeft + numRight);
}

//求二叉樹中葉子節點的個數
//左右兒子為NULL
//則：LeafNum(t) = LeafNum(t->lchild) + LeafNum(t->rchild);
int GetLeafNodeNum(BiTree t)
{
    if(t == NULL) 
        return 0;
    if(t->lchild ==NULL && t->rchild ==NULL) 
        return 1;
    int numleft = GetLeafNodeNum(t->lchild);
    int numright = GetLeafNodeNum(t->rchild);

    return (numleft + numright);
}

//求二叉樹中節點的最大距離
//MaxDistance(t->lchild)//MacDistance(t->rchild)
//MaxLeft(t->lchild)+MaxRight(t->rchild)
int GetMaxDistance(BiTree t, int & maxLeft, int & maxRight)
{
    // maxLeft, 左子樹中的節點距離根節點的最遠距離
    // maxRight, 右子樹中的節點距離根節點的最遠距離
    if(t == NULL)
    {
        maxLeft = 0;
        maxRight = 0;
        return 0;
    }
    int maxLL, maxLR, maxRL, maxRR;
    int maxDistLeft, maxDistRight;
    if(t->lchild != NULL)
    {
        maxDistLeft = GetMaxDistance(t->lchild, maxLL, maxLR);
        maxLeft = max(maxLL, maxLR) + 1;
    }
    else
    {
        maxDistLeft = 0;
        maxLeft = 0;
    }
    if(t->rchild != NULL)
    {
        maxDistRight = GetMaxDistance(t->rchild, maxRL, maxRR);
        maxRight = max(maxRL, maxRR) + 1;
    }
    else
    {
        maxDistRight = 0;
        maxRight = 0;
    }
    return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);
}

//兩結點最低公共祖先
//如果兩個節點分別在根節點的左子樹和右子樹，則返回根節點
//如果兩個節點都在左子樹，則遞歸處理左子樹；如果兩個節點都在右子樹，則遞歸處理右子樹
//求最近公共祖先：
/*
//應該就是這樣的啊，為什麼運行的時候出現內存訪問沖突的問題........
bool FindNode(BiTree t, DateType x)
{
    if(t == NULL || x == NULL)
        return false;
    if(t->data == x)
        return true;
    bool found = FindNode(t->lchild, x);
    if(!found)
        found = FindNode(t->rchild, x);
    return found;
}

DateType  GetLastCommonParent(BiTree t ,DateType A,DateType B)
{
    if(FindNode(t->lchild,A))
    {
        if(FindNode(t->rchild,B))
            return t->data;
        else
            return GetLastCommonParent(t->lchild,A,B);
    }
    else
    {
        if(FindNode(t->lchild,B))
            return t->data;
        else
            return GetLastCommonParent(t->rchild,A,B);
    }
}
*/

//判斷二叉樹是不是平衡二叉樹
//如果左子樹和右子樹都是AVL樹並且左子樹和右子樹高度相差不大於1，返回真，其他返回假
bool isAVL(BiTree t, int & height)
{
    if(t == NULL) // 空樹，返回真
    {
        height = 0;
        return true;
    }
    int heightLeft;
    bool resultLeft = isAVL(t->lchild, heightLeft);
    int heightRight;
    bool resultRight = isAVL(t->rchild, heightRight);
    // 左子樹和右子樹都是AVL，並且高度相差不大於1，返回真
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) 
    {
        height = max(heightLeft, heightRight) + 1;
        return true;
    }
    else
    {
        height = max(heightLeft, heightRight) + 1;
        return false;
    }
}

//釋放樹空間
void DestroyBinTree(BiTree t)
{
    if(t==NULL) return;
    DestroyBinTree(t->lchild); 
    DestroyBinTree(t->rchild);
    t->lchild=NULL;
    t->rchild=NULL;
    free(t);
}


//先序遍歷(非遞歸)
//思路：訪問T->data後，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，
//出棧,再先序遍歷T的右子樹。

void PreOrder2(BiTree T){
    stack<BiTree> stack;
    //p是遍歷指針
    BiTree p = T;
    //棧不空或者p不空時循環
    while(p || !stack.empty()){
        if(p != NULL){
            //存入棧中
            stack.push(p);
            //訪問根節點
            printf("%c ",p->data);
            //遍歷左子樹
            p = p->lchild;
        }
        else{
            //退棧
            p = stack.top();
            stack.pop();
            //訪問右子樹
            p = p->rchild;
        }
    }//while
}
//中序遍歷(非遞歸)
//思路：T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹後，訪問根，再遍歷右子樹。
//先將T入棧，遍歷左子樹；
//遍歷完左子樹返回時，棧頂元素應為T，出棧，訪問T->data，再中序遍歷T的右子樹。

void InOrder2(BiTree T){
    stack<BiTree> stack;
    //p是遍歷指針
    BiTree p = T;
    //棧不空或者p不空時循環
    while(p || !stack.empty()){
        if(p != NULL){
            //存入棧中
            stack.push(p);
            //遍歷左子樹
            p = p->lchild;
        }
        else{
            //退棧，訪問根節點
            p = stack.top();
            printf("%c ",p->data);
            stack.pop();
            //訪問右子樹
            p = p->rchild;
        }
    }//while
}

//後序遍歷(非遞歸)
typedef struct BiTNodePost{
    BiTree biTree;
    char tag;
}BiTNodePost,*BiTreePost;
//後序遍歷
void PostOrder2(BiTree T){
    stack<BiTreePost> stack;
    //p是遍歷指針
    BiTree p = T;
    BiTreePost BT;
    //棧不空或者p不空時循環
    while(p != NULL || !stack.empty()){
        //遍歷左子樹
        while(p != NULL){
            BT = (BiTreePost)malloc(sizeof(BiTNodePost));
            BT->biTree = p;
            //訪問過左子樹
            BT->tag = 'L';
            stack.push(BT);
            p = p->lchild;
        }
        //左右子樹訪問完畢訪問根節點
        while(!stack.empty() && (stack.top())->tag == 'R'){
            BT = stack.top();
            //退棧
            stack.pop();
            BT->biTree;
            printf("%c ",BT->biTree->data);
        }
        //遍歷右子樹
        if(!stack.empty()){
            BT = stack.top();
            //訪問過右子樹
            BT->tag = 'R';
            p = BT->biTree;
            p = p->rchild;
        }
    }//while
}
//層次遍歷
void LevelOrder(BiTree T){
    BiTree p = T;
    //隊列
    queue<BiTree> queue;
    //根節點入隊
    queue.push(p);
    //隊列不空循環
    while(!queue.empty()){
        //對頭元素出隊
        p = queue.front();
        //訪問p指向的結點
        printf("%c ",p->data);
        //退出隊列
        queue.pop();
        //左子樹不空，將左子樹入隊
        if(p->lchild != NULL){
            queue.push(p->lchild);
        }
        //右子樹不空，將右子樹入隊
        if(p->rchild != NULL){
            queue.push(p->rchild);
        }
    }
}
int main()
{

    //測試：ABC##DE#G##F###
    //測試：124##57##8##3#6##
    BiTree T;
    cout<<"先序輸入二叉樹"<<endl;
    CreateBiTree(T);

    printf("先序遍歷：\n");
    PreOrder(T);
    printf("\n");

    printf("先序遍歷(非遞歸)：\n");
    PreOrder2(T);
    printf("\n");

    printf("中序遍歷：\n");
    InOrder(T);
    printf("\n");

    printf("中序遍歷(非遞歸)：\n");
    InOrder2(T);
    printf("\n");

    printf("後序遍歷：\n");
    PostOrder(T);
    printf("\n");

    printf("後序遍歷(非遞歸)：\n");
    PostOrder2(T);
    printf("\n");

    printf("層次遍歷：\n");
    LevelOrder(T);
    printf("\n");

    cout<<endl<<"樹的高度為："<<BinTreeDepth(T)<<endl<<endl;

    cout<<"結點數"<<getNodeNum(T)<<endl<<endl;

    cout<<"二叉樹第K層的節點個數"<<endl;
    int k;    cin>>k;
    cout<<"二叉樹第K層的節點個數"<<endl;
　　 cout<<GetNodeNumKthLevel(T,k)<<endl<<endl;

    cout<<"二叉樹中葉子節點的個數"<<endl<<GetLeafNodeNum(T)<<endl<<endl;

    int maxLeft = 0;
    int maxRight = 0;
    cout<<"二叉樹中節點的最大距離"<<endl;
　　cout<<<<GetMaxDistance(T, maxLeft, maxRight)<<endl<<endl;

    //cout<<"兩結點最低公共祖先"<<endl;
    //DateType A,B;
    ///cin>>A>>B;
    //cout<<GetLastCommonParent(T,A,B)<<endl;

    int height = 0;
    cout<<"判斷二叉樹是不是平衡二叉樹"<<endl<<isAVL(T,height)<<endl<<endl;

    cout <<"釋放樹空間"<<endl<<endl;
    DestroyBinTree(T);

    system("pause");
    return 0;
}

總結：

二叉樹的操作主要是用遞歸，只要用遞歸的思想就很容易解決問題，可是遞歸的效率不高，所以在遍歷的時候要想想不用遞歸該怎麼做？

接下來：

用分層的方法來創建二叉樹

訪問內存出錯的問題，指針

線索二叉樹、搜索二叉樹。