• Later half, we’ll learn Non-Linear Data Structure.

A tree and its components

• A tree is a hierarchical nonlinear data structure which composes of nodes and branches
• The root is the node at the top of the hierarchy. (เอาต้นไม้มาพลิกกลับด้าน)
  
• The leaf node is the node that has no branch leaving from it

Indegree, Outdegree, and Degree

• The indegree of a node is the number of branches that point inward to it.
  • Number of arrow ที่ point ไปยัง Node นั้น ๆ
• The outdegree of a node is the number of branches that point outward from it.
  • Number of arrow ที่ point ออกจาก Node นั้น ๆ
• The degree of a node is equal to its indegree plus its outdegree.
  • เอา Indegree บวกกับ Outdegree
• The maximum indegree of a tree is the highest indegree among all nodes.
  • ก็ดูว่า Node ไหนมี Indegree มากสุด เปรียบเทียบกับทั้ง Tree
• The maximum outdegree of a tree is the highest outdegree among all nodes.

Parent, Child, Leaf

• A parent node is a node with a nonzero outdegree. (แปลว่ามีต่อไปข้างล่าง)
• A child node is a node with a nonzero indegree.
• A leaf node is a node that has no children; its outdegree is zero.
• A root is a node with a zero indegree.

Level and Height

• The level (L) of a node in a tree is the distance from the root to that node.
  • Concept คล้าย ๆ Array ที่เริ่มจาก 0
• The height (H) of a node in a tree is the number of levels of that node plus 1.
• A tree of size $n$ has a height of at most $n$.
  
• A tree of size $n$ has a height of at least $2$.
  

A subtree

• A subtree of a tree is a smaller tree that is part of the larger tree.
  
  The tree on the right is the subtree of the tree on the left

Binary Tree (BT)

A binary tree (BT) is a tree in which ==each node has at most two children.==

• The left subtree of a BT is the subset of the BT that contains all nodes and branches from the left side of the BT.
• The concept of the right subtree of a BT is similar.
  

Balance Factor

• ย้ำอีกครั้งว่า A binary tree (BT) is a tree in which each node has at most two children.
• The balance factor ($B$) of a node is the difference between the height of its left subtree $(H_L)$ and the height of its right subtree ($H_R$), i.e. $B = H_L - H_R$
• A BT is balanced if the absolute balance factor ($|B|$) of every node in the tree is either 0 or 1

Height of a Binary Tree

• A binary tree of size $n$ has the height at most $n$
  • A BT with one node per each level.
    
• A binary tree of size $n$ has the height at least $\lceil(\log_2(n+1))\rceil$
  • สูตรนี้ได้มาจากการคำนวณ $S(n)$ นั่นแหละ ไม่มีไรมากก จำไปเลย!
    

Complete, Nearly Complete

• A BT tree is complete or ==full if and only if every level is full.==
• A BT tree is nearly complete if and only if all levels, excepts the last, are full, and the elements in the last level are filled consecutively from left to right.
• The height of a complete or nearly complete BT of size n is $\lceil(\log_2(n+1))\rceil$

Binary Tree Application

1. Expression Tree

• มาจาก Infix ใน 07 Stack and its Applications

เวลา Pop-out ให้อันที่อยู่ข้างบนไว้ขวามือนะ!

• แยกออกเป็น 2 Stack: Tree กับ Operator

2. Huffman Coding

• Huffman coding was invented by David Huffman.
• It is used for file compression.
• It saves space compared to fixed-length encoding by using short codeword strings to encode high-frequency characters and long codeword strings to encode low-frequency characters.
• The Huffman code is used to assign variable bit lengths to each character based on its frequency of appearance.
• A character that appears more often is assigned a shorter bit length compared to other characters.

Steps

1. เขียน Frequency ของแต่ละตัวอักษรที่ปรากฎอยู่ในคำ (ขั้นตอนนี้นับดี ๆ)
2. บรรทัดล่างสุด เรียง Frequency ของแต่ละตัว จาก (มาก → น้อย, ซ้าย → ขวา) — ไม่ต้องห่วงเรื่องการเรียงตัวหนังสือที่เท่ากัน เพราะแต่ละคนจะเรียงไม่เหมือนกันอยู่แล้ว
3. แล้วก็ Construct ออกมาได้เลย

3. Visiting Nodes in a tree (Searching)

• อันนี้มันไม่ใช่ Linear แล้ว ดังนั้นการจะ Search มันก็จะยากขึ้น ดังนั้นเราจะ Collapse Tree ให้เป็น Linear-ich??

Binary Tree Traversal

• Tree traversal is useful for listing out data or to visit nodes in the tree
• The traversal can also be used for searching for a specific element
• Five ways to visit nodes in tree
  • Traverse nodes according to the order of the root, its left node, and its right node
    • Inorder traversal: left root right
    • Postorder traversal: left right root
    • Preorder traversal: root left right

    ไอ่ตัวบอกตำแหน่งเนี่ยให้ focus ที่ root— in ก็หมายถึง “middle” ดังนั้น root ก็อยู่ตรงกลาง แล้วที่เหลือก็คือ left, right (ตามลำดับ)

  • Traverse nodes vertically/horizontally
    • Depth first traversal: visit nodes from top to the bottom.
    • Breadth first traversal: visit nodes level by level

Pre-order

• Base case of recursive preorder: Preorder of a tree with size 1 (or just a tree with a single node) → print ตัวนั้น ๆ ออกมาเลย
  

In-order

• The concepts of In-order traversal are similar
• Recursion can be used for implementation
  

Post-order

• The concepts of Post-order traversal are similar
• Recursion can be used for implementation
  

Depth First Traversal (DFT)

• Traverse the tree vertically, left subtree has higher priority than the right subtree (L > R)
• Note that the depth first traversal is as same as PRE-ORDER
• ต้องใช้ Stack to solve the problem
  • Create a stack S
  • Insert the root to S
  • Until S is empty
    • Pop and print the top element in S
    • If right child of the popped element exists, push it to S (เอา right ก่อนเสมอ!)
    • If left child of the popped element exists, push it to S

pop print push

Breadth First Traversal (BFT)

• Traverse the tree horizontally level by level (each layer), from top to bottom, from and left to right
• ต้องใช้ Queue to solve the problem
  • Create a queue Q
  • Insert the root to Q
  • Until Q is empty
    • dequeue and print the front element of Q
    • enqueue left and right children of the dequeued element to Q (เวลา enqueue ซ้าย ไป ขวา ตามที่เราเห็นเลย)

dequeue print enqueue

4. Binary Tree Representation (in Java)