深度学习入门小菜鸟，希望像做笔记记录自己学的东西，也希望能帮助到同样入门的人，更希望大佬们帮忙纠错啦~侵权立删。

目录

一、树的一些基础概念

二、python简单树的自行构建

三、python构建二叉树

1、概念申明

2、python实现二叉树的基本操作

1、判断树是否为空

2、照着层的顺序往树添加节点

3、以层序遍历方式输出整棵树

4、找到对应data的节点的父节点

5、删除特定的节点

6、具体调用

---

一、树的一些基础概念

🎈边：边连接两个结点来显示它们之间存在关系。每个结点（除根之外）都恰好从另一个节点的传入连接。每个节点可以具有多个输出边。

🎈节点的度：一个节点含有的子树的个数；

🎈树的度：一棵树中，最大的节点的度；

🎈叶节点或终端节点：度为零的节点；

🎈节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

🎈树的高度（深度）：树中节点的最大层次；

🎈森林：由m（m>=0）棵互不相交的树的集合称为森林；

🎈路径：对于一棵子树中任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径

🎈常用树的分类：

     （1）无序树（自由树）：树中任意节点的子节点之间没有顺序关系；

     （2）有序树：树中任意节点的子节点之间有顺序关系；

     （3）二叉树：每个节点最多含有两个子树的树；

     （4）完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，

    （5）满二叉树的定义是所有叶节点都在最底层的完全二叉树;

    （6）平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

    （7） 排序二叉树（二叉查找树，二叉搜索树、有序二叉树）：

                🌳若它的左子树不为空，则左子树上所有节点的值要均小于根节点的值；

                🌳若它的右子树不为空，则右子树上所有节点的值要均大于根节点的值；

                🌳左、右子树也分别是排序二叉树

    （8）霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

    （9）B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

---

二、python简单树的自行构建

首先定义一个节点的创建

class Node:def __init__(self,data,lchild = None,rchild = None):self.lchild = lchildself.rchild = rchildself.data = data

接着定义树类的初始化

class tree:def __init__(self,root = None):self.root = root

其他的根据具体要求来设定，我们后面再细讲二叉树等的实现。

---

三、python构建二叉树

1、概念申明

再次回顾一下二叉树：每个节点最多含有两个子树的树，这是他的基本性质。除此之外，比较常用的是二叉树的遍历（即如何按某种路径搜索树中的每个结点，使得每个结点都被只访问一次）。

常见的遍历方式有：先序遍历，中序遍历，后序遍历，层序遍历。（遍历方式的实现等待第二篇）

2、python实现二叉树的基本操作

1、判断树是否为空

—— 只需要看树的根节点是否存在即可

    def isEmpty(self): #查看树是否为空return not self.root

2、照着层的顺序往树添加节点

—— 思路就是往叶子上加节点

（1）首先调用前面写的Node类建立一个新的节点

    def add(self,data): #添加子节点到树里面node = Node(data)

（2）然后调用isEmpty()，判断树是否为空。如果是空，则新建的节点即为树的根节点。

        if self.isEmpty(): #如果二叉树为空，那么新建的节点即为树的根节点self.root = node

（3）如果树不为空：

        ①初始创建一个只含树的根节点的列表queue，这就是初始的树

        ②然后进入循环，遍历现在的树，取出queue的第一个元素，即现如今的第一个节点cur

        ③然后有3种情况：

                第一：cur的左子树为空，那我们就把这个节点加到它的左子树上

                第二：cur的右子树为空，那我们就把这个节点加到它的右子树上

                第三：cur的左右子树都不为空，说明还未找到叶子，那我们就把左子树，右子树依次填进queue里。

        else:queue = [self.root] #添加二叉树的根节点,形成初始树while queue:cur = queue.pop(0) #提取第一个元素（第一个节点）if not cur.lchild: #左子树为空，则将把节点加给左子树cur.lchild = nodereturn elif not cur.rchild: #右子树为空，则将把节点加给右子树cur.rchild = nodereturnelse:queue.append(cur.lchild)queue.append(cur.rchild)

3、以层序遍历方式输出整棵树

（1）首先还是调用isEmpty()，判断树是否为空。如果是空，直接返回None结束。

    def printtree(self): #输出整棵树(层序遍历)if self.isEmpty():return None

（2）如果树不为空，参照上面add的思路：

不断取出树的节点，输出节点的data，将该节点的左孩子和右孩子填进queue，不断循环输出直至没有节点了。

        else:queue = [self.root]while queue:cur = queue.pop(0)print(cur.data)if cur.lchild and cur.rchild:queue.append(cur.lchild)queue.append(cur.rchild)elif not cur.lchild and cur.rchild:queue.append(cur.rchild)elif not cur.rchild and cur.lchild:queue.append(cur.lchild)

4、找到对应data的节点的父节点

（1）首先看看根节点的值是否为data，如果是就没有所谓的父节点，那就输出None

    def getparent(self,data): #找到data的父节点if self.root.data == data:return None

（2）按照前面函数的方法遍历树，然后设置判断条件，如果该节点的左/右孩子是我们要找的data，那么就return 这个节点。

同时这里要注意：不能直接if cur.lchild.data == data，因为cur.lchild可能为空，那就没有data这个属性了，那就会报错。

        queue = [self.root]while queue:cur = queue.pop(0)if cur.lchild and cur.lchild.data == data: #这里需要先判断cur.lchild是否为空，如果为空是没有data属性的return curif cur.rchild and cur.rchild.data == data: #这里需要先判断cur.rchild是否为空，如果为空是没有data属性的return curif cur.lchild:queue.append(cur.lchild)if cur.rchild:queue.append(cur.rchild)return None

5、删除特定的节点

（1）首先老规矩判断是否为空，空就None

    def delete(self,data): #删除特定节点if self.isEmpty():return None

（2）然后调用前面的getparent(data)函数，找到对应删除节点的父节点

        parent = self.getparent(data)

（3）如果要删除的节点有父节点：

那么首先判断一下要删除的节点是它的左孩子还是右孩子，并且把这个要删除的节点赋给delnode。

        if parent:if parent.lchild.data == data:delnode = parent.lchildelse:delnode = parent.rchild

接下来进入3大类的判断：

①要删除的节点没有左孩子：那么就用删除的节点的右孩子来替代删除的节点

            if delnode.lchild is None: #要删除的节点没有左孩子if parent.lchild.data == data:parent.lchild = delnode.rchildelse:parent.rchild = delnode.rchilddel delnodereturn True

②要删除的节点没有右孩子：那么就用删除的节点的左孩子来替代删除的节点

            elif delnode.rchild is None: #要删除的节点没有右孩子if parent.lchild.data == data:parent.lchild = delnode.lchildelse:parent.rchild = delnode.lchilddel delnodereturn True

③要删除的节点左右孩子都有：找右子树中的最左叶子节点去代替删除的节点

            else: #要删除的节点左右都有子树renext = delnode.rchildif renext.lchild is None:renext = delnode.rchildrenext.lchild = delnode.lchildelse:while renext.lchild:renext = renext.lchildrenext.lchild = delnode.lchildrenext.rchild = delnode.rchildif parent.lchild.data == data:parent.lchild = renextelse:parent.rchild = renextdel delnodereturn True

最后处理删除的节点没有父节点的情况（根节点），根节点不能删除，返回False。

        else:return False

6、具体调用

k = Tree()
for i in range(5):k.add(i)
k.printtree()
print(k.isEmpty())
print(k.getparent(4).data)
k.delete(1)
k.printtree()

---

欢迎大家在评论区批评指正，谢谢大家~