1 二叉树的性质
① 在二叉树的第i层至多有2^(i-1)个节点
② 深度为k的二叉树至多有2^k-1个节点
③ 对于任意一颗二叉树，如果其叶子节点数为N0，而度数为2的节点总数为N2，则N0=N2+1
④ 具有n个节点的完全二叉树的深度必为log2(n+1)
⑤ 对完全二叉树，若从上至下，从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1，其双亲的编号必为i/2（i=1时为根，除外）
2 二叉树的实现
二叉树的实现与链表类似，由节点构成，每个节点包含1个数值及左右两个连接点。
class Node(object): def __init__(self,item): self.item=item self.lchild=None self.rchild=None class DoubleTree(object): def __init__(self): self.root=None def add(self, item): node=Node(item) if(self.root is None): self.root=node return queue=[self.root] while queue: cur_node=queue.pop(0) if(cur_node.lchild is None): cur_node.lchild=node return else: queue.append(cur_node.lchild) if(cur_node.rchild is None): cur_node.rchild=node return else: queue.append(cur_node.rchild) def travel(self): if(self.root is None): return queque=[self.root] while queque: cur_node=queque.pop(0) print(cur_node.item) if (cur_node.lchild is not None): queque.append(cur_node.lchild) if (cur_node.rchild is not None): queque.append(cur_node.rchild)
3 二叉树的遍历
二叉树的遍历可以从广度及深度两个方向进行，上面2中介绍了广度上的遍历，深度遍历包括三种方式：先序遍历、中序遍历和后序遍历。遍历中用到了递归方法。
def xianxu(self,node): if(node is None): return print(node.item) self.xianxu(node.lchild) self.xianxu(node.rchild)
原文：https://www.cnblogs.com/zhuome/p/11487825.html