二叉树（了解）c++

二叉树是一种特别的树型结构，它的特点是:

• 每个结点至多只有2棵子树(即二叉树中不存在度大于2的结点)   
  
• 而且二叉树的子树有左右之分，其次序不能任意颠倒，因此是一颗有序树
  

以A结点为例，左边的B是它的左孩子，右边的C是它的右孩子，以左孩子为根的这棵树称为左指树，以右孩子为根的这棵树称为右子树，把BDEH单独拉出来看就是一个二叉树，B是它的根结点，D H是左子树，E是右子树，同理，C这个右子树也是把CFGI单独拿出来看，C是他的根结点，FI是左子树，G是右子树，因此二叉树可以抽象为右边这个等式

• 二叉树也是通过递归界说的结构
  

满二叉树:

   在一棵二叉树中，所有非叶结点都存在左右孩子，所有叶子结点都在同一层，那么这棵树就是满二叉树
                            

 
性质:

• 高度为h的满二叉树，结点个数为2h-1
  
• 结点个数为n的满二叉树，树高h=log以2为底n+1
  
• 如果将满二叉树按照层序遍历的过程编号:从根节点开始，由1开始编号:
  
  
  
  •  结点i左孩子的编号为2xi
    
  • 结点i右孩子的编号为2xi+1结点i双亲的编号为i/2
    
  • 这个性质可以资助我们存储二叉树 
    
  
  

完全二叉树

   如果一棵树所有结点和同样深度的满二叉树，按照层序遍历编号的位置-一对应，则这棵二叉树为完全二叉树。（这个界说很抽象，我们可以记住相当于在满二叉树的基础上，从后往前依次删掉一些结点就变成了完全二叉树 ）
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。