目录

一、二叉树遍历

       1、前序遍历：                 

动态图解析：

       2、中序遍历：

       3、后序遍历：

       4、层序遍历 （利用队列）

动态图解析：

二、统计二叉树的节点个数：

       1、二叉树总节点个数

       2、二叉树叶子节点个数

       3、二叉树第K层节点个数

三、查找二叉树中值为x的节点

四、代码总览：

一、二叉树遍历

      注： 由于二叉树结构的特殊性，我们采用递归的方式进行遍历。

       1、前序遍历：                 

         根节点 --> 左孩子节点 --> 右孩子节点

          一棵最基本的二叉树由一个根和左右两个孩子组成，而前序遍历的意思是：

          先遍历根节点，再遍历左孩子节点，再遍历右孩子节点 ，

          而且二叉树上的所有子树都要符合这种遍历的顺序 。

动态图解析：

//前序遍历：根左右
binary_node* Preorder(binary_node* root)
{if (root == NULL){printf("# ");return NULL;}printf("%d", root->data);Preorder(root->leftNode);	Preorder(root->rightNode);
}

       2、中序遍历：

          左孩子节点--> 根节点 --> 右孩子节点

          先遍历根左孩子节点，再遍历根节点，再遍历右孩子节点 ，

          而且二叉树上的所有子树都要符合这种遍历的顺序 。

//中序遍历
binary_node* Inorder(binary_node* root)
{if (!root)return;Inorder(root->leftNode);printf("%d ", root->data);Inorder(root->rightNode);
}

       3、后序遍历：

          左孩子节点--> 右孩子节点 --> 根节点

          先遍历左孩子节点，再遍历右孩子节点，再遍历根节点 

//后序遍历
binary_node* postorder(binary_node* root)
{if (!root)return;postorder(root->leftNode);postorder(root->rightNode);printf("%d ", root->data);
}

       4、层序遍历 （利用队列）

               从上到下 ；从左到右 依次遍历

将根节点入队列 >> 遍历根节点（根节点出队列）>> 根节点的孩子节点依次入队列  （以此类推）

动态图解析：

//层序遍历
void sequence(binary_node* root)
{if (!root)return;//创建队列binary_node** simuqueue = (binary_node**)malloc(sizeof(binary_node*));  int basei = 0;simuqueue[basei] = root;                      //根节点入队列for (int exporti = 0; exporti<=basei;){root = simuqueue[exporti];                //根节点出队列printf("%d ", (simuqueue[exporti++])->data);if (root->leftNode || root->rightNode)//队列扩容		simuqueue = realloc(simuqueue, sizeof(binary_node*)*(basei+3));  if((root->leftNode))               simuqueue[++basei] = root->leftNode;       //左孩子节点入队列if((root->rightNode))simuqueue[++basei] = root->rightNode;      //右孩子节点入队列}}

二、统计二叉树的节点个数：

       1、二叉树总节点个数

            方法一：定义一个全局变量用来计数，每次遍历，该变量++

            方法二：累加 函数返回值的方式 ，每遍历一个节点，返回值++

//统计二叉节点个数
int cont = 0, leafcont = 0;
int binary_size(binary_node* root)
{//if (!root)                  ______ 方法一：（全局变量）return;//cont++;//binary_size(root->leftNode);//binary_size(root->rightNode);//                            —————— 方法二：（函数返回值）if (!root)                   return 0;elsereturn 1 + binary_size(root->leftNode) + binary_size(root->rightNode);
}

       2、二叉树叶子节点个数

            判定条件：没有左右孩子节点   ，即为一个叶子节点。（不是叶子节点继续遍历）

//统计叶子节点个数
int binary_leafsize(binary_node* root)
{if (!root)return 0;if ((!root->leftNode)&&(!root->rightNode))    //--如果没有左右孩子return 1;                                 //--即为一个叶子节点else                                          //不是叶子节点继续遍历return  binary_leafsize(root->leftNode)+binary_leafsize( root->rightNode);}

       3、二叉树第K层节点个数

            利用函数传参，层层递减的方式，确定到第K层，利用返回值累加确定节点个数

（如：初始查找第三层：k = 3，每遍历到下一层，k - - ，当k =1 时, 即遍历到第三层 ）

//第k层节点个数
int binary_ksize(binary_node* root,int cont_k)
{if (!root)            //第k层没有节点 && 越界（k过大） 《==》 root == NULLreturn 0;if (1 == cont_k && root)      //遍历到 k 层并且有节点return 1;else if (cont_k > 1)          //尚未遍历到 k 层return binary_ksize(root->leftNode, cont_k - 1) + binary_ksize(root->rightNode, cont_k - 1);}

三、查找二叉树中值为x的节点

            依次遍历，比较值即可，（找到返回该节点地址，找不到返回NULL）

            注：要优化遍历次数，如：一条路径找到值后就无需再遍历其他节点了。

//查找二叉树中值为x的节点
binary_node* binary_find(binary_node* root,int x)
{if (!root)return NULL;if (root->data == x)return root;else{   //先遍历左孩子节点binary_node* tempL = binary_find(root->leftNode, x);if (tempL)return tempL;//左孩子节点找不到再找右孩子节点else if (tempL = binary_find(root->rightNode, x)){return tempL;}}
}

四、代码总览：

//前序遍历
binary_node* preorder(binary_node* root)
{if (!root)return;printf("%d ", root->data);preorder(root->leftNode);preorder(root->rightNode);
}
//中序遍历
binary_node* Inorder(binary_node* root)
{if (!root)return;Inorder(root->leftNode);printf("%d ", root->data);Inorder(root->rightNode);
}
//后序遍历
binary_node* postorder(binary_node* root)
{if (!root)return;postorder(root->leftNode);postorder(root->rightNode);printf("%d ", root->data);
}//统计二叉节点个数
int cont = 0, leafcont = 0;
int binary_size(binary_node* root)
{/*if (!root)return;cont++;binary_size(root->leftNode);binary_size(root->rightNode);*/if (!root)return 0;elsereturn 1 + binary_size(root->leftNode) + binary_size(root->rightNode);
}//统计叶子节点个数
int binary_leafsize(binary_node* root)
{/*if (!root)return;if ((!root->leftNode) && (!root->rightNode))leafcont++;binary_leafsize(root->leftNode);binary_leafsize(root->rightNode);*/if (!root)return 0;if ((!root->leftNode)&&(!root->rightNode))return 1;elsereturn  binary_leafsize(root->leftNode)+binary_leafsize( root->rightNode);}//第k层节点个数
int binary_ksize(binary_node* root,int cont_k)
{if (!root)            //第k层没有节点 && 越界 《==》 root == NULLreturn 0;if (1 == cont_k && root)      //遍历到 k 层并且有节点return 1;else if (cont_k > 1)return binary_ksize(root->leftNode, cont_k - 1) + binary_ksize(root->rightNode, cont_k - 1);}//统计二叉树层数
int binary_layers(binary_node* root)
{int layers = 0, temp = 0;if (!root)return 0;return 1+((layers = binary_layers(root->leftNode)) > (temp = binary_layers(root->rightNode)) ? layers : temp);
}//查找二叉树中值为x的节点
binary_node* binary_find(binary_node* root,int x)
{if (!root)return NULL;if (root->data == x)return root;else{binary_node* tempL = binary_find(root->leftNode, x);if (tempL)return tempL;else if (tempL = binary_find(root->rightNode, x)){return tempL;}}
}