怎么提高网站的权重帝国cms 商城网站视频教程
目录
一、二叉树的基本结构
二、二叉树的遍历
1.前序
2.中序
3.后序
4.层序遍历
三.计算二叉树的相关参数
1.计算节点总个数
2.计算叶子节点的个数
3.计算树的高度
4.计算第k层的子树个数
5.查找树中val为x的节点
四.刷题
1.单值二叉树
2.检查两棵树是否相同
3.一棵树是否对称
二叉树的实现源码_gitee
一、二叉树的基本结构
这里的二叉树比堆的定义更广泛，
heap=>完全二叉树/满二叉树
二叉树=>二叉，不成图（没有闭合圈）
二、二叉树的遍历
1.前序
NULL用‘#’表示，下面实例的val是char类型
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}这里使用的是递归式的遍历，因为二叉树可以看作根和子树，而子树又可以看作根和子树
注意，这里的return 是指返回上一层的递归，下面是部分运行逻辑
2.中序
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);}3.后序
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}4.层序遍历
这里要使用队列，先根节点入队，根节点出队后，对应的左右子树节点入队，左子树节点作为根节点出队，再有对应的左右子树节点入队，以此类推
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while(!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);printf("%c ", cur->_data);if (cur->_left)QueuePush(&q, cur->_left);if(cur->_right)QueuePush(&q, cur->_right);}}
这是带有换行效果的层序遍历，实现原理是需要记录每一层的个数，方便pop 完一层接一个换行
void BinaryTreeLevelOrder(BTNode* root)
{Queue Bq;QueueInit(&Bq);QueuePush(&Bq, root);int popnum = QueueSize(&Bq);while(!QueueEmpty(&Bq)){while(popnum--){BTNode* cur = QueueFront(&Bq);QueuePop(&Bq);printf("%c ", cur->_data);if(cur->_left!=NULL){QueuePush(&Bq, cur->_left);}if(cur->_right!=NULL){QueuePush(&Bq, cur->_right);}}popnum = QueueSize(&Bq);printf("\n");}}
三.计算二叉树的相关参数
1.计算节点总个数
思路1：遍历二叉树，不过要传入一个可以记录的参数，为了这个参数可以随遍历而变化，不能传入实参拷贝为形参这一套
解决方法：
1.使用static参数，在函数内定义，只要把static的值最后return,在全局则可以不用，直接查static的值，弊端：这个函数不能再同一个程序里重复调用，因为static的值不会再从0开始
2.在参数列表里多传入一个int *size,每次++时就（*size）++,在进入下一个递归
思路2：递归计数，
当root==NULL, return 0;
当root不为NULL时，return 1+左子树的个数+右子树的个数
int BinaryTreeSize(BTNode* root)
{
if(root==NULL)
{return 0;
}
return 1 + BinaryTreeSize(root->_right) + BinaryTreeSize(root->_left);}2.计算叶子节点的个数
思路：递归计数，叶子节点时左右子树都为NULL时，
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL) { return 0; }if(root->_left==NULL&&root->_right==NULL){return 1;}return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}3.计算树的高度
int nummax(int p1, int p2)
{return p1 > p2 ? p1 : p2;}
int tree_height(BTNode* root)
{if(root==NULL){return 0;}return 1 + nummax(height(root->_left),height(root->_right));}
4.计算第k层的子树个数
思路：距离root为k,那么距离root的下一层为k-1，当k==1时，就是递归到第k层了
root==NULL,return 0
root!=NULL&&k==1,return 1;
其他情况：return knum(root->left,k-1) + knum(root->right,k-1)
int knum(BTNode* root,int k)
{if(root==NULL){return 0;}if (k == 1){return 1;}return knum(root->left, k - 1) + knum(root->right, k - 1);}5.查找树中val为x的节点
思路:递归遍历+比较是否为x
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == x){return root; }BTNode* node1 = BinaryTreeFind(root->_left, x);if (node1) { return node1; }return BinaryTreeFind(root->_right, x);} 
6.判断是否为完全二叉树
思路：以层序遍历对二叉树进行收集(此时NULL也收入)，在每个节点开始pop时，判断是否为NULL，一旦为NULL,则跳出循环，开始判断NULL之后的队列是否全为NULL,
如果全为NULL==>是完全二叉树
如果不是==>不是
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);if (cur == NULL)break;QueuePush(&q, cur->_left);QueuePush(&q, cur->_right);}while (!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);if (cur != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;} 
四.刷题
1.单值二叉树
bool _isUnivalTree(struct TreeNode* root,int val)
{
if(root==NULL)
return true;if(root->val!=val)
return false;return _isUnivalTree(root->left,val)&&_isUnivalTree(root->right,val);}bool isUnivalTree(struct TreeNode* root) {int val=root->val;
return _isUnivalTree(root,val);}
2.检查两棵树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if (p == NULL && q == NULL)return true;
if(p==NULL||q==NULL)
return false;if(p->val!=q->val){return false;} return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);}3.一棵树是否对称
bool issame(struct TreeNode* p1, struct TreeNode* p2)
{if (p1 == NULL && p2 == NULL){return true;}if (p1 == NULL || p2 == NULL){return false;}if (p1->val != p2->val) { return false; }return issame(p1->left, p2->right)&&issame(p1->right, p2->left);
}
bool isSymmetric(struct TreeNode* root) {if(root==NULL){return true;}return issame(root->left, root->right);}