데이터 구조 빠 른 회고 - 이 진 트 리

이 진 트 리 (Binary Tree) 는 유한 요소 의 집합 으로 이 집합 은 비어 있 거나 뿌리 (root) 라 고 불 리 는 요소 와 교차 하지 않 는 두 개의 왼쪽 트 리 와 오른쪽 트 리 라 고 불 리 는 이 진 트 리 로 구성 된다.집합 이 비어 있 을 때 이 두 갈래 나 무 를 빈 두 갈래 나무 라 고 부른다.이 진 트 리 에서 하나의 원소 도 하나의 결점 이 라 고 부른다.
기본 개념:
(1) 결점 의 도.결점 이 가지 고 있 는 하위 나무의 개 수 를 이 결점 의 도 라 고 한다.
(2) 엽 결점.도 0 의 결점 을 엽 결점 이 라 고 부 르 거나 단말기 결점 이 라 고 부른다.
(3) 분지 결점.도 0 이 아 닌 결점 을 분기 결점 이 라 고 부 르 거나 비 단말기 결점 이 라 고 부른다.한 그루 나무의 결점 은 잎의 결점 을 제외 하고 나머지 는 모두 지점 이다.
(4) 왼쪽 아이, 오른쪽 아이, 부모.나무 에 있 는 결점 이 있 는 나무의 뿌리 결점 을 이 결점 의 아이 라 고 부른다.이 결점 을 아이의 결점 이 라 고 부 르 는 양친.같은 부 모 를 가 진 아이의 결점 을 서로 형제 라 고 부른다.
(5) 경로, 경로 길이.만약 에 한 나무의 한 줄 의 결점 n1, n2,..., nk 는 다음 과 같은 관계 가 있다. 결점 ni 는 Ni + 1 의 아버지 결점 (1 ≤ i < k) 이 고 n1, n2,..., nk 를 n1 에서 nk 까지 의 경로 라 고 부른다.이 경로 의 길 이 는 k - 1 입 니 다.
(6) 조상, 자손.나무 에서 결점 M 에서 결점 N 까지 의 경로 가 있다 면 M 은 N 의 조상 이 라 고 부 르 고 N 은 M 의 자손 이 라 고 부른다.
(7) 결점 의 층수.나무의 뿌리 결산 점 을 규정 하 는 층 수 는 1 이 고, 나머지 결산 점 의 층 수 는 그의 부모 결산 점 의 층수 에 1 을 더 하 는 것 과 같다.
(8) 나무의 깊이.나무의 모든 결점 의 최대 층 수 를 나무의 깊이 라 고 한다.
(9) 나무의 도.나무의 각 결점 도의 최대 치 를 이 나무의 도 라 고 한다.
(10) 이 진 트 리 가 가득 합 니 다. 이 진 트 리 에 모든 가지 결점 이 왼쪽 나무 와 오른쪽 나무 가 존재 하고 모든 잎 결점 이 같은 층 에 있 습 니 다. 이런 이 진 트 리 를 이 진 트 리 라 고 합 니 다.
 
다음은 이 진 트 리 의 노드 구 조 를 보 여 줍 니 다.

1 //       
2 
3 typedef struct BinaryTreeNode 4 { 5     int m_nValue; 6     BinaryTreeNode *m_pLeft; 7     BinaryTreeNode *m_pRight; 8     
9 }node;

 
이 진 트 리 의 기본 동작: 노드 개수 계산, 트 리 깊이 계산, 앞 순서 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤 순서 옮 겨 다 니 기 및 넓 은 검색
그 중에서 앞 순 서 는 재 귀 대신 스 택 을 사용 하 는 실현 방법 을 보 여 주 었 다.

 1 //          
 2 
 3 int getNodeNum(node *pRoot)  4 {  5     if(pRoot == NULL)  6         return 0;  7     return getNodeNum(pRoot->m_pLeft)+getNodeNum(pRoot->m_pRight)+1;  8 }  9 
 10 
 11 //      
 12 int getDepth(node *pRoot)  13 {  14     if(pRoot == NULL)  15         return 0;  16     int depthLeft = getDepth(pRoot->m_pLeft);  17     int depthRight = getDepth(pRoot->m_pRight);  18     
 19     return depthLeft>depthRight ? (depthLeft+1) :(depthRight+1);  20     
 21 }  22 
 23 //              
 24 /*        ：  25 （1）       ，     26 （2）        ，     ，       ，         27       ：  28 */
 29 void PreOrderTraverse(node *pRoot)  30 {  31     if(pRoot == NULL)  32         return;  33  Visit(pRoot);  34     PreOrderTraverse(pRoot->m_pLeft);  35     PreOrderTraverse(pRoot->m_pRight);  36 }  37 //         
 38 void PreOrderTraverse(node *pRoot)  39 {  40  InitStack(S);  41     while(!StackEmpty(S))  42  {  43         node *p = new node();  44         //           
 45         while(GetTop(S,p)&& p)  46             Push(p->m_pLeft);  47         Pop(S,p);//      
 48         if(!StackEmpty(S))  49  {  50  Pop(S,p);  51             if(!Visit(p->data))  52                 return 0;//        
 53             Push(S,p->m_pRight);  54  }  55  }  56 }  57 
 58 //    
 59 
 60 void InOrderTraverse(node *pRoot)  61 {  62     if(pRoot == NULL)  63         return;  64     InOrderTraverse(pRoot->m_pLeft);  65  Visit(pRoot);  66     InOrderTraverse(pRoot->m_pRight);  67 }  68 
 69 //    
 70 void PostOrderTraverse(node *pRoot)  71 {  72     if(pRoot == NULL)  73         return;  74     
 75     PostOrderTraverse(pRoot->m_pLeft);  76     PostOrderTraverse(pRoot->m_pRight);  77  Visit(pRoot);  78 }  79 
 80 //      
 81 /*
 82      ，        。      ，      ：      ，  ，             ，      。  83 */
 84 void LevelTraverse(node *pRoot)  85 {  86     if(pRoot == NULL)  87         return;  88     
 89     quene<node *> q;  90  q.push(pRoot);  91     
 92     while(!q.empty())  93  {  94         node *pNode = q.front();  95  q.pop();  96         
 97  Visit(pNode);  98         if(pNode->m_pLeft != NULL)  99             q.push(pNode->m_pRight); 100         if(pNode->m_pRight != NULL) 101             q.push(pNode->m_pRight); 102  } 103     return; 104 }

 
 
 
참고:http://www.cztvu.ah163.net/czcai/soft/kj/sjjg/jj/ch6.htm