前段时间刚好在学习机器学习中的决策树，想起多年前学习树这个数据结构的场景，刚好借此机会回归一下知识点。
树是一种非常常见的数据结构，它由节点（Node）和边（Edge）构成。它有如下的一些特征：
1. 根结点（Root Node）：树有且只有一个根结点，它是树的顶端结点。
2.结点（Node）：每个结点包含一个值或信息，除了根结点，每个结点都有一个父结点和零个或多个子结点。
3.边（Edge）：连接两个结点的连线，表示结点之间的关系。
4.叶结点（Leaf Node）：没有子结点的结点。
5.子结点（Child Node）：直接连接在某结点下的结点。
6.父结点（Parent Node）：直接连接在某结点上的结点。
7.子树（Subtree）：由一个结点及其所有子结点组成的树。
根据树的节点情况，主要有下面的分类：
1.二叉树（Binary Tree）：每个结点最多有两个子结点，称为左子结点和右子结点。
2.完全二叉树（Complete Binary Tree）：除了最后一层，其他层的结点都填满了，最后一层的结点靠左排列。
3.满二叉树（Full Binary Tree）：每个结点要么是叶结点，要么有两个子结点。
4.平衡二叉树（Balanced Binary Tree）：左右子树的高度差不超过1的二叉树。
5.二叉搜索树（Binary Search Tree, BST）：左子结点的值小于父结点的值，右子结点的值大于父结点的值。
树的真实应用很多，比如LInux系统中的文件系统结构就是树结构。
我用Python实现了这个文件系统的树结构，代码如下：
class FileSystemNode: def __init__(self, name, is_directory=False): self.name = name self.is_directory = is_directory self.children = [] def add_child(self, child_node): if self.is_directory: self.children.append(child_node) else: raise ValueError("Cannot add child to a file node") def __repr__(self, level=0): ret ="\t" * level + repr(self.name) +"\n" for child in self.children: ret += child.__repr__(level + 1) return ret# 创建文件系统根目录root = FileSystemNode("/", is_directory=True)# 创建子目录和文件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("file1.txt")photo1 = FileSystemNode("photo1.jpg")# 构建文件系统树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)# 打印文件系统树print(root)运行代码，可以得到输出如下所示：
'/''home''user1''documents''file1.txt''pictures''photo1.jpg''user2''var''etc'可以看出这个文件夹结构是一个多叉树，一个父节点可以有多个子节点。
最开始说到的决策树也是一种树结构的应用。下面是用Python实现的树的定义和三种遍历算法：
class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right# 创建一个简单的二叉树root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)# 前序遍历def pre_order_traversal(node): if not node: return print(node.value, end=' ') pre_order_traversal(node.left) pre_order_traversal(node.right)# 中序遍历def mid_order_traversal(node): if not node: return mid_order_traversal(node.left) print(node.value, end=' ') mid_order_traversal(node.right)# 后序遍历def post_order_traversal(node): if not node: return post_order_traversal(node.left) post_order_traversal(node.right) print(node.value, end=' ')# 调用前序遍历pre_order_traversal(root) # 输出：1 2 4 5 3print("-------------------------\r\n")mid_order_traversal(root)print("-------------------------\r\n")post_order_traversal(root)明天在继续学习树的其他案例，日拱一卒，不负年华。