#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
	树：是由结点与节点之间的链接关系组成
	
	树的特征：
		1、存在唯一的起始点，树根
		2、树根外的其他结点都有且只有一个前驱结点；但每个结点可以有0-n个后继
			  树可以有多个尾结点
			  
		3、树根可以到达任意结点（有限跳）
		4、任意两个不同结点向下出发，无交叉
		
	二叉树：
		树中每个结点最多关联到两个后继结点
		后继结点明确分左右
		
		左右子树必须明确说明
		
		几个基本概念：（都是对于二叉树而言）
			空树：不包含任何结点
			单点树：只包含一个结点
			父结点和子节点是相对而言的
			边：父到子，具有方向性
			兄弟结点：具有相同的父结点的结点
			树叶：没有子节点的二叉树
			分支结点
			度数：一个结点的子结点的个数
			
			路径边的条数 -- 路径的长度
			到自身，长度为0
			路径唯一性
			
			从树根到树中任一结点的路径长度 --- 结点的层数
			
			二叉树的高度（深度） -- 树中结点最大层数
			
			
		二叉树的性质：
			1、在非空二叉树第i层中至多有2^i个结点（i >=0)
			2、高度为h的二叉树至多有2^(h+1)-1个结点 (h>=0)
			3、对于任何非空二叉树，如果叶结点的个数为n0，度数为2的结点个数为n2
				  n0 = n2 + 1
				  
		
		满二叉树;
			所有分支结点的度数都为2
			
			性质; 	满二叉树里的叶结点比分支结点多一个
			
		扩充二叉树：
			将非满二叉树扩充成满 -- 外部结点：内部结点
			
		完全二叉树：
			最后一层排不满，且空位都在右边（如果有空位的话）
			
			n个结点的完全二叉树高度 h =[log_2(n)], 即为不大于它的最大整数
			
			notes: 从上到下，从左到右编号，0开始，对任意结点i都有
				1、0 -- 根结点
				2、i>0, 父结点编号int((i-1)/2)
				3、2*i + 1 < n, 左子结点序号为 2*i + 1, 否则它没有子节点
				4、2*i + 2 < n ，右子结点序号为 2*i + 2, 否则没有子结点
				
				                             (i-1)/2
							i									i+1
				2*i +1		2*i + 2
				
总结：


	
"""