두 갈래 트리 검색 및 삽입 작업
1503 단어 데이터 구조와 알고리즘
일단 나무를 정의하자!
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
맞아, 확실히 아버지의 지침이 없었어.
찾다
우선 찾기 문제를 해결하고, 찾기는 두 갈래 찾기 트리에서 가장 간단한 조작이어야 한다
사고방식 해석:
1. 노드의 val 값이value 값과 같으면 이 노드를 되돌려줍니다.
2. 찾기 노드의 val 값이value 값보다 크면 이 노드의 왼쪽 트리를 찾습니다.
3. 노드의 val 값이value 값보다 작으면 이 노드의 오른쪽 트리를 찾습니다.
사고방식은 분명하고 과정은 고통스럽다
TreeNode* TreeSearch(int val, TreeNode* root)
{
TreeNode* cur = root//
while (cur)
{
if (cur->val == val)
{
return cur;
}
else if(cur->val > val) //
{
return cur = cur->left;
}
else
{
return cur = cur->right;
}
}
return cur;//
}
삽입
사상 해석: 루트 노드에서 아래로 계속 찾고 과정은 현재 노드의 부모 노드(관건)를 기록하고 마지막으로 삽입 작업을 완성합니다. 코드는 다음과 같습니다.
TreeNode* TreeInsert(int val, TreeNode* root)
{
TreeNode* cur = root//
TreeNode* parent = NULL;//
while (cur)
{
parent = cur;//
if (cur->val == val)
return val;
if (cur->val > val)
cur = cur=>left;
else
cur = cur->right;
}
TreeNode* newNode = new TreeNode(val);
if (NULL != parent) //
{
if (parent->val > val)
{
parent->left = newNode;
}
else
{
parent->right = newNode;
}
}
return newNode;
}
응, 그렇다
먼저
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.