show function of binary tree structure (a solution is given).

[zkk960317]

using DataStructures
tree = RBTree{Int}();
for k in 1:2:20
    push!(tree, k)
end
tree

The above code produces the following long output:

RBTree{Int64}(DataStructures.RBTreeNode{Int64}(false, 7, DataStructures.RBTreeNode{Int64}(false, 3, DataStructures.RBTreeNode{Int64}(false, 1, DataStructures.RBTreeNode{Int64}(false, nothing, nothing, nothing, 
nothing), DataStructures.RBTreeNode{Int64}(false, nothing, nothing, nothing, nothing), DataStructures.RBTreeNode{Int64}(#= circular reference @-2 =#)), 
……
DataStructures.RBTreeNode{Int64}(false, nothing, nothing, nothing, nothing), 10)

This is because the show function of binary tree is missing. So I developed the show function as follows:

Base.show(io::IO, tree::Union{RBTree,AVLTree,SplayTree}) = Base.show(io::IO, tree.root)

function Base.show(io::IO, root::Union{DataStructures.RBTreeNode,DataStructures.AVLTreeNode,DataStructures.SplayTreeNode})
    lowbit(x::Int) = Int(log2(x & (~x+1)))
    function printLevel(nodeList::Vector)
        nodeList1 = Any[]
        for (n,node) in enumerate(nodeList)
            n ==1 || (str *= string(repeat("·",lowbit(n-1))))
            if node == nothing
                append!(nodeList1, [nothing, nothing])
                str *= string("[,]")
                continue
            end
            data = node.leftChild == nothing ? string() : string(node.leftChild.data)
            str *= string('[', data)
            data = node.rightChild == nothing ? string() : string(node.rightChild.data)
            str *= string(',', data, ']')
            append!(nodeList1, [node.leftChild, node.rightChild])
        end
        return nodeList1
    end

    h = 8 # only show the first $h levels
    level = 0
    nodeList = [root]
    str = string(level, ": ", root.data)
    for i = 1:h  
        println(io,str)
        str = string(level + 1, ": ")
        nodeList = printLevel(nodeList)
        all(nodeList .== nothing) && return
        level += 1
    end
    level == h && println("......")
end

Then the above RBTree show like this:

0: 7    
1: [3,11]
2: [1,5][9,15]
3: [nothing,nothing][nothing,nothing]·[nothing,nothing][13,17]
4: [,][,]·[,][,]··[,][,]·[nothing,nothing][nothing,19]
5: [,][,]·[,][,]··[,][,]·[,][,]···[,][,]·[,][,]··[,][,]·[,][nothing,nothing]  

And the AVLTree show like this:

tree = AVLTree{Int}()
for k in 1:2:20
    push!(tree, k)
end
tree

0: 7    
1: [3,15]
2: [1,5][11,17]
3: [,][,]·[9,13][,19]

This function works with RBTree, AVLTree and SplayTree. The following is a brief description of the display:

1. The number of the tree level is displayed at the beginning of each line.
2. [a,b] is the left and right child of the same node.
3. [a,b][c,d] means that the second generation above them is the same node.
4. [a,b]·[c,d] means that the third generation above them is the same node.
5. [a,b]··[c,d] means the 4th ... , and so on.

I hope a developer can check my code and pull it!