Data Structure & Algorithms/Trees and Graphs13 [Tree] 기초 inorder traverse 구현 및 이해 코드 레벨로 내려가서 차근차근 짚고 넘어가는데 c++ 기초가 부실한게 여실히 나타난다. 하나하나 두들기면서 배울수밖에. 할수있다. 코딩도 수학 같이 아는것과 모르는것을 구분하는것이 정말 중요한듯. //creat a tree #include using namespace std; //structure of the binary tree struct treenode { //member int info; struct treenode *left , *right; // }; //Function to create the binary tree struct treenode* create(){ int data; struct treenode* tree; //Dynamically allocating memory //for tr.. 2023. 1. 20. [Graphs] BFS vs DFS 비교하기 유명한 Breath First Search 와 Depth First Search 비교해보자. 이 두 알고리즘은 트리 구조에서 어떻게 데이터를 순회하는 방법에대한 차이를 나타낸다 . DFS 는 먼저 깊게 왼쪽 트리부터 파고들어서 순차적으로 찾는것이고 BFS는 LEVEL (층)을 나눈다면 똑같은 층으로 옆 노드로 옮겨다니며 원하는 정보를 찾는 형태이다. 아래 GIF가 잘 설명해준다! DFS와 BFS를 표로 분석해보면 아래와 같다. Traversal order Depth Level Data structure Used Stack Queue Time Complexity O(V + E) O(V + E) Space Complexity O(V) O(V) Traversal tree Narrow and long Wide .. 2023. 1. 18. [Tree][leetcode] 트리 개념 재정리 with GIF. 릿코드로 다시 data structure 와 algorithms 강의를 하루에 하나씩 듣고있는데 트리부분에 도착하였다! 이번에는 담담히 넘어가보자. 갈 길이 아직멀다... 면접에서 가장 흔하게 나온다는 tree 구조! binary tree를 많이 사용하는데 이는 root(꼭대기 부터 2가지고 갈라져 나오기때문). 구조는 linked list에서 다뤘던것처럼 포인터가 다른 노드를 가르키고 있으며 여기서는 children 을 가르킨다고 한다. (parent 노드는 2개의 childeren 노드를 가지고있다) 트리 구조는 일상생활에서 많이 사용되는데 :: 등이있다 File system A comment thread on an app like Reddit or Twitter A company's organiza.. 2023. 1. 14. [DS] chapter8 트리 -2 [08-3] 이진 트리의 순회 (Traversal) 순회가 필요한 이유는 삭제할 서브트리가 2개라면 한번의 free함수 호출이 전부이므로 메모리 누수로 이어질수있다. 순회의 종류: - 전위 순회( Preorder Traversal) - 중위 순회(Inorder Traversal) - 후위 순회( Postorder Traversal) - 높이가 2이상인 이진트리의 순회법 1단계 : 왼쪽 서브트리 순회 2단계: 루트노드의 방문 3단계: 오른쪽 서브 트리의 순회 void InorderTraverse(BTreeNode * bt) { InorderTraverse(bt->left); // 1단계 왼쪽 서브트리의 순회 printf("%d \n", bt ->data); // 2단계 루트 노드의 방문 (이게 방문으로~).. 2022. 7. 3. [DS]chapter8 트리 개념1 [8-1] 트리의 개요 트리를 이용하여 무엇인가를 저장하고 꺼내야한다는 생각은 지운다! 대신 무엇인가를 표현하는 도구라 생각! *무언가 네트워크 처럼 생겼네. 노드도 있고 간선도 있고.. 이진트리(Binary Tree) 와 서브트리(Sub Tree) - 이진 트리의 조건(*Binary니까 두개가 까지) 1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다. 2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. (*하나만 트리가 있어도 이진트리! 노드가 존재하지않는다면 공집합 노드가 존재한다고 판단한데) 포화이진트리(Full Binary Tree) 와 완전 이진 트리 (Complete Binary Tree) 포화이진 트리 : 모든 레벨이 꽉 찬 이진 트리 완전이진 트리 : 포화 이진 트리 처럼 .. 2022. 7. 1. 이전 1 2 다음
