[数据结构与算法]简述树的特立——二叉树

概念

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

?特殊二叉树

1.满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。. 也就是说，如果一个二叉树的层数为K，且结点总数是 (2^k) -1 ，则它就是满二叉树。如下图：

?2.完全二叉树：满足以下要求：. 所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；. 第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。注意：满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

?二叉树的性质

性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

????????1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

????????2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子

?

二叉树的存储结构

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}

?

// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

?

?题目