이 진 트 리 기본 조작

이 진 트 리 는 매우 중요 한 데이터 구조 로 서 다음 과 같은 이 진 트 리 의 기본 작업 에 대해 예제 1, 이 진 트 리 의 정 의 를 내린다.

typedef char ElementType;  
  
typedef struct BiTreeNode  
{  
    ElementType data;  
    struct BiTreeNode* lchild;  
    struct BiTreeNode* rchild;  
}BiTreeNode, *BiTree;  

2. 이 진 트 리 의 구축 과 소각 (1) 우선 순위 순 서 를 이용 하여 이 진 트 리 를 구축한다.

//             
//              
void createBiTree(BiTree &T)  
{  
    char data;  
    data = getchar();  
    if(data == '#')  
    {  
        T = NULL;  
    }  
    else  
    {  
        T = new BiTreeNode;  
        T->data = data;  
        createBiTree(T->lchild);  
        createBiTree(T->rchild);  
    }  
}  

(2) 광의 표를 이용 하여 이 진 트 리 만 들 기

//             
void createBiTreeWithGenList(BiTree &T)  
{  
    stack s;//             
    BiTree p = NULL;//          
    int k = 0;//       , k==1         ，k==2         
    char ch = getchar();  
      
    //        
    if(ch!='#')  
    {  
        p = new BiTreeNode;  
        p->data = ch;  
        p->lchild = NULL;  
        p->rchild = NULL;  
        T = p;//      
    }  
    while((ch=getchar())!='#')  
    {  
        switch(ch)  
        {  
            case '(':  
                s.push(p);//        ， p  ，p      
                k = 1;  //                
                break;  
            case ',':  
                k = 2;  //                
                break;  
            case ')':  
                s.pop();//         ，     
                break;  
            default:  
                p = new BiTreeNode;  
                p->data = ch;  
                p->lchild = NULL;  
                p->rchild = NULL;  
                if(k==1)  
                    s.top()->lchild = p;  
                else   
                    s.top()->rchild = p;  
        }         
    }  
}  

(3) 이 진 트 리 를 출력 하 는 광의 표 표시

//              
void printBiTreeWithGenList(const BiTree&T)  
{  
    if(T)  
    {  
        cout<data;  
        if(T->lchild ||T->rchild)//          
        {  
            cout<lchild);//        ，       
            if(T->rchild)          
            {  
                cout<rchild);  
            }  
            cout<

(4) 이 진 트 리 의 소각

//           
void destroyBiTree(BiTree &T)  
{  
    if(T)  
    {  
        destroyBiTree(T->lchild);  
        destroyBiTree(T->rchild);  
        delete T;  
        T = NULL;  
    }  
}  

3. 이 진 트 리 의 재 귀적 옮 겨 다 니 기 (1) 먼저 재 귀적 옮 겨 다 니 기

//            
void preOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        cout<data<lchild);//        
        preOrderTraverse(T->rchild);//        
    }  
}  

(2) 중간 순서 로 반복

//           
void inOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        inOrderTraverse(T->lchild);//        
        cout<data<rchild);//        
    }  
}  

(3) 뒷 순 서 를 반복 한다.

//           
void postOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        postOrderTraverse(T->lchild);//        
        postOrderTraverse(T->rchild);//        
        cout<data<

4. 이 진 트 리 의 다른 흔 한 재 귀 알고리즘
(1) 재 귀 트 리 의 깊이 (높이)

//          
int depthOfBiTree(const BiTree &T)  
{  
    int ldepth;  
    int rdepth;  
      
    if(T==NULL)//     
        return 0;  
    ldepth = depthOfBiTree(T->lchild);  
    rdepth = depthOfBiTree(T->rchild);  
      
    return (ldepth>rdepth)?(ldepth+1):(rdepth+1);  
}  

(2) 재 귀 구 나무의 잎 결점 개수

//               
int leafCountOfBiTree(const BiTree &T)  
{     
    if(T==NULL)  
        return 0;  
    if(T->lchild==NULL && T->rchild==NULL)  
        return 1;  
    return leafCountOfBiTree(T->lchild) + leafCountOfBiTree(T->rchild);  
}  

(3) 귀속 교환 좌우 자녀

//            
void exchangeChild(BiTree &T)  
{  
    if(T)  
    {  
        BiTree temp = NULL;  
          
        if(T->lchild ||T->rchild)  
        {  
            temp = T->lchild;  
            T->lchild = T->rchild;  
            T->rchild = temp;  
            exchangeChild(T->lchild);  
            exchangeChild(T->rchild);  
        }  
    }  
}  

5. 완전한 테스트 코드

#include   
#include   
#include   
  
using namespace std;  
  
//        
typedef char ElementType;  
  
typedef struct BiTreeNode  
{  
    ElementType data;  
    struct BiTreeNode* lchild;  
    struct BiTreeNode* rchild;  
}BiTreeNode, *BiTree;  
  
  
//             
//              
void createBiTree(BiTree &T)  
{  
    char data;  
    data = getchar();  
    if(data == '#')  
    {  
        T = NULL;  
    }  
    else  
    {  
        T = new BiTreeNode;  
        T->data = data;  
        createBiTree(T->lchild);  
        createBiTree(T->rchild);  
    }  
}  
  
//             
void createBiTreeWithGenList(BiTree &T)  
{  
    stack s;//             
    BiTree p = NULL;//          
    int k = 0;//       , k==1         ，k==2         
    char ch = getchar();  
      
    //        
    if(ch!='#')  
    {  
        p = new BiTreeNode;  
        p->data = ch;  
        p->lchild = NULL;  
        p->rchild = NULL;  
        T = p;//      
    }  
    while((ch=getchar())!='#')  
    {  
        switch(ch)  
        {  
            case '(':  
                s.push(p);//        ， p  ，p      
                k = 1;  //                
                break;  
            case ',':  
                k = 2;  //                
                break;  
            case ')':  
                s.pop();//         ，     
                break;  
            default:  
                p = new BiTreeNode;  
                p->data = ch;  
                p->lchild = NULL;  
                p->rchild = NULL;  
                if(k==1)  
                    s.top()->lchild = p;  
                else   
                    s.top()->rchild = p;  
        }         
    }  
}  


//              
void printBiTreeWithGenList(const BiTree&T)  
{  
    if(T)  
    {  
        cout<data;  
        if(T->lchild ||T->rchild)//          
        {  
            cout<lchild);//        ，       
            if(T->rchild)          
            {  
                cout<rchild);  
            }  
            cout<lchild);  
        destroyBiTree(T->rchild);  
        delete T;  
        T = NULL;  
    }  
}   
  
//            
void preOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        cout<data<lchild);//        
        preOrderTraverse(T->rchild);//        
    }  
}  
  
//           
void inOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        inOrderTraverse(T->lchild);//        
        cout<data<rchild);//        
    }  
}  
  
//           
void postOrderTraverse(const BiTree &T)  
{  
    if(T)  
    {  
        postOrderTraverse(T->lchild);//        
        postOrderTraverse(T->rchild);//        
        cout<data<lchild);  
    rdepth = depthOfBiTree(T->rchild);  
      
    return (ldepth>rdepth)?(ldepth+1):(rdepth+1);  
}  
  
//               
int leafCountOfBiTree(const BiTree &T)  
{     
    if(T==NULL)  
        return 0;  
    if(T->lchild==NULL && T->rchild==NULL)  
        return 1;  
    return leafCountOfBiTree(T->lchild) + leafCountOfBiTree(T->rchild);  
}   
  
//              
void exchangeChild(BiTree &T)  
{  
    if(T)  
    {  
        BiTree temp = NULL;  
          
        if(T->lchild ||T->rchild)  
        {  
            temp = T->lchild;  
            T->lchild = T->rchild;  
            T->rchild = temp;  
            exchangeChild(T->lchild);  
            exchangeChild(T->rchild);  
        }  
    }  
}  
   
int main(int argc, char *argv[])  
{  
    BiTree T = NULL;  
      
    createBiTree(T);//         AB#D##CE###   
//  createBiTreeWithGenList(T);//   A(B(,D),C(E))#  
      
    cout<

주: 본 고 는 글 을 전재 하기 위해 전재 원인: 나중에 스스로 보기 편 하 게 합 니 다.원문:http://blog.csdn.net/sysu_arui/article/details/7865873