[이진트리] 기본 c++구현 및 이진 트리 순회 설명(전위,중위,후위)

목차

 

이진트리의 정의

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조를 말한다.

 

 

 

 

 

 

 

 

 

 

 

 

이미지출처: https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

• 노드: 트리의 구성요소에 해당하는 A, B, C 와 같은 요소들을 말한다.
• 간선: 노드와 노드를 연결하는 연결선을 말한다,
• 루트노드: 트리 구조에서 최상위에 존재하는  P와 같은 요소를 말한다.
• 단말노드: 아래로 또 다른 노드가 연결되어 있지 않은 E, F, G, H 같은 요소를 말한다.
• 내부노드: 단말노드를 제외한 모든 노드로 A, B와 같은 노드를 말한다.
• 레벨: 트리의 각 층을 숫자로 매긴것을 레벨이라고 한다.
• 높이:트리의 최고 레벨을 가리켜 높이라고 한다.

 

이진트리의 기본적인 ADT

#ifndef BINARYTREE_H
#define BINARYTREE-H

typedef int BTData;

typedef struct BTreeNode{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
}

BTreeNode * MakeBTreeNode(void);    //노드의 생성을 해준다.

BTData GetData(BTreeNode * bt);    //노드에 저장된 데이터를 반환

void setData(BTreeNode * bt, BTData data);   //노드에 데이터를 저장


BTreeNode * GetLeftSubTree(BTreeNode * bt);   //왼쪽 서브 트리 주소 값 반환
BTreeNode * GetRightSubTree(BTreeNode * bt);  //오른쪽 서브 트리 주소 값 반환


void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);   //메인 트리 왼쪽에 서브 트리 추가
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);  //메인 트리 오른쪽에 서브 트리 추가


#endif

 

 

이진 트리 c++ 기본적인 구현

#include <iostream>

using namespace std;

struct Node {
	struct Node* left;
	struct Node* right;
	int data;
};

class BinaryTree {

public:
	Node* Tree;

	BinaryTree() {
		Tree = MakeTreeNode();
	}
	Node* MakeTreeNode() {
		Node* newNode = new Node;
		newNode->left = nullptr;
		newNode->right = nullptr;
		return newNode;
	}

	void setData(int data) {
		this->Tree->data = data;
	}

	void MakeLeftSubTree(Node *tree) {
		if (this->Tree->left == nullptr) {
			this->Tree->left = tree;
		}

	}

	void MakeRightSubTree(Node *tree) {
		if (this->Tree->right == nullptr) {
			this->Tree->right = tree;
		}
	}
};

Node* getLeftSubTree(Node* tree) {
	if (tree->left != nullptr)
		return tree->left;
}

Node* getRightSubTree(Node* tree) {
	if (tree->right != nullptr)
		return tree->right;
}

int getData(Node* tree) {
	return tree->data;
}

void preorder(struct Node* node) {   //전위 순회
	if (node == NULL) return;
	cout << node->data << "->";
	preorder(node->left);
	preorder(node->right);
}

void inorder(struct Node* node) {   //중위 순회
	if (node == NULL) return;
	inorder(node->left);
	cout << node->data << "->";
	inorder(node->right);
}

void postorder(struct Node* node) {   //후위 순회
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	cout << node->data << "->";
}



int main() {
	BinaryTree At;
	BinaryTree Bt;
	BinaryTree Ct;
	BinaryTree Dt;
    
	At.setData(1);
	Bt.setData(2);
	Ct.setData(3);
	Dt.setData(4);
    
	At.MakeLeftSubTree(Bt.Tree);                //  A(1)
	At.MakeRightSubTree(Ct.Tree);              //  B(2) C(3)
	Bt.MakeLeftSubTree(Dt.Tree);              //  D(4)      
    
	cout << getData(getLeftSubTree(At.Tree)) << endl;  //At트리의 왼쪽 2출력
	cout << getData(getLeftSubTree(getLeftSubTree(At.Tree)));  //Bt트리의 왼쪽 4출력
    
    
	preorder(At.Tree);
	cout << '\n';
	inorder(At.Tree);
	cout << '\n';
	postorder(At.Tree);

}

 

트리 순회 설명

 

 

 

 

 

 

 

 

 

 

 

 

 

• 전위 순회: 루트 노드를 먼저 탐색하고, 자식노드를 탐색하는 방식이다.

preorder traversal: A  -> B  -> D  -> E -> C

void preorder(struct Node* node) {    //전위 순회
	if (node == NULL) return;
	cout << node->data << "->";
	preorder(node->left);
	preorder(node->right);
}

 

 

• 중위 순회:  왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고 오른쪽 자식 노드를 탐색하는 방법이다.

preorder traversal: D -> B  -> E  -> A -> C

void inorder(struct Node* node) {     //중위 순회
	if (node == NULL) return;
	inorder(node->left);
	cout << node->data << "->";
	inorder(node->right);
}

 

 

• 후위 순회: 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.

preorder traversal: D -> E  -> B  -> C -> A

void postorder(struct Node* node) {    //후위 순회
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	cout << node->data << "->";
}

 

인접리스트로 트리순회 구현하기

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;

vector<int> adj[1004];
int visit[1004];

void postOrder(int here) {
	if (visit[here] == 0) {
		if (adj[here].size() == 1)
			postOrder(adj[here][0]);
		if (adj[here].size() == 2) {
			postOrder(adj[here][0]);
			postOrder(adj[here][1]);
		}
		visit[here] = 1;
		cout << here << " ";
	}
}

void preOrder(int here) {
	if (visit[here] == 0) {
		visit[here] = 1;
		cout << here << " ";
		if (adj[here].size() == 1)
			preOrder(adj[here][0]);
		if (adj[here].size() == 2) {
			preOrder(adj[here][0]);
			preOrder(adj[here][1]);
		}

	}
}

void inOrder(int here) {
	if (visit[here] == 0) {
		if (adj[here].size() == 1) {
			inOrder(adj[here][0]);
			visit[here] = 1;
			cout << here << " ";
		}
		else if (adj[here].size() == 2) {
			inOrder(adj[here][0]);
			visit[here] = 1;
			cout << here << " ";
			inOrder(adj[here][1]);
		}
		else {
			visit[here] = 1;
			cout << here << " ";
		}

	}
}



int main() {
	adj[1].push_back(2);
	adj[1].push_back(3);
	adj[2].push_back(4);
	adj[2].push_back(5);
	adj[3].push_back(6);
	adj[3].push_back(7);
	//preOrder(1);
	inOrder(1);

}
/*

*/

 

 

참고

https://www.jiwon.me/binary-tree-traversal/

이진 트리 순회: 전위, 중위, 후위, 레벨