树树是一种非常重要的非线性结构，它本身就具有递归的性质（在后续的编程中充分体现）。看下图，A节点是B节点的父节点，B节点是A节点的子节点。B、C、D三个节点的父节点是同一个节点A，没有的父节点称为根节点，即E。没有子节点的节点称为叶节点或叶子节点。图中的G、H、I、J、K、L对“树”有三个相似的概念：高度（Height）、深度（Depth）、层级（level）二叉树（binaryTree）二叉树是一个有限集n(n>=0)个节点，它要么是一个空集（称为空二叉树），要么由一个根节点和两个互不相交的左子树和右子树组成，分别称为根节点。上图中，1号是普通二叉树，2号是满二叉树，2号是完全二叉树。满二叉树：在二叉树中。如果所有的分支节点都有左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点是：叶子只能出现在最底层。出现在其他层中，就无法达到平衡。非叶子节点的度数必须为2。在一棵相同深度的二叉树中，满二叉树的节点数最多，叶子数也最多。编号3是一棵完全二叉树》对一棵有n个节点的二叉树逐层编号，如果编号为i的节点（1<=i<=n）与编号为i的节点在完全二叉树中的位置相同二叉树完全相同，所以这棵二叉树称为完全二叉树。”表示叶子节点的上层必须达到最大值，最低两层，最后一层的叶子节点向左排列。二叉树具有以下数学性质：二叉树的第i层最多有2(i-1)个节点(i>0)。一棵深度为k的二叉树最多有2K-1个节点（k>0）。对于任意一棵二叉树，如果其叶子节点的点数为N0，度数为2的节点总数为N2，则N0=N2+1；n个节点的完全二叉树的深度一定是log2(n+1)二叉树中的节点按一定顺序排列，使得每个节点被访问一次且仅访问一次。中序遍历：先左子树，再根节点，最后右子树。前序遍历：先是根节点，然后是左子树，最后是右子树。节点。通俗地说，前序遍历从二叉树的根节点开始，第一次到达该节点时输出节点数据，按照先左后右的方向进行访问。中序遍历是从二叉树的根节点开始，第二次到达该节点时输出节点数据，按照先左后右的方向访问。后序遍历是从二叉树的根节点开始，第三次到达该节点时输出节点数据，按照先左后右的方向进行访问。删除有3种情况。删除的节点是叶节点。这个时候只要删除这个节点，然后把指向这个节点的父节点指针置为空即可。被删除的节点有左子树或右子树，并且只有一个，所以只需将当前删除节点的父节点指向被删除节点的左子树或右子树即可。如果要删除的节点有两个子节点，需要找到该节点右子树的最小节点，替换为要删除的节点，然后删除最小节点，因为最小节点一定没有左子节点代码实现二叉树以上就是二叉树的全部内容，下面使用Python代码具体实现二叉树。按下它实现编程，请自己动手。先实现一个node节点类：classNode(object):def__init__(self,item):self.item=itemself.left=Noneself.right=Nonedef__str__(self):returnstr(self.item)这里的__str__方法是为了方便打印.打印Node类时，会打印__str__的返回值，例如：print(Node(5))会打印出字符串5。实现一个二叉树类：classTree(object):def__init__(self):#The根节点被定义为永远不会被删除并用作哨兵的根。self.root=Node('root')#添加节点操作defadd(self,item):node=Node(item)ifself.rootisNone:self.root=nodeelse:q=[self.root]whileTrue:pop_node=q.pop(0)ifpop_node.leftisNone:pop_node.left=nodereturnifpop_node.rightisNone:pop_node.right=nodereturnelse:q.append(pop_node.left)q.append(pop_node.right)defget_parent(self,item):'''ItemfoundTheparentnode'''ifself.root.item==item:returnNone#根节点没有父节点tmp=[self.root]whiletmp:pop_node=tmp.pop(0)ifpop_node.left和pop_node.left。item==item:returnpop_nodeifpop_node.rightandpop_node.right.item==item:returnpop_nodeifpop_node.leftisnotNone:tmp.append(pop_node.left)ifpop_node.rightisnotNone:tmp.append(pop_node.right)returnNonedefdelete(self,item):'''从二叉树中删除一个元素，首先获取要删除的节点的父节点。如果父节点不为空，则判断该项的左右子树。如果左子树为空，则判断该项是父节点的左孩子还是右孩子。如果是左孩子，则将父节点的左指针指向该项的右子树。否则，父节点的右指针指向该项的右子树。如果右子树为空，则判断该项是父节点的左孩子还是右孩子。如果是左孩子，则将父节点的左指针指向该项的左子树，反之，将父节点的右指针指向该项的左子树。如果左右子树都不为空，则在右子树中找到最左边的叶子节点x，将x覆盖该节点删除。如果删除成功，返回True。如果删除失败，则返回False'''ifself.rootisNone:#如果root为空，什么也不做删除parent.right=del_node.leftdeldel_nodereturnTrueelse:#左右子树都不为空tmp_pre=del_nodetmp_next=del_node.rightiftmp_next.leftisNone:#替换tmp_pre.right=tmp_next.righttmp_next.left=del_node.lefttmp_next.right=del_node。rightelse:whilttmp_next.left:#让tmp指向右子树的最后一片叶子==item:parent.left=tmp_nextelse:parent.right=tmp_nextdeldel_nodereturnTrueelse:returnFalsedeftraverse(self):#level遍历ifself.rootisNone:returnNoneq=[self.root]res=[self.root.item]whileq!=[]:pop_node=q.pop(0)ifpop_node.leftisnotNone:q.append(pop_node.left)res.append(pop_node.left.item)ifpop_node.rightisnotNone:q.append(pop_node.right)res.append(pop_node.right.item)returnresdefpreorder(self,root):#顺序遍历ifrootisNone:return[]result=[root.item]left_item=self.preorder(root.left)right_item=self.preorder(root.right)returnresult+left_item+right_itemdefinorder(self,root):#中序遍历ifrootisNone:return[]result=[root.item]left_item=self.inorder(root.left)right_item=self.inorder(root.right)returnleft_item+result+right_itemdefpostorder(self,root):#后序遍历ifrootisNone:return[]result=[root.item]left_item=self.postorder(root.left)right_item=self.postorder(root.right)returnleft_item+right_item+result运行测试：if__name__=='__main__':t=Tree()foriinrange(10):t.add(i)print('层次遍历:',t.traverse())print('顺序遍历:',t.preorder(t.root))print('中序遍历:',t.inorder(t.root))print('后序遍历:',t.postorder(t.root))foriinrange(10):print(i,"的父亲",t.get_parent(i))foriinrange(0,15,3):print(f"Delete{i}",'success'ift.delete(i)else'failure')print('层序遍历：',t.traverse())print('前序遍历：',t.preorder(t.root))print('中序遍历:',t.inorder(t.root))print('后序遍历:',t.postorder(t.root))执行结果如下：层序遍历:['root',0,1,2,3,4,5,6,7,8,9]前序遍历：['root',0,2,6,7,3,8,9,1,4,5]中序遍历：[6,2,7,0,8,3,9,'root',4,1,5]后序遍历：[6,7,2,8,9,3,0,4,5,1,'root']0的父亲root1的父亲root2的父亲03的父亲04的父亲15的父亲16的父亲27的父亲28的父亲39的父亲3delete0层序遍历成功:['root',8,1,2,3,4,5,6,7,9]前序遍历：['root',8,2,6,7,3,9,1,4,5]前序遍历：[6,2,7,8,3,9,'root',4,1,5]后序遍历：[6,7,2,9,3,8,4,5,1,'root']删除3层序遍历成功：['root',8,1,2,9,4,5,6,7]前序遍历：['root',8,2,6,7,9,1,4,5]中序遍历：[6,2,7,8,9,'root',4,1,5]后序遍历：[6,7,2,9,8,4,5,1,'root']删除6级序遍历成功：['root',8,1,2,9,4,5,7]前序遍历：['root',8,2,7,9,1,4,5]中序遍历：[2,7,8,9,'root',4,1,5]后序遍历：[7,2,9,8,4,5,1,'root']删除9级序遍历成功：['root',8,1,2,4,5,7]前序遍历：['root',8,2,7,1,4,5]中序遍历：[2,7,8,'root',4,1,5]后序遍历：[7,2,8,4,5,1,'root']删除12个失败的平序遍历:['root',8,1,2,4,5,7]前序遍历：['root',8,2,7,1,4,5]中序遍历：[2,7,8,'root',4,1,5]后序遍历：[7,2,8,4,5,1,'root']Binarytree是一个Python库，通过二叉树是通过一个简单的API生成的，可以在Github上查看和操作：https://github.com/joowani/binarytree/releases。本文已收录到GitHubhttps://github.com/MaoliRUNsen/runsenlearnpy100
