[C]二叉树的实现——喵喵成长记

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

目录

前言

二叉树的定义

特殊的二叉树

二叉树的性质（超级重要）

代码实现

二叉树的练习题

总结

前言

二叉树用C语言实现，会加些习题进行巩固练习。那么，就让我们开始吧! 喵~

二叉树的定义

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

注意：

• 二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

以下图片的树都是二叉树哦

特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k，则它就是满二叉树。（满二叉树
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

如图所示：

二叉树的性质（超级重要）

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有n0＝n2＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)(ps：是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

• i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
• 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

代码实现

typedef char BTDataType;typedef struct BinaryTreeNode{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;}BTNode;// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);// 二叉树销毁void BinaryTreeDestory(BTNode** root);// 二叉树节点个数int BinaryTreeSize(BTNode* root);// 二叉树叶子节点个数int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层节点个数int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树查找值为x的节点BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root);// 二叉树中序遍历void BinaryTreeInOrder(BTNode* root);// 二叉树后序遍历void BinaryTreePostOrder(BTNode* root);// 层序遍历void BinaryTreeLevelOrder(BTNode* root);// 判断二叉树是否是完全二叉树int BinaryTreeComplete(BTNode* root);

#include "BTree.h"#include "queue.h" #include "stack.h"BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi){if (*pi >= n || src[*pi] == '#'){(*pi)++;return NULL;}BTNode * cur = (BTNode *)malloc(sizeof(BTNode));cur->_data = src[*pi];(*pi)++;cur->_left = BinaryTreeCreate(src, n, pi);cur->_right = BinaryTreeCreate(src, n, pi);return cur;}void BinaryTreePrevOrder(BTNode* root){if (root){putchar(root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}}void BinaryTreeInOrder(BTNode* root){if (root){BinaryTreeInOrder(root->_left);putchar(root->_data);BinaryTreeInOrder(root->_right);}}void BinaryTreePostOrder(BTNode* root){if (root){BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);putchar(root->_data);}}void BinaryTreeDestory(BTNode** root){if (*root){BinaryTreeDestory(&(*root)->_left);BinaryTreeDestory(&(*root)->_right);free(*root);*root = NULL;}}void BinaryTreeLevelOrder(BTNode* root){Queue qu;BTNode * cur;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_left){QueuePush(&qu, cur->_left);}if (cur->_right){QueuePush(&qu, cur->_right);}QueuePop(&qu);}QueueDestory(&qu);}int BinaryTreeComplete(BTNode* root){Queue qu;BTNode * cur;int tag = 0;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_right && !cur->_left){return 0;}if (tag && (cur->_right || cur->_left)){return 0;}if (cur->_left){QueuePush(&qu, cur->_left);}if (cur->_right){QueuePush(&qu, cur->_right);}else{tag = 1;}QueuePop(&qu);}QueueDestory(&qu);return 1;}

二叉树的练习题

965.单值二叉树

简单

197

相关企业

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回true；否则返回false。

示例 1：

输入：[1,1,1,1,1,null,1]输出：true

示例 2：

输入：[2,2,2,5,2]输出：false提示

1. 给定树的节点数范围是[1, 100]。
2. 每个节点的值都是整数，范围为[0, 99]。

   bool isUnivalTree(struct TreeNode* root){if(!root){return true;}if(root->left){if(root->val!=root->left->val || !isUnivalTree(root->left)){return false;}}if(root->right){if(root->val!=root->right->val || !isUnivalTree(root->right)){return false;}}return true;}

   ---

   100.相同的树

   简单

   1.1K

   相关企业

   给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。

   如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

   示例 1：

   

   输入：p = [1,2,3], q = [1,2,3]输出：true

   示例 2：

• 

  输入：p = [1,2], q = [1,null,2]输出：false

  示例 3：

  输入：p = [1,2,1], q = [1,1,2]输出：false

  提示：

• 

1. 两棵树上的节点数目都在范围[0, 100]内

• -104 <= Node.val <= 104

  bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL&&q==NULL)return true;else if(p==NULL||q==NULL){return false;}else if(p->val!=q->val){return false;}else{returnisSameTree(p->left,q->left)&& isSameTree(p->right,q->right);}}

  ---

  101.对称二叉树

  简单

  2.6K

  相关企业

  给你一个二叉树的根节点root， 检查它是否轴对称。

  示例 1：

• 

1. 输入：root = [1,2,2,3,4,4,3] 输出：true

2. 示例 2：

   

   输入：root = [1,2,2,null,3,null,3]输出：false

   提示：

3. 树中节点数目在范围[1, 1000]内
4. -100 <= Node.val <= 100

 bool check(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 check(p->left,q->right)&&check(p->right,q->left); else return false;}bool isSymmetric(struct TreeNode* root){ return check(root,root);}

总结

来嘛，来嘛，笑一个，今天的你也是超级赞滴，喵~

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。