二叉树详解(求二叉树的结点个数、深度、第k层的个数、遍历等)

二叉树，是一种特殊的树，特点是树的度小于等于2（树的度是整个树的结点的度的最大值），由于该特性，构建二叉树的结点只有三个成员，结点的值和指向结点左、右子树的指针。

typedef int DateType;
typedef  struct TreeNode
{DateType val;//结点的值struct TreeNode*left;//指向左结点struct TreeNode*right;//指向右节点
}Node；

对于二叉树，有一种特殊的情况，即一共有k层，前k-2层每个结点的度都是2，第k-1层若有个结点有子树，则其左侧的结点均有子树，这种情况被称为完全二叉树。若第k-1层也是所有结点的度都是2，则为满二叉树。

二叉树的遍历：

1.前序遍历：对于二叉树的每个结点，都是先访问根节点，再访问其左子树，访问完再访问右子树。前序遍历可以用于深度搜索

2.中序遍历：对于二叉树的每个结点，都是先访问其左子树，再访问根节点，访问完再访问右子树。中序遍历就是把二叉树的每个结点垂直投影到同一水平的序列。

3.后序遍历：对于二叉树的每个结点，都是先访问其左子树，再访问访问右子树，访问完再访问根节点。

4.层序遍历：一层一层的访问，每一层都是先访问左侧的结点再访问右侧的。层序遍历可以用于广度搜索

知道前序遍历和后序遍历的其中一个结果，再知道中序遍历的结果，可以唯一确定一颗二叉树，但只知道前序遍历和后序遍历的结果不能唯一确定。

求树的深度：

思路：化成求子树的深度，找出其中的最大值，再加上根节点这一层（即加1），就是当前结点的深度。

int maxdepth(TNode *root)
{if(root==NULL)
{return 0;
}return max(maxdepth(root->left),maxdepth(root->right))+1;}

求结点的个数：

思路：对于每个结点，求左子树的结点的个数和右子树的结点的个数，再加上根节点，就是以当前结点为根的树的结点的个数。

 

int Nodenum(Node*root)
{if(root==NULL){return 0;}return Nodenum(root->left)+Nodenum(root->right)+1;}

求叶子结点的个数：

思路：对每个结点，判断其是不是叶子结点，若不是则找左子树和右子树的叶子结点的个数，若是则返回1.

int NodeLeaveNum(Node*root)
{if(root==NULL)return 0;if(root->left==NULL&&root->right==NULL)return 1;return  NodeLeaveNum(root->left)+ NodeLeaveNum(root->right);}

求第k层结点的个数：

思路：对于第m层的结点找第n层，就是第m层的子节点找第n-1层。

int NodeKNum(Node*root, int k)
{if(root==NULL)return 0;if(k==1)return 1;
//上述两个判断位置不能颠倒，否则会出错return  NodeKNum(root->left,k-1)+ NodeKNum(root->right,k-1);}