Tree

08 Jul 2023 in Study / Computer science on Tree

Data Structure, 이것이 자료구조+알고리즘이다 with C언어 (reference)

• a kind of Graph
• Node (N) + Edge (N-1)
• hierarchy : no cycle (Only Top → Bottom or Bottom → Top)
• From root (only one) to specific node, there is only one path
• For all of nodes except root node, it has only one parent node
• A specific node can be a root node for subtree

Words

• Root node
• Parent node
• Child node
• Leaf node : has no child node
• Internal node : node which is not leaf node
• Sibling nodes : have same parent node
• Level (for a specific node) : the number of nodes while searching from root to specific node (root node : level 0)
• Height (for a tree) : maximum level
• Degree (for a specific node) : the number of subtrees whose root nodes are child nodes of a specific node
• Degree of tree (for a tree) : maximum degree
• Depth (for a specific node): From root to a specific node, the number of edges
• Size (for a specific node) : 1 (self) + the number of child nodes

Notation for Tree

• Method 1
  • Nested Parenthesis
    • (A(B((D)(E))(C(F))) (previous tree example)
• Method 2

  • Indentation

    
    

    A
    +--B     +-- represents this is a child node
        +--D
        +--E
    +--C
        +--F
    

Notation for Node

• N-Link notation
  • Each node includes the list for the child node
  • When we use the language like C, it gonna be uncomfortable if the degree of each node is different
• Left Child-Right Sibling notation
  • Condition: The tree’s node has to be added from left to right (For previous tree example, F has to be left-child of C)
  • Each node includes only left child node and right sibling -> It is possible to include all of nodes

  
  

                A
             ↙
           B    →   C
        ↙        ↙
      D  → E    F
  

Implementation with C

• Use Indentation method for printing the tree
• Use Left Child-Right Sibling notation for notation of node
• Struct node

typedef struct treenode
{
  struct treenode* LeftChild;
  struct treenode* RightSibling;

  int data;
} TreeNode;

• Create node

void createTreeNode(TreeNode** node, int data)
{
  *node = (TreeNode*)malloc(sizeof(TreeNode));
  (*node)->LeftChild = NULL;
  (*node)->RightSibling = NULL;
  (*node)->data = data;
}

• Destroy node

void destroyTreeNode(TreeNode** node)
{
  free(*node);
  *node = NULL;
}

• Add node to tree

void addTreeNode(TreeNode* parent, TreeNode* child)
{
  if (parent->LeftChild == NULL)
  {
    parent->LeftChild = child;
  }
  else
  {
    TreeNode* currentNode = parent->LeftChild;
    while (currentNode->RightSibling != NULL)
    {
      currentNode = currentNode->RightSibling;
    }
    currentNode->RightSibling = child;
  }
}

• print the tree

// depth starts 0
void printTree(TreeNode* node, int depth)
{
  for (int i = 0; i < depth - 1; i++)
    printf("   ");

  if (depth > 0)
    printf("+--");

  printf("%d\n", node->data);

  if (node->LeftChild != NULL)
    printTree(node->LeftChild, depth + 1);
  if (node->RightSibling != NULL)
    printTree(node->RightSibling, depth);
}

Implementation with Python

class Node:
  def __init__(self, data = None):
    self.data = data
    self.child = {}      # dictionary (key == data, value == Node for data)
                        # Based on the situation, list can be used
                        # Left Child-Right Sibling notation can used as well

class Tree:
  def __init__(self, node):
    self.root = node

  # various method can be implemented

• Because tree is also graph, it can be also implemented by Adjacency matrix or Adjacency list

Binary Tree

• Degree of all nodes <= 2
• It contributes to the searching algorithm
• Binary Search Tree
  • All of nodes have their value
  • all nodes of one node’s left-subtree <= one node <= all nodes of one node’s right-subtree
• Full Binary Tree : All internal nodes have 2 child nodes
• Perfect Binary Tree : Depth of all leaf nodes has same value
• Complete Binary Tree : All nodes have 2 child nodes except for nodes of last level (They may have only left-child node or 2 child nodes)
• Height Balanced Tree: The difference between the height of root’s left-subtree and that of root’s right-subtree is less than 2
• Completely Height Balanced Tree: The height of root’s left-subtree is the same with that of root’s right-subtree

Implementation for Binary Tree with Python

class Node:
  def __init__(self, data = None):
    self.data = data
    self.left = None
    self.right = None

class BinaryTree:
  def __init__(self, node):
    self.root = node

  # various method can be implemented

• Because tree is also graph, it can be also implemented by Adjacency matrix or Adjacency list

Search for Binary Tree with Python

• method 1 : BFS
  

from collections import deque

class Node:
  def __init__(self, data = None):
    self.data = data
    self.child = []

class Tree:
  def __init__(self, node):
    self.root = node

def BFS(tree):
  visited = []
  need_visit = deque()
  need_visit.append(tree.root)

  while need_visit:
    node = need_visit.popleft()
    print(node.data)
    visited.append(node)

    for child in node.child:
      if child not in visited:
        need_visit.append(child)

• method 2 : DFS
  • Use recursion
  • PreOrder : Root → Left → Right (A, B, D, E, C, F)
  • InOrder : Left → Root → Right (D, B, E, A, C, F)
  • PostOrder : Left → Right → Root (D, E, B, F, C, A)

class Node:
  def __init__(self, data = None):
    self.data = data
    self.left = None
    self.right = None

  def preOrder(self, root_node):
    if root_node == None:
      return
    print(root_node.data)
    preOrder(root_node.left)
    preOrder(root_node.right)  

  def inOrder(self, root_node):
    if root_node == None:
      return

    inOrder(root_node.left)
    print(root_node.data)
    inOrder(root_node.right)

  def postOrder(self, root_node):
    if root_node == None:
      return

    postOrder(root_node.left)
    postOrder(root_node.right)
    print(root_node.data)

Implementation for Binary Tree with C

• struct node

typedef struct treenode
{
  struct treenode* LeftChild;
  struct treenode* RightChild;

  int data;
} TreeNode;

• create node

void createTreeNode(TreeNode** node, int data)
{
  *node = (TreeNode*)malloc(sizeof(TreeNode));
  (*node)->LeftChild = NULL;
  (*node)->RightChild = NULL;
  (*node)->data = data;
}

• destroy node

void destroyTreeNode(TreeNode** node)
{
  free(*node);
  *node = NULL;
}

• add node
  • There are multiple ways
  • Example) LeftChild -> RightChild

void addTreeNode(TreeNode* parent, TreeNode* child)
{
    if (parent->LeftChild == NULL)
    {
        parent->LeftChild = child;
    }
    else if (parent->RightChild == NULL)
    {
        parent->RightChild = child;
    }
}

Search for Binary Tree with C

• method 1 : BFS
• method 2 : DFS
  • Use recursion
  • PreOrder : Root → Left → Right (A, B, D, E, C, F)
  • InOrder : Left → Root → Right (D, B, E, A, C, F)
  • PostOrder : Left → Right → Root (D, E, B, F, C, A)
    • When we destroy the tree node, we need to destroy the child node at first
    • Consequently, we use PostOrder for destroying the tree

  
  

  void preOrderTree(TreeNode* node)
  {
    if (node == NULL)
      return;
  
    printf("%d\n", node->data);
    preOrderTree(node->LeftChild);
    preOrderTree(node->RightChild);
  }
  
  void inOrderTree(TreeNode* node)
  {
    if (node == NULL)
      return;
  
    inOrderTree(node->LeftChild);
    printf("%d\n", node->data);
    inOrderTree(node->RightChild);
  }
  
  void postOrderTree(TreeNode* node)
  {
    if (node == NULL)
      return;
  
    postOrderTree(node->LeftChild);
    postOrderTree(node->RightChild);
    printf("%d\n", node->data);
  }
  
  void destroyTree(TreeNode** node)
  {
    if (node == NULL)
      return;
  
    destroyTree(&(node->LeftChild));
    destroyTree(&(node->RightChild));
    free(*node);
    *node = NULL;
  }
  

Reference

blog
blog