⼆叉树
⼆叉树的基本概念
⼆叉树是每个节点最多有两个⼦树的树结构。通常⼦树被称作“左⼦树”（left subtree）和“右⼦树”（right        subtree）
⼆叉树的性质(特性)
性质1:        在⼆叉树的第i层上⾄多有2^(i-1)个结点（i>0） 性质2:        深度为k的⼆叉树⾄多有2^k        -        1个结点（k>0） 性质3:        对于任意⼀棵⼆叉树，如果其叶结点数为N0，⽽度数为2的结点总数 为N2，则N0=N2+1; 性质4:具有n个结点的完全⼆叉树的深度必为        log2(n+1) 性质5:对完全⼆叉树，若从上⾄下、从左⾄右编号，则编号为i        的结点，其左 孩⼦编号必为2i，其右孩⼦编号必为2i＋1；其双亲的编号必为i/2（i＝1        时为 根,除外）
(1)完全⼆叉树——若设⼆叉树的⾼度为h，除第        h        层外，其它各层        (1～ h-1)        的结点数都达到最⼤个数，第h层有叶⼦结点，并且叶⼦结点都是 从左到右依次排布，这就是完全⼆叉树。

(2)满⼆叉树——除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最 底层的⼆叉树。


⼆叉树的节点表示以及树的创建
通过使⽤Node类中定义三个属性，分别为elem本身的值，还有lchild左孩⼦ 和rchild右孩⼦

[AppleScript] 纯文本查看 复制代码

class	Node(object):				"""节点类"""				def	__init__(self,	elem=-1,	lchild=None,	rchild=None):								self.elem	=	elem								self.lchild	=	lchild								self.rchild	=	rchild

树的创建,创建⼀个树的类，并给⼀个root根节点，⼀开始为空，随后添加节 点

[AppleScript] 纯文本查看 复制代码

class	Tree(object):				"""树类"""				def	__init__(self,	root=None):								self.root	=	root
				def	add(self,	elem):								"""为树添加节点"""								node	=	Node(elem)								#如果树是空的，则对根节点赋值								if	self.root	==	None:												self.root	=	node								else:												queue	=	[]												queue.append(self.root)												#对已有的节点进⾏层次遍历												while	queue:																#弹出队列的第⼀个元素																cur	=	queue.pop(0)																if	cur.lchild	==	None:																				cur.lchild	=	node																				return																elif	cur.rchild	==	None:																				cur.rchild	=	node																				return																else:																				#如果左右⼦树都不为空，加⼊队列继续判断																				queue.append(cur.lchild)																				queue.append(cur.rchild)

⼆叉树
⼆叉树的基本概念
⼆叉树是每个节点最多有两个⼦树的树结构。通常⼦树被称作“左⼦树”（left subtree）和“右⼦树”（right        subtree）
⼆叉树的性质(特性)
性质1:        在⼆叉树的第i层上⾄多有2^(i-1)个结点（i>0） 性质2:        深度为k的⼆叉树⾄多有2^k        -        1个结点（k>0） 性质3:        对于任意⼀棵⼆叉树，如果其叶结点数为N0，⽽度数为2的结点总数 为N2，则N0=N2+1; 性质4:具有n个结点的完全⼆叉树的深度必为        log2(n+1) 性质5:对完全⼆叉树，若从上⾄下、从左⾄右编号，则编号为i        的结点，其左 孩⼦编号必为2i，其右孩⼦编号必为2i＋1；其双亲的编号必为i/2（i＝1        时为 根,除外）
(1)完全⼆叉树——若设⼆叉树的⾼度为h，除第        h        层外，其它各层        (1～ h-1)        的结点数都达到最⼤个数，第h层有叶⼦结点，并且叶⼦结点都是 从左到右依次排布，这就是完全⼆叉树。

(2)满⼆叉树——除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最 底层的⼆叉树。


⼆叉树的节点表示以及树的创建
通过使⽤Node类中定义三个属性，分别为elem本身的值，还有lchild左孩⼦ 和rchild右孩⼦

[AppleScript] 纯文本查看 复制代码

class	Node(object):				"""节点类"""				def	__init__(self,	elem=-1,	lchild=None,	rchild=None):								self.elem	=	elem								self.lchild	=	lchild								self.rchild	=	rchild

树的创建,创建⼀个树的类，并给⼀个root根节点，⼀开始为空，随后添加节 点

[AppleScript] 纯文本查看 复制代码

class	Tree(object):				"""树类"""				def	__init__(self,	root=None):								self.root	=	root
				def	add(self,	elem):								"""为树添加节点"""								node	=	Node(elem)								#如果树是空的，则对根节点赋值								if	self.root	==	None:												self.root	=	node								else:												queue	=	[]												queue.append(self.root)												#对已有的节点进⾏层次遍历												while	queue:																#弹出队列的第⼀个元素																cur	=	queue.pop(0)																if	cur.lchild	==	None:																				cur.lchild	=	node																				return																elif	cur.rchild	==	None:																				cur.rchild	=	node																				return																else:																				#如果左右⼦树都不为空，加⼊队列继续判断																				queue.append(cur.lchild)																				queue.append(cur.rchild)