tree

package
v0.0.0-...-f6cfca9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 1, 2022 License: MIT Imports: 2 Imported by: 0

README

Binary Tree

A binary tree is a tree where each node has 0, 1, or 2 children. This is a binary tree:

A binary tree

The child nodes are usually called the left child and the right child. If a node doesn't have any children, it's called a leaf node. The root is the node at the very top of the tree (programmers like their trees upside down).

Often nodes will have a link back to their parent but this is not strictly necessary.

Binary trees are often used as binary search trees. In that case, the nodes must be in a specific order (smaller values on the left, larger values on the right). But this is not a requirement for all binary trees.

For example, here is a binary tree that represents a sequence of arithmetical operations, (5 * (a - 10)) + (-4 * (3 / b)):

A binary tree

The code

Here's how you could implement a general-purpose binary tree in Swift:

public indirect enum BinaryTree<T> {
  case node(BinaryTree<T>, T, BinaryTree<T>)
  case empty
}

As an example of how to use this, let's build that tree of arithmetic operations:

// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)

You need to build up the tree in reverse, starting with the leaf nodes and working your way up to the top.

It will be useful to add a description method so you can print the tree:

extension BinaryTree: CustomStringConvertible {
  public var description: String {
    switch self {
    case let .node(left, value, right):
      return "value: \(value), left = [\(left.description)], right = [\(right.description)]"
    case .empty:
      return ""
    }
  }
}

If you print(tree) you should see something like this:

value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

With a bit of imagination, you can see the tree structure. ;-) It helps if you indent it:

value: +, 
	left = [value: *, 
		left = [value: 5, left = [], right = []], 
		right = [value: -, 
			left = [value: a, left = [], right = []], 
			right = [value: 10, left = [], right = []]]], 
	right = [value: *, 
		left = [value: -, 
			left = [], 
			right = [value: 4, left = [], right = []]], 
		right = [value: /, 
			left = [value: 3, left = [], right = []], 
			right = [value: b, left = [], right = []]]]

Another useful method is counting the number of nodes in the tree:

  public var count: Int {
    switch self {
    case let .node(left, _, right):
      return left.count + 1 + right.count
    case .empty:
      return 0
    }
  }

On the tree from the example, tree.count should be 12.

Something you often need to do with trees is traverse them, i.e. look at all the nodes in some order. There are three ways to traverse a binary tree:

  1. In-order (or depth-first): first look at the left child of a node, then at the node itself, and finally at its right child.
  2. Pre-order: first look at a node, then at its left and right children.
  3. Post-order: first look at the left and right children and process the node itself last.

Here is how you'd implement that:

  public func traverseInOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traverseInOrder(process: process)
      process(value)
      right.traverseInOrder(process: process)
    }
  }
  
  public func traversePreOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      process(value)
      left.traversePreOrder(process: process)
      right.traversePreOrder(process: process)
    }
  }
  
  public func traversePostOrder(process: (T) -> Void) {
    if case let .node(left, value, right) = self {
      left.traversePostOrder(process: process)
      right.traversePostOrder(process: process)
      process(value)
    }
  }

As is common when working with tree structures, these functions call themselves recursively.

For example, if you traverse the tree of arithmetic operations in post-order, you'll see the values in this order:

5
a
10
-
*
4
-
3
b
/
*
+

The leaves appear first. The root node appears last.

You can use a stack machine to evaluate these expressions, something like the following pseudocode:

tree.traversePostOrder { s in 
  switch s {
  case this is a numeric literal, such as 5:
    push it onto the stack
  case this is a variable name, such as a:
    look up the value of a and push it onto the stack
  case this is an operator, such as *:
    pop the two top-most items off the stack, multiply them,
    and push the result back onto the stack
  }
  the result is in the top-most item on the stack
}

Written for Swift Algorithm Club by Matthijs Hollemans

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func EqualTree 

func EqualTree[T constraints.Ordered](p, q *BinaryTree[T]) bool

Public Static Function that comapres two nodes and returns True if they're equal. False otherwise.

Types

type BinaryTree 

type BinaryTree[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Binary Tree Struct

func BinaryTreeInit 

func BinaryTreeInit[T constraints.Ordered](values ...T) *BinaryTree[T]

Constructor Function to return a new Binary Tree.

func (*BinaryTree[T]) Count 

func (self *BinaryTree[T]) Count() int

Method to return the distance of node to it's lowest leaf. Runs in O(h) time.

func (*BinaryTree[T]) Height 

func (BT *BinaryTree[T]) Height() int

Method to return the largest # of edges in a path from the tree's root to a leaf node.

func (*BinaryTree[T]) Invert 

func (BT *BinaryTree[T]) Invert()

Method to Invert tree.

func (*BinaryTree[T]) IsEmpty 

func (self *BinaryTree[T]) IsEmpty() bool

Method to return True if tree is currently empty (rootless). False otherwise.

func (*BinaryTree[T]) TranverseInOrder 

func (BT *BinaryTree[T]) TranverseInOrder(process func(T))

Method to Iterate node in inorder order (left, node, right).

func (*BinaryTree[T]) TranverseLevelOrder 

func (BT *BinaryTree[T]) TranverseLevelOrder(process func(T))

Method to Iterate node in postorder order (left, right, node).

func (*BinaryTree[T]) TranversePostOrder 

func (BT *BinaryTree[T]) TranversePostOrder(process func(T))

Method to Iterate node in postorder order (left, right, node).

func (*BinaryTree[T]) TranversePreOrder 

func (BT *BinaryTree[T]) TranversePreOrder(process func(T))

Method to Iterate tree in preorder order (node, left, right).

type BinaryTreeNode 

type BinaryTreeNode[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Binary Tree's Node Struct

func (*BinaryTreeNode[T]) Count 

func (self *BinaryTreeNode[T]) Count() int

Method to return number of subnodes. Runs in O(n) time.

func (*BinaryTreeNode[T]) Depth 

func (self *BinaryTreeNode[T]) Depth() int

Method to return the distance of node from the root. Runs in O(h) time.

func (*BinaryTreeNode[T]) HasAnyChildren 

func (self *BinaryTreeNode[T]) HasAnyChildren() bool

Method to return True if node Has a left or right child (if HasLeftChild || HasRightChild). False if otherwise.

func (*BinaryTreeNode[T]) HasBothChildren 

func (self *BinaryTreeNode[T]) HasBothChildren() bool

Method to return True if node Has both children (if HasLeftChild && HasRightChild). False if otherwise.

func (*BinaryTreeNode[T]) HasLeftChild 

func (self *BinaryTreeNode[T]) HasLeftChild() bool

Method to return True if node Has a left child (if node.left != nil). False if otherwise.

func (*BinaryTreeNode[T]) HasRightChild 

func (self *BinaryTreeNode[T]) HasRightChild() bool

Method to return True if node Has a right child (if node.right != nil). False if otherwise.

func (*BinaryTreeNode[T]) Height 

func (self *BinaryTreeNode[T]) Height() int

Method to return the distance of node to it's lowest leaf. Runs in O(h) time.

func (*BinaryTreeNode[T]) Invert 

func (self *BinaryTreeNode[T]) Invert()

Method to reverse node (left, node, right) -> (right, node, left)

func (*BinaryTreeNode[T]) IsLeaf 

func (self *BinaryTreeNode[T]) IsLeaf() bool

Method to return True if node is a leaf node (Has no left or right). False if otherwise.

func (*BinaryTreeNode[T]) IsLeftChild 

func (self *BinaryTreeNode[T]) IsLeftChild() bool

Method to return True if node is a left child (if parent.left == node). False if otherwise.

func (*BinaryTreeNode[T]) IsRightChild 

func (self *BinaryTreeNode[T]) IsRightChild() bool

Method to return True if node is a right child (if parent.right == node). False if otherwise.

func (*BinaryTreeNode[T]) IsRoot 

func (self *BinaryTreeNode[T]) IsRoot() bool

Method to return True if node is root (Has no parent node). False otherwise.

func (*BinaryTreeNode[T]) IterInOrder 

func (self *BinaryTreeNode[T]) IterInOrder(process func(T))

Method to Iterate node in inorder order (left, node, right)

func (*BinaryTreeNode[T]) IterPostOrder 

func (self *BinaryTreeNode[T]) IterPostOrder(process func(T))

Method to Iterate node in postorder order (left, right, node)

func (*BinaryTreeNode[T]) IterPreOrder 

func (self *BinaryTreeNode[T]) IterPreOrder(process func(T))

Method to Iterate node in preorder order (node, left, right)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.