理解二叉树【1】

二叉树的结构：
特点：

每个节点最多有两棵子树，所以不存在度大于2的节点。
左子树和右子树是有顺序的，顺序不能颠倒
即使树中的某个节点只有一棵子树，也要区分左子树或者右子树。
度：结点拥有的子树个数（树的度是，树内各结点的度的最大值）
深度/高度：结点的层次从根开始定义为第一次层。由上而下，树中结点的最大层数，即为树的深度。

二叉树分类：
空二叉树
满二叉树（一个二叉树的左右孩子是满二叉树，一定是满二叉树吗？不一定）
完全二叉树（一个二叉树的左右孩子都是完全二叉树，一定是，完全二叉树吗？不一定）
斜二叉树
二叉树的性质：
【1】若二叉树的层次从0开始，则而擦函数的第i层最多有2^i个。（i>=0)
【2】深度为k的而二叉树至多有2^k -1个结点（k>=1)
【3】任何一个二叉树，如果其叶结点个数为n0，度为2的非叶结点个数为n2，则有n0=n2+1
总结点 = n0 + n1 +n2
完全二叉树:
如下图：
若设置二叉树高度为h，则公有h+1层，除了h层以外，其他各层（0~h-1）结点数都达到最大数，第h层开始，从右往左连续缺少若干个结点，即为完全二叉树。（缺失最底层的右边的结点，保证序号是连续的）

深度：[log2n]+1

二叉树的存储结构：

顺序存储结构：一维数组存储
链式存储结构
静态结构

这样就可以看出完全二叉树的优越性。顺序存储也可以反映出二叉树的结构。
经过比较，完全二叉树，二叉树，以及斜而二叉树，可以发现，为了避免存储空间的浪费，顺序存储一般用于完全二叉树。
他们之间之间的关系由（左孩子用 2i+1 右孩子用2i+2(数组的下标)）
二叉链表：
根据二叉树每个结点最多有两个孩子的特点，所以设计了一个数据域，两个指针域。
示例代码：

 typedef char ElemType;
 typedef struct BtNode
 {
  ElemType data;
  struct BtNode* leftchild;
  struct BtNode* rightchild; 
 }BtNode,*BinaryTree;

三叉链表：（需要回溯）

静态结构（链表很好的反映了这种逻辑关系）

void PreOder(BtNode* p)
{
	if (p != nullptr)
	{
		cout << p->data << " ";
		PreOder(p->leftchild);
		PreOder(p->rightchild);
	}
 }

  void InOder(BtNode *p)
  {
   if(p != nullptr)
   {
    InOder(p->leftchild);
    cout<data<<" ";
    InOder(p->rightchild);
    } 
  }

void EndOder(BtNode* p)
{
	if (p != nullptr)
	{
		
		EndOder(p->leftchild);
		EndOder(p->rightchild);
		cout << p->data << " ";
	}
}

理解二叉树 【1】