BinaryTrees 1.04

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

BinaryTrees is a package for generating, visualizing, and manipulating binary trees.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

To use BinaryTrees, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<BinaryTrees`

Representing trees

A rooted, ordered tree is represented by an expression in which each vertex corresponds to a list containing its children.  For example, here is a 5-leaf binary tree:

{{{},{}},{{{},{}},{}}}

The Wolfram Language symbol TreeForm displays expressions graphically.  BareTreeForm uses TreeForm to draw trees without vertex labels:

BareTreeForm[{{{},{}},{{{},{}},{}}}]

BinaryTrees gives a list of all binary trees with a fixed number of leaves.

BinaryTrees[4]
BareTreeForm/@%

Trees gives a list of all trees with a fixed number of vertices.

Trees[4]
BareTreeForm/@%

Rooted binary trees with n leaves are in bijection to general rooted trees with n vertices, via BinaryTree and its inverse, FromBinaryTree.

BareTreeForm/@BinaryTree/@Trees[4]
BareTreeForm/@FromBinaryTree/@BinaryTrees[4]

Trees with n vertices are also in bijection to Dyck words of length 2(n-1):

DyckWord/@Trees[4]
BareTreeForm/@FromDyckWord/@DyckWords[3]

Families of trees

Several particular families of trees are implemented.

A path tree is a binary tree in which at most one vertex on each level has children of its own.  PathTrees gives the n-leaf path trees:

BareTreeForm/@PathTrees[6]

Since at each step we have the choice of the left vertex or right vertex having children, there are (2^(n-2)) n-leaf path trees, and we can encode a path tree as a binary (n-2)-tuple.  PathTree constructs a path tree from a list of zeros and ones.

BareTreeForm[PathTree[{0,1,1,0,1,1,0}]]

FromPathTree constructs the binary tuple encoding a path tree.

FromPathTree[First[PathTrees[10]]]

The left comb tree is the path tree corresponding to {0,0,…,0}; the right comb tree is the path tree corresponding to {1,1,…,1}.

BareTreeForm[LeftCombTree[7]]
BareTreeForm[RightCombTree[7]]

LeftCrookedTree and RightCrookedTree give trees that alternate on each level.

BareTreeForm[LeftCrookedTree[7]]
BareTreeForm[RightCrookedTree[7]]

Package symbols

BareTreeForm

?BareTreeForm

BareTreeForm/@BinaryTrees[5]

The option LevelHeight can be used to adjust the size.

(BareTreeForm[#1,LevelHeight->20]&)/@BinaryTrees[5]

BinaryTree and FromBinaryTree

?BinaryTree

BinaryTree[Trees[5][[1]]]

?FromBinaryTree

FromBinaryTree[BinaryTrees[5][[1]]]

BinaryTreeQ

?BinaryTreeQ

BinaryTreeQ[{{},{}}]

Select[Trees[5],BinaryTreeQ]
BareTreeForm/@%

BinaryTrees

?BinaryTrees

BareTreeForm/@BinaryTrees[5]

CompleteBinaryTree

?CompleteBinaryTree

Table[BareTreeForm[CompleteBinaryTree[(2^n)]],{n,0,4}]

DyckWord and FromDyckWord

?DyckWord

DyckWord/@Trees[5]

?FromDyckWord

BareTreeForm/@FromDyckWord/@DyckWords[4]

DyckWordQ

?DyckWordQ

DyckWordQ["0110"]

DyckWordQ["0101"]

DyckWords

?DyckWords

DyckWords[4]

LeftCombTree and RightCombTree

?LeftCombTree

BareTreeForm/@LeftCombTree/@Range[10]

?RightCombTree

BareTreeForm/@RightCombTree/@Range[10]

LeftCrookedTree and RightCrookedTree

?LeftCrookedTree

BareTreeForm/@LeftCrookedTree/@Range[2,10]

?RightCrookedTree

BareTreeForm/@RightCrookedTree/@Range[2,10]

LeftPathTree and RightPathTree

?LeftPathTree

?RightPathTree

Row[Table[BareTreeForm[LeftPathTree@@Range[n]],{n,2,10}]]

LeftTurnTree and RightTurnTree

?LeftTurnTree

?RightTurnTree

BareTreeForm[LeftTurnTree[2,3]]

Grid[Table[BareTreeForm[LeftTurnTree[m,n]],{m,4},{n,2,7}]]

PathTree and FromPathTree

?PathTree

‘0’ means ‘left’, and ‘1’ means ‘right’:

BareTreeForm[PathTree[{0,0,0,0,0,0,0}]]

?FromPathTree

FromPathTree/@PathTrees[5]

PathTreeQ

?PathTreeQ

BareTreeForm/@Select[BinaryTrees[5],PathTreeQ]

PathTrees

?PathTrees

BareTreeForm/@PathTrees[5]

RandomBinaryTree

?RandomBinaryTree

Table[BareTreeForm[RandomBinaryTree[20]],{10}]

RandomPathTree

?RandomPathTree

Table[BareTreeForm[RandomPathTree[20]],{10}]

RankBinaryTree

?RankBinaryTree

RankBinaryTree[{{},{{},{{{{},{}},{{{{},{}},{}},{}}},{}}}}]

BinaryTrees[9][[109]]=={{},{{},{{{{},{}},{{{{},{}},{}},{}}},{}}}}

RankTree

?RankTree

RankTree[{{{},{},{{},{},{{}}}}}]

Trees[9][[275]]=={{{},{},{{},{},{{}}}}}

TreeChop

?TreeChop

tree=CompleteBinaryTree[64];

BareTreeForm[tree]

BareTreeForm[TreeChop[tree,3]]

Clear[tree]

TreeEdgeRules and FromTreeEdgeRules

?TreeEdgeRules

tree={{},{{{{{}}}},{{},{{}}}}};
BareTreeForm[tree]

TreeEdgeRules[tree]

?FromTreeEdgeRules

FromTreeEdgeRules[{1->2,1->3,3->4,3->5,4->6,5->7,5->8,6->9,8->10,9->11}]

Clear[tree]

Trees

?Trees

BareTreeForm/@Trees[5]