JavaScript를 사용한 기본 데이터 구조 - 이진 트리 - 1부🚀
* 🤓 INTRODUCTION
* 📜 DEFINITION
* 👨🏻🔬 OPERATIONS
* 🏃🏻♀️ TRAVERSAL EXPLANATION
* 🙏 THANK YOU
🤓 소개
Welcome, my dear hackers!🚀 Welcome to yet another blog article about elementary data structures.
If you missed the previous article where we describe the Linked Lists and write pseudocode, you can check it out here:
더 이상 사용할 수 없는 기사
Today, we are going to start a three-part article about Binary Tree data structure. We will talk a bit about theoretical stuff because it will make sense of all the implementation that we will do using the JavaScript programming language. As you may know, data structures are not specific to any programming language, so you are free to use any other programming language of your choice.
Please feel free to connect with me via , or
Let's start our journey!📜 정의
Binary tree is an ordered "tree" where each node has two "children" nodes at most.
- Right child and Left child
A subtree of some node N is called the left and right subtrees, and the node N is their parent. This is also known as the Knut's binary tree.
A Strict binary tree is a binary tree where each node has 0 or 2 subtrees.
Complete binary tree is a strict binary tree of a height h where all the leaves are at the level h.
A Leaf is a node that has no children nodes.
A total number of nodes in a complete binary tree of height h is:
- n=2h+1 - 1
A height of a tree made up of n nodes is:
h = log2(n+1)-1
An almost complete binary tree is a tree where all of the levels, except the last one, filled out entirely.
A balanced tree is a tree where the height of the left and right subtree differs only by one.
👨🏻🔬 운영
Primitive operations
- 📄 Get the content of the node N
- 👈🏻 Get the left child of the node N
- 👉🏻 Get the right child of the node N
- 👪Get the parent node of the node N
- 🧒🏻👶🏻 Get the sibling node of the node N
- ➡Check if the node N is a right child
- ⬅Check if the node N is a left child
Composite operations
- 🏃🏻♀️ Binary tree traversal
- 🌎Creating the binary tree
- 📥Insert into a binary tree
- ❌Delete a node from the binary tree
- 🔎Search an element in the binary tree
- 🔁Merging two binary trees
🏃🏻♀️ 순회 설명
There are a couple of ways to traverse a tree:
PREORDER
- Process the root node
- Traverse the left subtree
- Traverse the right subtree
POSTORDER
- Traverse the left subtree
- Traverse the right subtree
- Process the root node
IN-ORDER
- Traverse the left subtree
- Process the root node
- Traverse the right subtree
BY LEVEL TRAVERSAL
- Traverse all of the nodes by levels, starting from the node 0 a.k.a. the root node.
We will write minimal pseudocode for our traversal algorithms:
선주문 순회
1 preOrder(root):
2 visit(root) //print out the content
3 preOrder(left(root))
4 preOrder(right(root))
5 exit procedure
사후 순회
1 postOrder(root):
2 postOrder(left(root))
3 postOrder(right(root))
4 visit(root)
5 exit procedure
순회 순회
1 inOrder(root):
2 inOrder(left(root))
3 visit(root)
4 inOrder(right(root))
5 exit procedure
레벨 순회 기준
//for this purpose we need to use the helper - the queue data //structure
1 levelOrderN(info, left_link, right_link, root)
2 pointer => root
3 while (pointer not equal to null)
4 visit(pointer)
5 //add all of the descendants into a FIFO queue
6 queue_enqueue(left(pointer))
7 queue_enqueue(right(pointer))
8 //read from a queue
9 pointer => queue_dequeue()
10 //if the queue is empty dequeue returns null
11 endwhile
12 exit procedure
🙏 읽어주셔서 감사합니다!
We are taking baby steps! The binary trees are a bit more complex data structure, so we would need to break this article in order for you (and me 😆) to not freak out. Stay tuned for the next chapter of this article!
References:
School notes...
School books...
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
☕ SUPPORT ME AND KEEP ME FOCUSED!
즐거운 해킹 시간 되세요! 😊
Reference
이 문제에 관하여(JavaScript를 사용한 기본 데이터 구조 - 이진 트리 - 1부🚀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/devlazar/elementary-data-structures-with-javascript-binary-trees-part-1-gog
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
School notes...
School books...
Reference
이 문제에 관하여(JavaScript를 사용한 기본 데이터 구조 - 이진 트리 - 1부🚀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/devlazar/elementary-data-structures-with-javascript-binary-trees-part-1-gog텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)