创作不易，感谢三连！！
一、选择题
1、某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A.不存在这样的二叉树
B.200
C.198
D.199
解析：选B，根据n0=n2+1的结论（这个结论不清楚的看博主的关于二叉树概念的文章有证明），就是度为0的节点始终比度为2的节点多一个，所以这题就很显然选B了！！
2、在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
解析：选A ，原因如下
3、一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
解析：选B，根据结论——满二叉树的节点N数量=2^h-1,如果高度为8，那么节点最多有255个，当高度为10时，节点最多有1023个，所以高度只能是10
4、一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
解析：选B，因为度为2的节点数肯定并度为0的节点数少1个，所以n0和n2一个是奇数一个是偶数，所以n1只能是偶数，又因为完全二叉树n1只有可能是0或者1，所以n1只能取0，所以n0=384，n2=383
5、一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为（）。
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
解析：选C 先画出来，再不断向下调整
6、最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]
解析：选C，还是画出来再调整 
二、单值二叉树
bool isUnivalTree(struct TreeNode* root) { if(root==NULL)//a==b，a==c，->b==c return true; if(root->left&&root->left->val!=root->val) return false; if(root->right&&root->right->val!=root->val) return false; return isUnivalTree(root->left)&&isUnivalTree(root->right); }
三、检查两棵树是否相同
这个在博主讲解二叉树链式存储中有仔细分析过了！！
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); }
四、对称二叉树
bool _isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot) { //都为空，对称 if(leftroot==NULL&&rightroot==NULL) return true; //一个为空一个不为空，不对称 if(leftroot==NULL||rightroot==NULL) return false; //都不为空，就可以看值了，如果值不相等，不对称 if(leftroot->val!=rightroot->val) return false; //此时都不为空，且值相等，就走递归找下一个 //左树的左子树要跟右树的右子树相比 //左树的右子树要跟右树的左子树相比 return _isSymmetric(leftroot->left,rightroot->right)&& _isSymmetric(leftroot->right,rightroot->left); } bool isSymmetric(struct TreeNode* root) { if(root==NULL) return true; //根不对称，就去找左右子树比 相当于是拆成两棵树的了 return _isSymmetric(root->left,root->right); }
五、二叉树的前序遍历
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } void _preorder(struct TreeNode* root,int *a,int *i) { if(root==NULL) return ; a[(*i)++]=root->val; _preorder(root->left,a,i); _preorder(root->right,a,i); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { //returnsize是结点数 *returnSize=TreeSize(root); int *a=(int *)malloc(*returnSize*sizeof(int)); int i=0; _preorder(root,a,&i); return a; }
六、二叉树的中序遍历
int i=0; int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } void _inorderTraversal(struct TreeNode* root,int *a) { if(root==NULL) return ; _inorderTraversal(root->left,a); a[i++]=root->val; _inorderTraversal(root->right,a); } int* inorderTraversal(struct TreeNode* root, int* returnSize) { //returnsize是结点数 *returnSize=TreeSize(root); int *a=(int *)malloc(*returnSize*sizeof(int)); i=0;//全局变量一定要记得赋0 _inorderTraversal(root,a);//必须构造新函数去递归，因为在原函数递归会不断创建新的数组 return a; }
注：这题跟上题是差不多的，我稍微改了一下，这里数组的下标我不用指针去接受参数了，而是直接设置一个全局变量i！！要注意的是，因为力扣的测试可能会多次调用这个函数，所以我们一定要在递归函数运行前让i=0！！否则就会i就会一直叠加下去导致越界！！ （还有一个注意事项就是，这里千万不要使用静态的局部变量，虽然他也同样可以在函数栈帧销毁时不被释放，但是他的作用域很小，不能让我们在主函数中让i=0）
但是尽量少使用全局变量！！
七、二叉树的后序遍历
void _postorder(struct TreeNode* root,int *arr,int *arrsize) { if(root==NULL) return; _postorder(root->left,arr,arrsize); _postorder(root->right,arr,arrsize); arr[(*arrsize)++]=root->val; } int* postorderTraversal(struct TreeNode* root, int* returnSize) { int *arr=(int*)malloc(100*sizeof(int)); *returnSize=0; _postorder(root,arr,returnSize); return arr; }
注：这题和前两题差不多，但是又进行了改进，我们发现了题目的一个条件
也就是说我们动态开辟100个空间的话是绝对不会越界的，所以就不需要通过自己封装一个treesize函数来计算节点个数数量了！！ 那我们要怎么去让returnsize返回节点个数的值的？？方法就是把*returnsize初始化为0作为下标，每次放进一个值的时候*returnsize就会++一次，当后序遍历结束的时候，returnsize恰好又多+了一次，正好表示节点个数的数量！！
八、另一颗树的子树
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); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root==NULL) return false;//为空就不比较的，因为subRoot是至少有一个节点的。 if(isSametree(root,subRoot)) return true; return isSubtree(root->left, subRoot)||isSubtree(root->right, subRoot); //左子树和右子树只要有一个找到了，就返回true }
关键就是我们每遍历到一个节点，都要尝试把他往下遍历去和另外一个子树进行比较！！所以单独封装了一个比较两个树是否相同的函数，该树每遍历一次节点就去调用一次，最后在用||操作符，因为左子树和右子树只要有一个找到就可以了！！
九、二叉树的构建及遍历
typedef char BTDataType; typedef struct BTtreeNode { BTDataType val; struct BTtreeNode*left; struct BTtreeNode*right; }BTtreeNode; BTtreeNode* BuyNode(BTDataType x) { BTtreeNode*newnode=(BTDataType*)malloc(sizeof(BTDataType)); newnode->left=newnode->right=NULL; newnode->val=x; if(newnode==NULL) { perror("malloc fail"); exit(1); } return newnode; } BTtreeNode* CreateTree(BTDataType*a,int *pi) { if(a[*pi]=='#') { (*pi)++; return NULL; } BTtreeNode*root=BuyNode(a[(*pi)++]); root->left=CreateTree(a,pi); root->right=CreateTree(a,pi); return root; } void InOrder(BTtreeNode*root) { if(root==NULL) return; InOrder(root->left); printf("%c ",root->val); InOrder(root->right); } int main() { char arr[100]; scanf("%s",arr); int i=0; BTtreeNode*root=CreateTree(arr,&i); InOrder(root); printf("\n"); return 0; }
这题就是将二叉树的构建和链式结构的中序遍历结合起来了！！
