Trees, binary trees, threaded binary trees, heap

hierarchical structure

Trees and Binary trees

A tree is finite set of one or more nodes such that there is a root and remaining nodes are partitioned into disjoint trees. It’s hierarchical structure.

Degree of a tree: the maximum degree of the nodes in the tree

Leaf node: a node withe degree zero

several types of trees

A binary tree is a finite set of nodes such that empty or consists of root node and two disjoint binary trees, called, left subtree and right subtree.

There are 3 types of binary trees

1. Full binary tree : a binary tree of depth k(≥0) having 2^k-1 nodes
2. Complete binary tree : a binary tree with n nodes that correspond to the nodes numbered from 1 to n in the full binary tree of depth k
3. Skewed binary tree

<Properties of binary trees>

• empty node is possible
• the order of subtree are important
• a binary tree is not a subset of a tree
• maximum number of nodes in a binary tree 2^k-1 where k: depth of the tree
• relationship between the number of leaf nodes(n0) and the number of nodes with degree 2(n2) => n0 = n2 + 1
• binary tree is hard to represent it by using array
• usually use linked list

Binary tree traversal

Traversal is to visit each node in the tree exactly once and it produces a linear order for the information in a tree.

• inorder (LVR)
• preorder (VLR)
• postorder (LRV)

What else?

finding the inorder successor of a node

insertion into a max heap

deletion from a max heap

If you want to see a min-heap case? 👩🏻‍💻 https://github.com/jyuunnii/Data-Structure