Binary tree of directories UNIX

Question

I have a task to create a binary tree of directories in bash shell, the depth is given as a first argument of the script. Every directory has to be named with the second argument + the depth of the tree which the directory is in.

Example: ./tree.sh 3 name should create the following structure:

                        name11
                      /        \
                name21          name22
                /    \          /    \
            name31  name32    name33 name34

I don't really have an idea how to do this, Can't even start. It is harder than anything i have done in bash up until now.. Any help will be very much appreciated. Thanks in advance.

What do you do if a directory has more than two subdirectories? — CR Drost, May 10 '15 at 12:50
No, not really, never worked on problems like this. That is why i am asking for help :) — mouseepaad, May 10 '15 at 12:53
Is that really `name32`, or should that be `name33`. It really ought to be `name221`, or even `nameRL` with the root directory being simply `name` — William Pursell, May 10 '15 at 12:55
If you can accurately describe the names of the two directories that you will create inside `nameXY`, you are more than half way to solving the problem. — William Pursell, May 10 '15 at 12:59
@mouseepaad: Do you only want to print a tree with three levels or do you want to create the real structure of a [binary tree](http://en.wikipedia.org/wiki/Binary_tree) in variables/arrays? — Cyrus, May 10 '15 at 13:56
Create the directories only... the tree is shown for example how should they look like. With number of levels that is equal to the second command line argument. — mouseepaad, May 10 '15 at 14:44

score 0 · Accepted Answer · answered May 10 '15 at 16:55

With recursion:

#!/bin/bash

level=$1
current_level=$2; current_level=${current_level:=1}
last_number=$3; last_number=${last_number:=1}
prefix="name"

# test to stop recursion
[[ $level -eq $(($current_level-1)) ]] && exit

# first node
new_number=$(($current_level*10+$last_number*2-1))
mkdir "$prefix$new_number"
(
  cd "$prefix$new_number"
  $0 $level $(($current_level+1)) $(($last_number*2-1)) &
)

# second node, not in level 1
if [[ $current_level -ne 1 ]]; then
  new_number=$(($current_level*10+$last_number*2))
  mkdir "$prefix$new_number"
  cd "$prefix$new_number"
  $0 $level $(($current_level+1)) $(($last_number*2)) &
fi

Test with ./tree.sh 3

Be carefull with larger numbers to avoid a [fork bomb](http://en.wikipedia.org/wiki/Fork_bomb). — Cyrus, May 10 '15 at 18:02
To prevent a fork bomb in linux, edit the number of processes a user may create, e.g. `ulimit -u 30` — Alan, Feb 05 '16 at 10:45

AKS · Answer 2 · 2021-04-30T23:02:34.877

Even though other languages are more suitable in implementing a link list, I don't know why this post got a negative vote.

Here's this expert, shared something good for searching, take a look: https://gist.github.com/iestynpryce/4153007

NOTE: An implementation of a Binary Sort Tree in Bash. Object-like behaviour has been faked using eval. Remember that eval in shell scripting can be evil. BT and BST have difference, you can google it.

#!/bin/bash
#
# Binary search tree is of the form:
#               10
#              /  \
#             /    \
#            4      16
#           / \    /  
#          1   7  12
#

# Print the binary search tree by doing a recursive call on each node.
# Call the left node, print the value of the current node, call the right node.
# Cost is O(N), where N is the number of elements in the tree, as we have to
# visit each node once.
print_binary_search_tree() {
    local node="$*";
    # Test is the node id is blank, if so return
    if [ "${node}xxx" == "xxx" ]; then
        return;
    fi
    print_binary_search_tree $(eval ${node}.getLeftChild)
    echo $(${node}.getValue)
    print_binary_search_tree $(eval ${node}.getRightChild)
}

### Utility functions to generate a BST ###

# Define set 'methods'
set_node_left() {
    eval "${1}.getLeftChild()  { echo "$2"; }"
}
set_node_right() {
    eval "${1}.getRightChild() { echo "$2"; }"
}
set_node_value() {
    eval "${1}.getValue()      { echo "$2"; }"
}

# Generate unique id:
gen_uid() {
    # prefix 'id' to the uid generated to guarentee
    # it starts with chars, and hence will work as a
    # bash variable
    echo "id$(uuidgen|tr -d '-')";
}

# Generates a new node 'object'
new_node() {
    local node_id="$1";
    local value="$2";
    local left="$3";
    local right="$4";
    eval "${node_id}set='set'";
    eval "set_node_value $node_id $value";
    eval "set_node_left $node_id $right";
    eval "set_node_right $node_id $right";
}

# Inserts a value into a tree with a root node with identifier '$id'.
# If the node, hence the tree does not exist it creates it.
# If the root node is at the either end of the list you'll reach the
# worst case complexity of O(N), where N is the number of elements in 
# the tree. (Average case will be 0(logN).)
tree_insert() {
    local id="$1"
    local value="$2";
    # If id does not exist, create it
    if [ -z "$(eval "echo \$${id}set")" ]; then
        eval "new_node $id $value";
    # If id exists and the value inserted is less than or equal to 
    # the id's node's value. 
    # - Go down the left branch
    elif [[ $value -le $(${id}.getValue) ]]; then
        # Go down to an existing left node if it exists, otherwise
        # create it.
        if [ "$(eval ${id}.getLeftChild)xxx" != "xxx" ]; then
            tree_insert $(eval ${id}.getLeftChild) $value
        else
            local uid=$(gen_uid);
            tree_insert $uid $value;
            set_node_left $id $uid;
        fi
    # Else go down the right branch as the value inserted is larger
    # than the id node's value.
    else 
        # Go down the right node if it exists, else create it
        if [ "$(eval ${id}.getRightChild)xxx" != "xxx" ]; then
            tree_insert $(eval ${id}.getRightChild) $value
        else
            local uid=$(gen_uid);
            tree_insert $uid $value;
            set_node_right $id $uid;
        fi
    fi
}

# Insert an unsorted list of numbers into a binary search tree
for i in 10 4 16 1 7 12; do
    tree_insert bst $i;
done

# Print the binary search tree out in order
print_binary_search_tree bst

Actually, I think, it's super easy to implement aa BST in BASH.

How: Just create a :) damn .txt :) FILE for maintaining the BST.

Here, I'm not going to show how you can implement the CRUD operation for inserting/populating or deleting/updating a BST nodes if implemented using a simple .txt file, but it works as far as printing values. I'll work on it and share the solution soon.

Here is my solution: Just FYSA In BASH, I used a .txt file approach and tried for printing the same from any root node here: https://stackoverflow.com/a/67341334/1499296

Binary tree of directories UNIX

2 Answers2