抱怨是一件最没意义的事情。如果实在难以忍受周围的环境，那就暗自努力练好本领，然后跳出那个圈子。
目录
🎄二叉树
✔二叉树的结构：
✔BuyNode(创建二叉树节点)：
🎄基本函数操作：
✔PreOrder(前序递归遍历)：
✔InOrder(中序递归遍历)：
✔PostOrder(后序递归遍历)：
✔TreeSize(函数结点个数)：
✔TreeleafSize(叶子结点个数)：
✔TreeHeight(树的深度/高度)：
✔TreeKLevelSize(第k层的结点个数)：
✔TreeFind(二叉树查找值为x的值)：
✔LevelOrder(层序遍历)：
✔TreeComplete(判断二叉树是否是完全二叉树):
✔TreeDestory(二叉树销毁)：
🎄二叉树
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
✔二叉树的结构：
二叉树是一个节点root，链接着一个左节点left和一个右节点right
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
✔BuyNode(创建二叉树节点)：
BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail:"); exit(-1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; }
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树 操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
//构造二叉树 BTNode* n1 = BuyNode(1); BTNode* n2 = BuyNode(2); BTNode* n3 = BuyNode(3); BTNode* n4 = BuyNode(4); BTNode* n5 = BuyNode(5); BTNode* n6 = BuyNode(6); BTNode* n7 = BuyNode(7); n1->left = n2; n1->right = n4; n2->left = n3; n3->left = n7; n4->left = n5; n4->right = n6;
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
🎄基本函数操作：
再看二叉树基本操作前，再回顾下二叉树的概念，
二叉树是：
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。
✔PreOrder(前序递归遍历)：
前序遍历是每颗子树都先遍历root节点，再遍历左子树，最后在遍历右子树。
前序遍历：root 左子树 右子树
// 二叉树前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
✔InOrder(中序递归遍历)：
中序遍历是每颗子树都先遍历左子树，再遍历root节点，最后在遍历右子树。
中序遍历：左子树 root 右子树
// 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
✔PostOrder(后序递归遍历)：
后序遍历是每颗子树都先遍历左子树，再遍历右子树，最后在遍历root节点。
后序遍历：左子树 右子树 root
// 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
✔TreeSize(函数结点个数)：
二叉树节点的个数，可以看成左子树的节点个数+右子树的节点个数+1（根节点）。
遇到NULL返回0。
//返回二叉树的结点个数 int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }
✔TreeleafSize(叶子结点个数)：
叶节点代表它没有左右节点了，也就是左右节点皆为NULL
- 当左右左右节点皆为NULL时返回1
- 叶节点数等于左子树的叶子个数+右子树的叶子个数
//返回叶子结点个数 int TreeleafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeleafSize(root->left) + TreeleafSize(root->right); }
✔TreeHeight(树的深度/高度)：
当只有一层的时候，左子树为0，右子树为0层，总层数为 1层。
当有2层时，左子树为1，右子树为1层，总层数为1+1层。
当有3层时，左子树为2，右子树为2层，总层数为2+1层。
....
当有N层时，左子树为N-1层，右子树为N1层，总层数为（N-1）+1层。
这样就可以将树的高度看成较高子树的层高+1（根节点的那一层）。因此将左右子树的层数计算出来，让他们较大的一个+1就是二叉树的高度了。
//返回树的深度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int leafHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); return leafHeight > rightHeight ? leafHeight + 1 : rightHeight + 1; }
✔TreeKLevelSize(第k层的结点个数)：
可以通过左右子树，让他们可下降k-1层，k-1层的左孩子与右孩子树就是第k层的结点数
如果k==1,则返回1
如果为NULL，就返回0
//第k层的结点个数 k >= 1 int TreeKLevelSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1) return 1; return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); }
✔TreeFind(二叉树查找值为x的值)：
依旧不断通过左子树和右子树分别遍历下去
找到等于x的值，就返回那个结点
遇到NULL时，返回NULL
当全部找完依旧没找到，那就返回NULL。
//二叉树查找值为x的值 BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* ret1 = TreeFind(root->left, x); if (ret1) return ret1; BTNode* ret2 = TreeFind(root->right, x); if(ret2) return ret2; return NULL; }
✔LevelOrder(层序遍历)：
这里需要用到队列，队列详细讲解：http://t.csdn.cn/vhPtL
- 先让根节点进入队列
- 将队头用一个变量保存下来，如果不为NULL就将其打印
- 再将队头pop一下
- 当左右节点存在，就将其push进去队列，以此循环
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); printf("%d ", front->data); QueuePop(&q); if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } printf("\n"); QueueDestroty(&q); }
✔TreeComplete(判断二叉树是否是完全二叉树):
这个是建立在层序遍历的基础上的，利用层序遍历，遍历到第一个NULL时，后面都不为NULL才为完全二叉树，如果后面有一个不为NULL，那就不是完全二叉树返回false。
// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front == NULL) { break; } else { QueuePush(&q,front->left); QueuePush(&q,front->right); } } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front != NULL) { QueueDestroty(&q); return false; } } QueueDestroty(&q); return true; }
✔TreeDestory(二叉树销毁)：
// 二叉树销毁 void TreeDestory(BTNode* root) { if (root == NULL) return; TreeDestory(root->left); TreeDestory(root->right); free(root); }
