[자료구조] 트리(Tree) - 이진검색트리에서 다음노드 찾기 (inorder traversal)

아래의 영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다.
[자료구조 알고리즘] 이진검색트리에서 다음노드 찾기 (inorder traverse)
https://youtu.be/6DIxzakjewQ

(1) .h

	#pragma once
	#include <iostream>
	#include <vector>
	using namespace std;
	class Node
	{
	public:
	int data;
	Node* left, * right, *parent;
	Node(int data) {
	this->data = data;
	this->left = this->right = this->parent= NULL;
	}
	};
	class Tree
	{
	public:
	Node* root = NULL;
	Tree(vector<int> a)
	{
	root = bst(a, 0, a.size() - 1, NULL);
	//root->right->right->right->right = new Node(-1);
	}
	Node* bst(vector<int> a, int start, int end, Node* parent)
	{
	if (start <= end)
	{
	int mid = (start + end) / 2;
	Node* newNode = new Node(a[mid]);
	newNode->left = bst(a, start, mid - 1, newNode);
	newNode->right = bst(a, mid + 1, end, newNode);
	newNode->parent = parent;
	return newNode;
	}
	return NULL;
	}
	//이진검색트리에서
	//주어진 노드의 다음노드를
	//찾는 함수를 구현(inorder에 입각함)
	void findNextNode(Node* node)
	{
	if (node->right == NULL)
	{
	cout << findAbove(node->parent, node)->data << " is " <<
	node->data << "'s next" << endl;
	}
	else
	{
	cout << findBelow(node->right)->data << " is " <<
	node->data << "'s next" << endl;
	}
	}
	Node* findAbove(Node* parent, Node* child)//부모를 찾는다
	{
	if (parent == NULL) return NULL;
	if (parent->left == child) return parent;
	else return findAbove(parent->parent, parent);
	}
	Node* findBelow(Node* node)//left를 찾는다
	{
	if (node->left == NULL) return node;
	else return findBelow(node->left);
	}
	};

view raw 트리_이진검색트리에서 다음노드 찾기 (inorder traversal).h hosted with ❤ by GitHub

(2) .cpp

	#include "header.h"
	int main() {
	//정렬 되어있는 배열을 넣는다
	Tree* t = new Tree({ 0,1,2,3,4,5,6,7,8,9 });
	//4 is 3's next
	t->findNextNode(t->root->left->right->right);
	return 0;
	}

view raw 트리_이진검색트리에서 다음노드 찾기 (inorder traversal).cpp hosted with ❤ by GitHub