C 언어 데이터 구조 에서 순서 이 진 트 리 인 스 턴 스 상세 설명

C 언어 데이터 구조 에서 순서 이 진 트 리
선언:
단서 이 진 트 리 는 주로 결점 을 찾 는 선형 전구 와 후계 가 불편 한 문 제 를 해결 하기 위해 서 이다.이 는 두 개의 상징적 인 도 메 인 만 추가 하면 왼쪽 이나 오른쪽 아이의 결점 이 없 는 좌우 아이의 저장 공간 을 충분히 이용 하여 이 결점 의 선형 전구 결점 과 선형 후계 결점 을 저장 할 수 있다.두 개의 상징적 도 메 인 이 차지 하 는 공간 은 매우 적 고 이 진 링크 에 남아 있 는 저장 공간 을 충분히 이용 했다.
   단서 이 진 트 리 를 실현 하려 면 이 진 트 리 의 노드 데이터 구 조 를 다음 과 같이 정의 해 야 합 니 다(정 의 는 코드 를 보십시오).
left
leftTag
data
rightTag
right
설명:
1.       leftTag=false 시 left 가 이 노드 의 왼쪽 아 이 를 가리 키 는 것 을 표시 합 니 다.
2.       leftTag=true 일 때 left 가 이 결점 을 가리 키 는 선형 전구 결점 을 표시 합 니 다.
3.       rightTag=false 시 right 가 이 노드 의 오른쪽 아 이 를 가리 키 는 것 을 표시 합 니 다.
4.       rightTag=true 일 때 right 는 이 결점 의 선형 후계 결점 을 가리킨다.
     이 진 트 리 의 저장 구조 로 구 성 된 이 진 트 리 의 저장 구조 로 단서 이 진 트 리 라 고 합 니 다.결점 을 가리 키 는 선형 전구 나 선형 후계 결점 의 지침 을 단서 라 고 한다.단 서 를 더 한 이 진 트 리 를 단서 이 진 트 리 라 고 한다.이 진 트 리 를 어떤 순서 로 옮 겨 다 니 며 단서 이 진 트 리 로 만 드 는 과정 을 단서 화 라 고 합 니 다.
중간 순서 단서 화 이 진 트 리 알고리즘:
  중간 순서 단서 화 는 이 진 링크 노드 데이터 구조 로 이 진 트 리 의 이 진 링크 를 만 든 다음 에 중간 순서 로 옮 겨 다 니 는 방법 으로 노드 에 접근 할 때 단 서 를 만 드 는 것 을 말한다.(코드
검색 중 순서 이 진 트 리 의 한 노드 의 선형 전구 결점 알고리즘:
1.       이 노드 의 leftTag=true 라면 left 는 선형 전구 입 니 다.
2.       이 노드 의 leftTag=false 라면 이 노드 왼쪽 트 리 의 가장 오른쪽 끝 점 은 선형 전구 점 입 니 다.
(구체 적 으로 코드 를 보십시오)
검색 중 순서 이 진 트 리 의 한 노드 의 선형 후계 점 과 알고리즘:
1.       이 노드 의 right=true 라면 right 는 선형 후계 점 입 니 다.
2.       만약 이 결점 의 right=false 라면,이 결점 오른쪽 자나무 의 가장 왼쪽 끝 점 은 선형 후계 결점 이다
(구체 적 으로 코드 를 보십시오)

그림:후속 단서

그림:선구자 단서
 노드 정의:

struct Node 
{ 
  int data; 
  bool leftTag; 
  bool rightTag; 
  Node* left; 
  Node* right; 
  Node(int _data):data(_data),left(0),right(0),leftTag(false),rightTag(false){} 
}; 

클래스 정의:

class BinaryTree 
{ 
private: 
  Node* root; 
private: 
  Node* head; 
  Node* pre; 
  void makeThread(Node* node); 
public: 
  void buildThread(); 
  void traverseBySuccessor(); 
  void traverseByPredecessor(); 
 
// helper methods 
private: 
  static inline bool visit(Node* T) 
  { 
    if (T) 
    { 
      printf("data:%c, left:%c, right:%c
", 
        (char)T->data, 
        (T->left!=0) ? (char)T->left->data : '#', 
        (T->right!=0) ? (char)T->right->data : '#'); 
      return true; 
    } 
    else return false; 
  } 
}; 

방법 정의:

void BinaryTree::makeThread(Node* node) 
{ 
  if (node!=NULL) 
  { 
    makeThread(node->left); 
    if (pre!= NULL) 
    { 
      if (pre->right==NULL) //             ,                 
      { 
        pre->rightTag = true;  
        pre->right = node; 
      } 
      else pre->rightTag = false; 
    } 
    if (node->left==NULL) //             ,                 
    { 
      node->leftTag = true; 
      node->left = pre; 
    } 
    else node->leftTag = false; 
    pre = node; 
    makeThread(node->right); 
  } 
} 
 
void BinaryTree::traverseBySuccessor() 
{ 
  Node* p = head->left; //first find the root node 
  //           head          ,   p   NULL,  
  //     while ,    visit     p=p->right  
  while (p!=head) 
  { 
    while (!p->leftTag) 
      p = p->left; 
    visit(p); 
 
    while (p->rightTag && p->right!=head) 
    { 
      p = p->right; 
      visit(p); 
    } 
    p = p->right; 
  } 
  cout<<endl; 
} 
 
void BinaryTree::traverseByPredecessor() 
{ 
  Node* p = head->left; //first find the root node 
  while (p!=head) 
  { 
    while (!p->rightTag) 
      p = p->right; 
    visit(p); 
    if (p!=NULL) 
    { 
      while (p->leftTag && p->left!=head) 
      { 
        p = p->left; 
        visit(p); 
      } 
      p = p->left; 
    } 
  } 
  cout<<endl; 
} 
 
void BinaryTree::buildThread() 
{ 
  pre = NULL; 
  head = new Node('@'); 
  head->left = root; 
  head->right = head; 
  makeThread(root); 
  //    makeThread    , pre             . 
  //  pre      head,              
  // 
  pre->rightTag = 1; 
  pre->right = head; 
  pre = NULL; 
  Node* p = root; 
  /* 
   *           ，         head    。       
   */ 
  while (p->left!=NULL) 
    p = p->left; 
  p->left = head; 
} 

읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!