用Python如何判断不同类型的二叉树
二叉树是一种树状数据结构，其中每个父节点最多可以有两个子节点。
二叉树的类型
完全二叉树
完全二叉树是一种特殊类型的二叉树，其父节点存在2种情况，要么有2个子节点，要么没有子节点，详情如下图：
完全二叉树定理
1、叶数为i+1
2、节点总数为2i+1
3、内部节点数为(n–1)/2
4、叶数为(n+1)/2
5、节点总数为2l–1
6、内部节点数为l–1
7、叶子的数量最多2^λ-1
Python判断完整二叉树
class Node: def __init__(self,item): self.item=item self.leftChild=None self.rightChild=None def isFullTree(root): if root is None: return True if root.leftChild is None and root.rightChild is None: return True if root.leftChild is not None and root.rightChild is not None: return(isFullTree(root.leftChild)and isFullTree(root.rightChild)) return False root=Node(1) root.rightChild=Node(3) root.leftChild=Node(2) root.leftChild.leftChild=Node(4) root.leftChild.rightChild=Node(5) root.leftChild.rightChild.leftChild=Node(6) root.leftChild.rightChild.rightChild=Node(7) if isFullTree(root): print("The tree is a full binary tree") else: print("The tree is not a full binary tree")登录后复制
