阅前提示

该系列为数据结构回顾向文章，重点在于温故知新。 适合人群：All 阅读方式：浏览回顾 本系列在不断更新中，如果对你有所帮助，点赞收藏吧：）

文章目录

阅前提示树二叉树二叉查找树

---

树，大家最熟悉又最陌生。 天天的撸码生涯是不是天天打交道呢？多半已经被优化并封装好了，我们会用就行啦。但是还是要好好掌握一下这个分水岭的妙处~ 为什么称之为分水岭呢？作者大学期间刚刚开始学习数据结构课程的时候，前面的队列链表顺风顺，水上课不用听也基本上可以把它撸出来，现在也记忆犹新。 然而不知道哪一天开始学树了…然后我对数据结构的的记忆就到此终止了… 好了，无论是温故知新还是重新学习，借来下我们就好好认识一下这个分水树(岭)吧~

树

节点由 FirstChild（第一个子节点） + NextSibling（从左至右，下一个兄弟节点）构成

​ 先序遍历：处理子节点前先处理自身

​ 后序遍历：先处理子节点，再处理自身

class TreeNode: Value = None; FirstChild = None; # 第一个子节点 NextSibling = None; # 右侧下一个兄弟 def __init__(self,v:int): self.Value = v; # 先序 def ListOfTree(Node:TreeNode,depth:int): empty = " " if(Node.Value == Node): print(empty*depth + "N") else: print(empty*depth + str(Node.Value)) if(Node.FirstChild != None): ListOfTree(Node.FirstChild,depth + 1); if(Node.NextSibling != None): ListOfTree(Node.NextSibling,depth); # 后续 def ListOfTree2(Node:TreeNode,depth:int): empty = " " if(Node.FirstChild != None): ListOfTree2(Node.FirstChild,depth + 1); if (Node.NextSibling != None): ListOfTree2(Node.NextSibling, depth); if(Node.Value == Node): print(empty*depth + "N") else: print(empty*depth + str(Node.Value))

---

二叉树

最常见的树，是后续搜索树的基本结构 Left + Right 左右两子树构成，深度理想状态为logN

​ 先序遍历：节点、左、右

​ 中序遍历：左、节点、右

​ 后序遍历：左、右、节点

#二叉树 class BTreeNode: Value = None; Left = None; Right = None; def __init__(self,v:int): self.Value = v; # 先序 def ListOfTree(Node:BTreeNode,depth:int): empty = " " if(Node.Value == None): print(empty*depth + "N") else: print(empty*depth + str(Node.Value)) if(Node.Left != None): ListOfTree(Node.Left,depth + 1); if(Node.Right != None): ListOfTree(Node.Right,depth + 1); # 中序 def ListOfTree2(Node:BTreeNode,depth:int): empty = " " if(Node.Left != None): ListOfTree2(Node.Left,depth + 1); if(Node.Value == Node): print(empty*depth + "N") else: print(empty*depth + str(Node.Value)) if(Node.Right != None): ListOfTree2(Node.Right,depth + 1); # 后序 def ListOfTree3(Node:BTreeNode,depth:int): empty = " " if(Node.Left != None): ListOfTree3(Node.Left,depth + 1); if (Node.Right != None): ListOfTree3(Node.Right, depth + 1); if(Node.Value == Node): print(empty*depth + "N") else: print(empty*depth + str(Node.Value))

---

二叉查找树

二叉树，且 左子树值一定小于其根节点的值，右子树的值一定大于根节点的值，不存在相等的节点。

删除操作：叶子就直接删除，存在一个子节点则连接上下，若存在两个，则将该节点右侧的最小值（叶子）替代该节点的值，并删除叶子。

优点：查找速度理想状态控制在O(logN)

缺点：会导致不平衡，导致查找效率达不到O(logN)，尤其是进行多次删除操作后，因为删除都是拿右树的叶子补充，会导致左树高于右树的情况。

class BTreeNode: Value = None; Left = None; Right = None; def __init__(self,v:int): self.Value = v; # 二叉搜索树 左子树值一定小于其根节点的值，右子树的值一定大于根节点的值 class SearchTree: Node = None def Find(self,X:int) -> BTreeNode: self.__find(self.Node,X) def __find(self,Node:BTreeNode,X:int): if Node == None : return None; if Node.Value == X: return Node if Node.Value > X: return self.__find(Node.Left,X); return self.__find(Node.Right,X); def Add(self,X:int): self.Node = self.__add(self.Node,X); def __add(self,Node:BTreeNode,X:int) -> BTreeNode: if Node == None: Node = BTreeNode(X) else: if Node.Value > X : Node.Left = self.__add(Node.Left,X) elif Node.Value < X: Node.Right = self.__add(Node.Right, X) return Node # 删除操作：叶子就直接删除，存在一个子节点则连接上下，若存在两个，则将该节点右侧的最小值（叶子）替代该节点的值，并删除叶子。 def Delete(self,X:int): self.__delete(self.Node,X); def __delete(self,Node:BTreeNode,X:int) -> BTreeNode: if Node == None: return None; if Node.Value > X: Node.Left = self.__delete(Node.Left,X) elif Node.Value < X: Node.Right = self.__delete(Node.Right,X) elif Node.Value == X: if Node.Left != None and Node.Right != None: v = self.__getMin(Node.Right); Node.Value = v Node.Right = self.__delete(Node.Right,v) # 替换了右子树的最小值后删除该最小值的叶子节点。 else: if Node.Left == None: Node = Node.Right; elif Node.Right == None: Node = Node.Left; return Node # 最小值就是左侧叶子 def GetMin(self) -> int: return self.__getMin(self.Node) def __getMin(self,Node) -> int: if Node == None: return None; if Node.Left == None: return Node.Value; return self.__getMin(Node.Left); # 最大值就是右侧叶子 def GetMax(self) -> int: return self.__getMax(self.Node) def __getMax(self,Node) -> int: if Node == None: return None; if Node.Right == None: return Node.Value; return self.__getMax(Node.Right); def Log(self): self.__log(self.Node,0) def __log(self,Node:BTreeNode,depth:int): empty = " " if (Node == None): return; if (Node.Value == None): print(empty * depth + "N") else: print(empty * depth + str(Node.Value)) if (Node.Left != None): self.__log(Node.Left, depth + 1); if (Node.Right != None): self.__log(Node.Right, depth + 1);

---

. . . . .

---

嗨，我是作者Vin129，逐儿时之梦正在游戏制作的技术海洋中漂泊。知道的越多，不知道的也越多。希望我的文章对你有所帮助：）

---