두 갈래 나무 각종 반복 조작
11161 단어 알고리즘과 데이터 구조학교 모집 면접
1 두 갈래 나무 깊이 구하기
1.1 반복 실현
1.2 비귀속 실현(대기열)
1.3 비귀속 실현(창고)
2 가닥나무 높이 구하기
3 두 갈래 나무 순서대로
3.1 반복 버전
3.2 비귀속 버전
3.3 순서를 이용하여 두 갈래 나무 만들기
4 두 갈래 나무의 순서
4.1 반복 버전
4.2 비귀속 버전
5 두 갈래 나무 뒤에 차례대로
5.1 반복 버전
5.2 비귀속 버전
6 두 갈래 나무층 서열 두루
7 두 갈래 나무 깊이 우선 반복
8 두 갈래 나무 넓이 우선 훑어보기
9 두 갈래 나무 노드 사이의 최대 거리를 구한다
10 두 갈래 나뭇잎 노드 수량 계산
11 두 갈래 나무의 뿌리 노드에서 지정한 노드로의 경로 가져오기
12 두 경로의 마지막 공통 노드 가져오기
13 두 결점을 얻은 최근 공동 조상
본고는 두 갈래 나무에 관한 각종 역행 알고리즘을 총결하였다.
먼저 두 갈래 나무 노드 구조체를 정의합니다
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};1 두 갈래 나무 깊이 구하기
1.1 반복 실현
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL)
return 0;
int nleft = TreeDepth(pRoot->left);
int nright = TreeDepth(pRoot->right);
return (nleft>nright)?(nleft+1):(nright+1);
}1.2 비귀속 실현(대기열)
len를 사용하여 이 층의 결점 개수, 즉 대기열의 현재 길이를 기록한 다음에 순서대로 대기열에서 이 층의 len 결점에 접근하여 대기열len 요소를 대기열에서 내보내고 다음 층을 대기열에 넣어야 한다.int TreeDepth(TreeNode* pRoot)
{
queue q;
if(!pRoot) return 0;
q.push(pRoot);
int level=0;
while(!q.empty()){
int len=q.size();
level++;
while(len--){
TreeNode* tem=q.front();
q.pop();
if(tem->left) q.push(tem->left);
if(tem->right) q.push(tem->right);
}
}
return level;
} 1.3 비귀속 실현(창고)
#include
#include
using namespace std;
typedef struct BinTree
{
int data;
BinTree *lc;
BinTree *rc;
}BTNode,*BinTree;
int max(int a,int b)
{
return (a>b)?a:b;
}
int BinTreeDepth(BinTree T)
{
stack s;
BinTree p = T,r = NULL;
int depth=0;
while(p||!s.empty())
{
if(p)
{ //
s.push(p);
int size = s.size();//
depth = max(depth,size);//
p = p->lc;
}
else
{ //
p = s.top();
if(p->rc&&p->rc!=r)// ，
{
p = p->rc;
s.push(p);
int size = s.size();//
depth = max(depth,size);//
p = p->lc;
}else
{
p=s.top();
s.pop();
cout<data< 2 가닥나무 높이 구하기
깊이를 구하는 것과 마찬가지로 유일한 차이점은 뿌리 노드에 대해 깊이는 1이고 높이는 0이다.
int Height(TreeNode *node)
{
if(node == NULL)
return -1;
else
return 1 + Max(Height(node->left),Height(node->right));
}3 두 갈래 나무 순서대로
3.1 반복 버전
void preOrderTraverse(TreeNode *root) {
if (root != NULL) {
cout<val<left);
preOrderTraverse(root->right);
}
} 3.2 비귀속 버전
void PreOrder(TreeNode* pRoot)// ，
{
if (pRoot == NULL)
return;
stack s;
TreeNode *p = pRoot;
while (p != NULL || !s.empty())
{
if (p != NULL)
{
cout << p->val << " ";
s.push_back(p);
p = p->left;
}
else
{
p = s.pop();
p = p->right;
}
}
cout << endl;
} 3.3 순서를 이용하여 두 갈래 나무 만들기
//
void CreateBiTree(BiTree &T)
{
char c;
cin >> c;
if ('#' == c)
T=NULL;
else
{
T = (BiNode* ) malloc(sizeof(BiNode));
T->val = c;
CreateBiTree(T->left);
CreateBiTree(T->right);
}
}4 두 갈래 나무의 순서
4.1 반복 버전
void inOrderTraverse(TreeNode* root) {
if (root != NULL) {
inOrderTraverse(root->left);
cout<val<right);
}
} 4.2 비귀속 버전
void inOrderTraverse(TreeNode* root) {
stack s;
TreeNode* pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
s.push(pNode);
pNode = pNode->left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = s.pop();
cout<val<right;
}
}
} 5 두 갈래 나무 뒤에 차례대로
5.1 반복 버전
public void postOrderTraverse(TreeNode root) {
if (root != null) {
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.val+" ");
}
} 5.2 비귀속 버전
void PostOrder(BiTree &T)// （ ），
{
if (T == NULL)
return;
vector S1,S2;
BiNode *p ;//
S1.push_back(T);
while (!S1.empty())
{
p = S1[S1.size() - 1];
S1.pop_back();
S2.push_back(p);
if (p->left)
S1.push_back(p->left);
if (p->right)
S1.push_back(p->right);
}
while (!S2.empty())
{
cout << S2[S2.size() - 1]->val << " ";
S2.pop_back();
}
cout << endl;
}
6 두 갈래 나무층 서열 두루
void levelTraverse(TreeNode* root) {
if (root == NULL) {
return;
}
queue q;
queue.push_back(root);
while (!q.empty()) {
TreeNode* node = q.pop_front();
cout<val<left != NULL) {
q.push_back(node->left);
}
if (node->right != NULL) {
q.push_back(node->right);
}
}
} 7 두 갈래 나무 깊이 우선 반복
깊이 우선순위는 선순위입니다.
//
void depthFirstSearch(Tree root){
stack nodeStack;
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
cout<data;//
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //
}
if(node->lchild){
nodeStack.push(node->lchild); //
}
}
}
8 두 갈래 나무 넓이 우선 훑어보기
광도 우선은 사실 층층이 누적되어 있어 대열을 이용하면 실현하기 쉽다.
//
void breadthFirstSearch(Tree root){
queue nodeQueue; // C++ STL
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
cout<data;//
if(node->lchild){
nodeQueue.push(node->lchild); //
}
if(node->rchild){
nodeQueue.push(node->rchild); //
}
}
}
9 두 갈래 나무 노드 사이의 최대 거리를 구한다
int GetMaxDistance(BiTree &T)// ，
{
if (T == NULL)
return 0;
int Distance = TreeDepth(T->left) + TreeDepth(T->right);
int l_Distance = GetMaxDistance(T->left);
int r_Distance = GetMaxDistance(T->right);
Distance = (Distance > r_Distance) ? Distance : r_Distance;
Distance = (Distance > l_Distance) ? Distance : l_Distance;
return Distance;
}
10 두 갈래 나뭇잎 노드 수량 계산
int CountLeafNode(BiTree &T)// ，
{
if (T == NULL)
return 0;
if (T->left == NULL&&T->right == NULL)
return 1;
return CountLeafNode(T->left)+CountLeafNode(T->right);
}11 두 갈래 나무의 뿌리 노드에서 지정한 노드로의 경로 가져오기
//
void GetNodePath(BiNode* T, BiNode* Node, vector& Path,int &found)
{
if (T == NULL)
return;
Path.push_back(T);
if (T == Node)
found = 1;
if (!found)
{
GetNodePath(T->left, Node, Path, found);
}
if (!found)
{
GetNodePath(T->right, Node, Path, found);
}
if (!found)
Path.pop_back();
else
return;
} 12 두 경로의 마지막 공통 노드 가져오기
//
BiNode* GetLastCommonNode(const vector Path1, const vector Path2)
{
vector::const_iterator iter1 = Path1.begin();
vector::const_iterator iter2 = Path2.begin();
BiNode *p = NULL;
while ( iter1 != Path1.end() && iter2 != Path2.end() && *iter1 != *iter2 )
{
if (*iter1 == *iter2)
p = *iter1;
iter1++;
iter2++;
}
return p;
} 13 두 결점을 얻은 최근 공동 조상
//
BiNode* GetLastCommonParent(BiNode* T, BiNode* Node1, BiNode* Node2)
{
if (T == NULL || Node1 == NULL || Node2 == NULL)
return NULL;
vector Path1, Path2;
int found1 = 0;
int found2 = 0;
GetNodePath(T, Node1, Path1,found1);
GetNodePath(T, Node2, Path2, found2);
return GetLastCommonNode(Path1,Path2);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 앞 순서, 중간 순서, 뒤 순서, 깊이 우선 검색, 폭 우선 검색광범위한 우선 검색(Breadth-First-Search)은 루트 노드에서 시작하여 층층이 접근하여 직관적인 생각에 비교적 부합된다.대기열의 선진적인 선출 특성을 사용하여 특정한 층 노드를 방문한 후 이 층 노드를 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
