树

树的概念

树的特性

• 1）一棵树中的任意两个结点有且仅有唯一的一条路径连通；
• 2）一棵树如果有n个结点，则它一定有n−1条边；
• 3）在一棵树中加一条边将会构成一个回路。

二叉树

• 1）二叉树是一种特殊的树，二叉树的特点是每个结点最多有两个儿子。
• 2）二叉树使用范围最广，一颗多叉树也可以转化为二叉树。

满二叉树

• 1）二叉树中每个内部节点都有两个儿子，满二叉树所有的叶节点都有相同的深度。
• 2）满二叉树是一棵深度为h且有2h−1个结点的二叉树。

完全二叉树

• 1）若设二叉树的高度为h，除了第h层外，其他层的结点数都达到最大个数，第h层从右向左连续 缺若干个结点，则为完全二叉树。

树的特点

• 1、如果一棵完全二叉树的父节点编号为K,则其左儿子的编号是2K,右儿子的结点编号为2K+1
• 2、已知完全二叉树的总节点数为n求叶子节点个数：
  • 当n为奇数时：（n+1）/2
  • 当n为偶数时 : （n）/2
• 3、已知完全二叉树的总节点数为n求父节点个数：为：n/2
• 4、已知完全二叉树的总节点数为n求叶子节点为2的父节点个数：
  • 当n为奇数时：n/2
  • 当n为偶数时 : n/2-1
• 5、如果一棵完全二叉树有N个结点，那么这棵二叉树的深度为【log2（N+1）log2（N+1）】（向上取整）

树的特性模拟文件夹操作

"""
树模拟文件夹
"""


class Node:

    def __init__(self, name, ty="dir"):
        """

        :param name: 目录名称 
        :param ty: 类型
        """
        self.name = name
        self.type = ty
        self.parent = None
        self.children = []

    def __repr__(self):
        """返回展示名称而非内存地址"""
        return self.name


class FileTree:

    def __init__(self):
        self.root = Node("/")
        self.now = self.root

    def mkdir(self, name):
        """
        创建目录
        :param name: 新目录名称 
        :return: 
        """
        if name[-1] != "/":
            name += "/"
        # 创建该节点
        node = Node(name)
        # 为根目录添加当前节点
        self.now.children.append(node)

    def ls(self):
        """
        返回当前目录下的所有节点
        :return: 
        """
        return self.now.children

    def cd(self, name):
        """
        进入指定目录

        :param name: 目录名称 
        :return: 
        """
        if name[-1] != "/":
            name += "/"
        # 判断是否为返回上一级
        if name == "../":
            self.now = self.now.parent
            return
        # 寻找到指定的目录
        for child in self.now.children:
            if child.name == name:
                self.now = child
                return
        # 没有查找的目录抛出异常
        raise ValueError("invalid dir")


tree = FileTree()
tree.mkdir("bin")
tree.mkdir("etc")

print("---", tree.ls())
tree.cd("etc")
print("---", tree.ls())