나무 - 두 갈래 나무 두루 다니기
2004 단어 데이터 구조와 알고리즘#나무.
생각
반복은 실제적으로 어떤 순서에 따라 결점을 방문하는데 비교적 전형적인 것은 선순, 중순, 후순, 층순 등이 있다.두 갈래 나무는 천연적으로 자 구조를 가지고 있다. 즉, 왼쪽 갈래 나무와 오른쪽 갈래 나무는 똑같이 두 갈래 나무로 규모가 더 작을 뿐이다.두 갈래 나무의 세 가지 역행 방식
1.1 선순
창고 S;p= root; while(p | | S가 비어 있지 않음) {while(p) {p 노드에 접근하기; p의 오른쪽 트리가 S에 들어가기;//오른쪽 트리 p = p의 왼쪽 트리를 임시로 저장하기; } p = S.top; 아웃소싱//오른쪽 트리 처리}
vector preorderTraversal(TreeNode* root) {
vector vec;
stack stk;
while (root || !stk.empty()) {
while (root) {
vec.push_back(root->val); //
stk.push(root->right);
root = root->left; //
}
root = stk.top(); stk.pop(); //
} //
return vec;
} 1.2중서
창고 S;p= root; while (p | | S가 비어 있지 않음) {while (p) {p in S;p = p의 왼쪽 트리;//왼쪽 트리 방문} p = S.top 창고;액세스 p;//루트 p = p의 오른쪽 하위 트리 액세스;//오른쪽 하위 트리에 액세스하십시오.}
vector inorderTraversal(TreeNode* root) {
vector vec;
stack stk;
while (root || !stk.empty()) {//root ， ；stk ，
while (root) {
stk.push(root);
root = root->left;
}//
root = stk.top(); stk.pop(); // ，
vec.push_back(root->val); // （ ）
root = root->right; //
}
return vec;
} 1.3 후순
왼쪽 트리->오른쪽 트리->뿌리.뒤서열이 두루 돌아다니는 것이 가장 어려운데, 왜?뿌리는 마지막에 창고에서 나온 것이다.순환으로 이루어지면왼쪽 트리를 처리하기 전에 뿌리 결점을 창고에 넣어야 한다.창고 꼭대기 원소를 얻은 후 오른쪽 나무를 처리할 것인가 아니면 뿌리를 직접 처리할 것인가를 판단해야 한다.여기에서 포인터prev가 방문한 결점을 가리키는 매우 교묘한 방법을 사용합니다.
vector postorderTraversal(TreeNode* root) {
vector vec;
stack stk;
TreeNode *prev = nullptr;
while (root || !stk.empty()) {
while (root) {
stk.push(root);
root = root->left;
} //
root = stk.top(); //
if (root->right && root->right != prev) { //
root = root->right;
}
else { // ，
vec.push_back(root->val);
stk.pop();
prev = root; //
root = nullptr; //
}
} //
return vec;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
