알고리즘 문제2: 두 갈래 나무를 쌍방향 체인표로 변환

2400 단어
지난 블로그를 계속 하면서 두 갈래 나무의 상용 방법만 썼는데 전편에서 약간 부족했다.
1. 새 노드를 추가하면 그 코드는 독립적으로 만들어지고 귀속 방식으로 쓸 수 있다
void insertNode(BSTree* &p, int value)
{
if(p == NULL){
p = new BSTree();
p->value = value;
p->bsLeft = NULL;
p->bsRight = NULL;
return;
}
if(value < p->value)
insertNode(p->bsLeft, value);
else if(value >= p->value)
insertNode(p->bsRight, value);
}
2. 찾기도 함께 변경되고 자신에게 귀속된다
------------------------------------------------
여기에 새로운 문제를 도입하다1.   , 。 , 。           10     / \    6  14   / \ / \ 4  8 12 16           4=6=8=10=12=14=16。           :   struct BSTreeNode {    int m_nValue; // value of node    BSTreeNode *m_pLeft; // left child of node    BSTreeNode *m_pRight; // right child of node }; */

여기서 고려하면, 우리가 두루 다닐 때는 순서대로 출력한다. 그러면 우리는 이 순서 체인표를 얻을 수 있는 방법이 있기 때문에, 두루 다니는 함수를 조금만 바꾸면 된다
여기에 두 개의 공유 변수를 도입한다
BSTree* cur = NULL; BSTree*dchain_head = NULL;
아래에 두 개의 함수를 넣었는데, 주요한 것은 두 번째이다
void printDoubleChain(); voidch(BSTree*);
다음을 수행합니다.
void ch(BSTree* p) { 
	if(p==NULL){
		return; 
	} 
	ch(p->bsLeft);
 	// , 
	if(cur == NULL){ 
		cur = p;
		dchain_head = cur; 
	}else{ 
		cur->bsRight = p; 
		p->bsLeft = cur;
		cur = p; 
	} // 
	ch(p->bsRight); 
}

인쇄는 다음과 같습니다.
void printDoubleChain() { 
	cur =dchain_head; 
	cout<<"from left to right"<<endl;
	while(cur->bsRight!=NULL){ 
		cout<<cur->value<<" ";
		cur = cur->bsRight; 
	} 
	cout<<cur->value<<" ";
	// cur ,  
	//  
	cout<<"from right toleft"<<endl; 
	while(cur->bsLeft!=NULL){
		cout<<cur->value<<" "; 
		cur = cur->bsLeft; 
	}
	cout<<cur->value<<" "; 	
}

좋은 웹페이지 즐겨찾기