目录的二进制树Unix

Question

我有一个在bash shell中创建目录的二进制的任务，深度是作为脚本的第一个参数。每个目录都必须命名第二个参数 目录中的树的深度。

示例：./tree.sh 3名称应创建以下结构：

                        name11
                      /        
                name21          name22
                /              /    
            name31  name32    name33 name34

我真的不知道该怎么做，甚至无法开始。直到现在，这都比我在击败中所做的任何事情都难。任何帮助都将不胜感激。预先感谢。

Answer 1

带有递归：

#!/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

用./tree.sh 3

Answer 2

即使其他语言更适合实施链接列表，我也不知道为什么这篇文章会受到负面投票。

这是这位专家，分享了一些适合搜索的东西，看看：https://gist.github.com/iestynpryce/4153007

注意： bash中二进制排序树的实现。使用 eval 伪造了类似对象的行为。请记住，在外壳脚本中的评估可能是邪恶的。

#!/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

实际上，我认为，在 bash 中实现AA BST非常容易。

如何：只需创建一个：） damn .txt ：）用于维护bst的文件。

在这里，如果使用简单的.txt文件实现，我将不会展示如何实现插入/填充或删除/更新BST节点的CRUD操作，但是它可以与打印值相比。我将努力并尽快分享解决方案。

这是我的解决方案：只需在bash中的fysa，我使用了.txt文件方法，并尝试从任何根节点打印相同的词：https：//stackoverflow.com/a/67341334/1499296