두 갈래 트리 검색 및 삽입 작업

오늘 두 갈래 찾기 트리, 만악의 알고리즘 도론을 접했는데 자꾸 위조 코드가 나와서 알 것 같아요. 실제로 원본 코드를 사용하는데 어려움이 많아요?밤새 고민하다가 겨우 두 갈래 나무를 조금 알게 되었다.
일단 나무를 정의하자!
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;
}

응, 그렇다
먼저

좋은 웹페이지 즐겨찾기