普通二叉树
我们之前讲过完全二叉树的应用：【堆的数据结构】，在次我们使用的是顺序表来存储完全二叉树；
但是对于普通的二叉树，是不建议使用顺序表的结构来存储的，会浪费空间，所以，我们搞出了一个链式存储结构来存储普通二叉树；
对于普通二叉树我们需要明白几点：
- 普通二叉树的增删查改是没有任何意义的，因为普通二叉树增删查改的结构过于复杂，没有必要一定要用二普通二叉树的方式去增删查改；
- 对于普通二叉树我们需要关注的问题是：遍历普通二叉树的结构问题，前中后层次遍历，关注这个问题的意义所在也是：第一为以后学习更加复杂的二叉排序树，AVL树，红黑树，B树做准备；第二也就是为了刷刷OJ题；因为OJ题关于二叉树的问题还是蛮多的；
- 只有给普通二叉树加以一些性质的基础上，增删查改次啊有意义，比如二叉搜索树，AVL树等；
二叉树的遍历
遍历就是全部的结点都访问一遍，很自然的二叉树的遍历也是所有二叉树的结点都访问一遍；
二叉树的遍历需要关注三个结点：根结点，左子树结点，右子树结点；
这次以不同的视角理解以下二叉树的前序遍历,让你正真的吃透它；我们知道**前序遍历就是 先访问根，再访问左子树，再访问右子树，而中序就是先：左子树再根再右子树；后序就是先左再右后根；**我们之前学习遍历都是不画出NULL的，这次我们把NULL也画出来，这样才可以体会二叉树的遍历精髓所在！
假如我们有如上图的二叉树，用前序遍历和中序和后序遍历把NULL 画出来的结果是什么呢？
前序遍历：
中序遍历：
后序遍历：
二叉树遍历代码实现
要遍历二叉树，首先得有二叉树的存储结构，还要有二叉树，我们一直都没有创建出二叉树的模样，所以我们首先得创建二叉树出来，再进行遍历；
由于二叉树得创建并不是重点：所以我们使用了一种非常暴力的创建方式，具体如下：
创建二叉树：
typedef char BTDateType;
typedef struct BinaryTreeNode
{
BTDateType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDateType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->data = x;
node->left = node->right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
//主程序
int main()
{
BTNode* root = CreatBinaryTree();
//开始前序
//****
//开始中序
//****
//开始后序
//****
return 0;
}
创建好二叉树开始前序遍历代码：
void PreOrder(BTNode* root)
{
if(root == NULL)
{
printf("NULL ");
return;
}
printf("%c ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
前序遍历很简单，我们再为空时候，打印了NULL，便于观察结果
结果很正确嘛！
中序遍历：
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
后序遍历：
//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
理解递归遍历二叉树的调用过程
示例前序遍历的递归理解！！你把代码写出来，一个步骤一个步骤的走，去调用，去返回，这样来理解；
求二叉树的结点个数
首先我们来看看一个计数的方式，能否求得二叉树结点个数
**思路：当我在递归遍历二叉树时候，同时用一个计数变量count去记录遍历过得结点，就可以得到二叉树得结点个数。**但是是否可行呢？
//计数方式求二叉树得结点个数，！！！！！不可行！！！
//不可行得原因就是递归遍历是每个函数调用都有自己得栈帧的，每个栈帧都是独立的
//所以说这个count再每个递归遍历过程中，是没有联系的，最终结果只能是count = 1;
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int count = 0;
count++;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return count;
}
那这么说：是否可以设置一个静态遍历呢？staitc int count； 这样 count 就不会因为栈帧的问题而影响了.
但是是否可以行呢？
//这种方式也是不可以的，为什么？因为假如我调用不是一次这个函数呢？
//结果就会翻倍了，因为这个count在外面调用结束时候，count还没有销毁
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
static int count = 0;
count++;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return count;
}
上面的方式都不行，但是我们可以在main设置一个变量，把变量地址传递过去，给函数，函数设置一个形参指针变量，去保持函数里面的值返回给外面；
因为在main函数的变量的栈帧和在递归函数里面的栈帧不一样，所以可以这么做；
void BinaryTreeSize(BTNode* root,int* pn)
{
if (root == NULL)
{
return ;
}
++(*pn);
BinaryTreeSize(root->left,pn);
BinaryTreeSize(root->right, pn);
}
其实上面的方式都不是最好的：
最好的是直接递归返回就行！
//计算二叉树结点个数的方式
int BinaryTreeSize(BTNode* root)
{
if (NULL == root)
{
return 0;
}
//递归返回左子树的节点个数加上右子树的结点个数和根的个数
return BinaryTreeSize(root->right) + BinaryTreeSize(root->left) + 1;
}
求二叉树的叶子结点
求二叉树的叶子结点也可以用递归的思路思考：
当root为空，直接返回0，表示叶子结点为0；
当root只有根结点，直接返回1，表示叶子结点就是根结点；
其他情况，直接计算左子树的叶子结点+右子树的叶子结点即可。
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
//只有一个根结点的表示形式
if (root->left == NULL || root->right == NULL)
return 1;
int leftLeaf = BinaryTreeLeafSize(root->left);
int rightLeaf = BinaryTreeLeafSize(root->right);
return leftLeaf + rightLeaf;
}
求二叉树的第K层节点个数
当树为空时候，直接返回0；
当k == 1时候表示只有一层，那只能是根结点，直接返回1；
其他情况就是第k层结点数=第k-1层的左子树的结点数+第k层右子树的结点树之和；
//求二叉树的第k层结点个数
int BinaryTreeLevelKSize(BTNode* root,int k)
{
if (root == NULL) return 0;
if (k == 1) return 1;
return BinaryTreeLevelKSize(root->left, k - 1) +
BinaryTreeLevelKSize(root->right, k - 1);
}
求二叉树的深度或者高度
当树为空时候，直接返回；
当树不为空时候，树的深度 = max（左子树的深度，右子树的深度）+根的结点；
//求二叉树的深度或者高度
int BinaryDepth(BTNode* root)
{
if (root == NULL) return 0;
int LeftDepth = BinaryDepth(root->left);
int rightDepth = BinaryDepth(root->right);
return LeftDepth > rightDepth ? LeftDepth + 1 : rightDepth + 1;
}
在二叉树查找x值，返回结点
当树为空时候，不用找；
当树为根结点，判断根节点的值是否和x相等；
其他情况去左子树找，判断是否找到，找到就返回；再去右树找，找到就返回；假如左子树右子树都没找到，直接返回空；
常见的错误代码分析
//二叉树查找结点x的值
BTNode* BinaryTreeFind(BTNode* root,int x)
{
if (root == NULL) return NULL;
if (root->data == x) return root;
BinaryTreeFind(root->left, x);
BinaryTreeFind(root->right, x);
}
这段代码很明显会有错误！以为直接找左树和右树就可以了，可是写这个代码时候，忽略了递归返回只会返回到上一层调用它的地方，不会直接返回到刚开始调用的地方，这样就会导致返回到上一层时候，如果返回的是NULL的那么就会问题；
正确的代码
//二叉树查找结点x的值
BTNode* BinaryTreeFind(BTNode* root,int x)
{
if (root == NULL) return NULL;
if (root->data == x) return root;
BTNode* left = BinaryTreeFind(root->left, x);
if (left)
return left;
BTNode* right = BinaryTreeFind(root->right, x);
if (right)
return right;
return NULL;
}