Binary Trees

...

https://talks.obedmr.com/

What is a tree?

  • It's a hierarchical data structure.
  • The relationship between elements is one-to-many.
  • One natural way to define a tree is recursively.
  • A tree is a collection of nodes.
  • A tree consists of a distinguished node, , called the root, and zero or more nonempty (sub)trees , each of whose roots are connected by a directed edge from .
  • The root of each subtree is said to be a child of , and is the parent of each subtree root.
  • Nodes with no children are known as leaves; the leaves in the tree below are . Nodes with the same parent are siblings; thus, are all siblings.
  • Grandparent and grandchild relations can be defined in a similar manner.
  • A path from node to is defined as a sequence of nodes such that ni is the parent of for .
  • The length of this path is the number of edges on the path, namely, . There is a path of length zero from every node to itself.
  • For any node ni, the depth of is the length of the unique path from the root to . Thus, the root is at depth .
  • The height of is the length of the longest path from to a leaf. Thus all leaves are at height .

Implementation of a tree

struct TreeNode {
  Object element;
  TreeNode *firstChild;
  TreeNode *nextSibling;
};

Binary Trees

A binary tree is a tree in which no node can have more than two children.

Binary Search Trees

  • An important application of binary trees is their use in searching.

  • The property that makes a binary tree into a binary search tree is that for every node, , in the tree:

    • the values of all the items in its left subtree are smaller than the item in ,
    • and the values of all the items in its right subtree are larger than the item in .

Binary Search Tree: Node

struct Node {
    int key;
    Node* left;
    Node* right;
    Node(int item) {
        key = item;
        left = NULL;
        right = NULL;
    }
};

Source Code: binary_tree.cpp

TBD

Resources and Credits

This material is genereated thanks to some extracts from following resources:

  • Weiss, Mark Allen. Data Structures and Algorithm Analysis in C++. 4th ed. Boston: Pearson, 2014.
  • Humberto González, Luis. Abstraccion de Datos
  • Erickson, Jeff. Algorithms ...
  • Google-generated code with AI Overview

Thanks