Location>code7788 >text

Data Structures - Tree Structures

Popularity：282 ℃/2024-08-06 22:58:02

A while ago, I happened to be learning about decision trees in machine learning, and I remembered the scene of learning about trees as a data structure many years ago, so I just took the opportunity to return to my knowledge.
A tree is a very common data structure which consists of Nodes and Edges. It has some of the following characteristics:
1. Root Node: The tree has and only one root node, which is the top node of the tree.
2. Node: Each node contains a value or information, and each node, except the root node, has a parent node and zero or more child nodes.
3. Edge: a line connecting two nodes, indicating the relationship between the nodes.
4. Leaf Node: a node with no children.
5. Child Node: A node that is directly connected under a node.
6. Parent Node: A node directly attached to a node.
7. Subtree: a tree consisting of a node and all its children.

Based on the nodes of the tree, there are mainly the following classifications:
1. Binary Tree: Each node has at most two child nodes, called the left and right child nodes.
2. Complete Binary Tree (Complete Binary Tree): the nodes of all layers are filled except the last layer, which is arranged to the left.
3. Full Binary Tree: Each node is either a leaf node or has two children.
4. Balanced Binary Tree: A binary tree in which the difference in height between the left and right subtrees does not exceed one.
5. Binary Search Tree (BST): the value of the left child node is less than the value of the parent node, and the value of the right child node is greater than the value of the parent node.

There are many real-world applications of trees, for example, the file system structure in the LInux system is a tree structure.
I implemented this file system tree structure in Python with the following code:

class FileSystemNode:
    def __init__(self, name, is_directory=False):
         = name
        self.is_directory = is_directory
         = []

    def add_child(self, child_node):
        if self.is_directory:
            (child_node)
        else:
            raise ValueError("Cannot add child to a file node")

    def __repr__(self, level=0):
        ret = "\t" * level + repr() + "\n"
        for child in :
            ret += child.__repr__(level + 1)
        return ret

# Creating the file system root directory
root = FileSystemNode("/", is_directory=True)

# Creating subdirectories and files
home = FileSystemNode("home", is_directory=True)
var = FileSystemNode("var", is_directory=True)
etc = FileSystemNode("etc", is_directory=True)

user1 = FileSystemNode("user1", is_directory=True)
user2 = FileSystemNode("user2", is_directory=True)

documents = FileSystemNode("documents", is_directory=True)
pictures = FileSystemNode("pictures", is_directory=True)

file1 = FileSystemNode("")
photo1 = FileSystemNode("")

# Build the file system tree
root.add_child(home)
root.add_child(var)
root.add_child(etc)

home.add_child(user1)
home.add_child(user2)

user1.add_child(documents)
user1.add_child(pictures)

documents.add_child(file1)
pictures.add_child(photo1)

# Printing the file system tree
print(root)

Run the code to get the output as shown below:

'/'
	'home'
		'user1'
			'documents'
				''
			'pictures'
				''
		'user2'
	'var'
	'etc'

You can see that this folder structure is a multiforked tree, where a parent node can have multiple children.
The decision tree mentioned at the very beginning is also an application of a tree structure. Here is the definition of a tree and three traversal algorithms implemented in Python:

class TreeNode.
    def __init__(self, value=0, left=None, right=None): def __init__(self, value=0, left=None, right=None).
         = value
         = left
         = right


# Create a simple binary tree
root = TreeNode(1)
 = TreeNode(2)
 = TreeNode(3)
 = TreeNode(4)
 = TreeNode(5)


# Pre-order traversal
def pre_order_traversal(node).
    if not node: return
        print(, end=' ')
    print(, end=' ')
    pre_order_traversal()
    pre_order_traversal()

# Mid-order traversal
def mid_order_traversal(node).
    if not node: return
        return
    mid_order_traversal()
    print(, end=' ')
    mid_order_traversal()

# Post-order traversal
def post_order_traversal(node).
    if not node: return
        if not node: return
    post_order_traversal()
    post_order_traversal()
    print(, end=' ')

# Call preorder traversal
pre_order_traversal(root) # Output: 1 2 4 5 3
print("-------------------------\r\n")
mid_order_traversal(root)
print("-------------------------\r\n")
post_order_traversal(root)

I'm continuing to study the rest of Tree's case tomorrow, day arching and living up to my years.

<Previous Next>