开胃前菜 基础概念选择题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
   A 不存在这样的二叉树
   B 200
   C 198
   D 199

度为0的比度为2的永远多一个（任何二叉树都满足）
叶子结点的度为0，所以：199+1

2. 下列数据结构中，不适合采用顺序存储结构的是（ ）
   A 非完全二叉树
   B 堆
   C 队列
   D 栈

3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
   A n
   B n+1
   C n-1
   D n/2

n0+n2+n1 = 2n
n0+n0-1+n1 = 2n
2*n0-1+n1 = 2n
n1是0或者1，这里n1只能是1，不然算出的是小数

4. 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
   A 11
   B 10
   C 8
   D 12

高度为h的完全二叉树，节点范围是：[2^(h-1),2h-1]
这里算的是下限

5. 一个具有767个节点的完全二叉树，其叶子节点个数为（）
   A 383
   B 384
   C 385
   D 386

n0+n2+n1 = 767
n0+n0-1+n1 = 767
2*n0-1+n1 = 767
n1是0或者1，但这里767是一个奇数所以n1只能取0

---

 

主菜 二叉树oj题

1.单值二叉树

题目

LeetCode

 

思路1+代码

遍历，拿一个基准值去和树里的每一个值去比较

bool flag = true;
void PreOrderCompare(struct TreeNode* root, int val)
{if (root == NULL || flag == false)return;if (root->val != val){flag = false;return;}PreOrderCompare(root->left, val);PreOrderCompare(root->right, val);
}bool isUnivalTree(struct TreeNode* root){`在这里插入代码片`if (root == NULL)return true;flag = true;PreOrderCompare(root, root->val);return flag;
}

 

思路2+代码

分别用每个结点与他们的孩子相比较

bool isUnivalTree(struct TreeNode* root){if (root == NULL)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);
}

 

递归展开图

注意：递归中返回不是直接返回到最外面，是返回上一层
 

2. 检查两颗树是否相同

题目

LeetCode

 

代码

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. 对称二叉树

题目

LeetCode

 

思路+代码

bool isSymmetricSubTree(struct TreeNode* root1, struct TreeNode* root2)
{if(root1 == NULL && root2 == NULL)return true;if(root1 == NULL || root2 == NULL)return false;if(root1->val != root2->val)return false;return isSymmetricSubTree(root1->left,root2->right) && isSymmetricSubTree(root1->right,root2->left);}bool isSymmetric(struct TreeNode* root){if(root == NULL)return true;return isSymmetricSubTree(root->left,root->right);
}

 

4. 二叉树的前序遍历

题目

LeetCode

代码

int TreeSize(struct TreeNode* root){return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void preorder(struct TreeNode* root,int* a,int* pi){if(root == NULL)return;a[(*pi)++] = root->val;preorder(root->left,a,pi);preorder(root->right,a,pi); }int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize = TreeSize(root);int* a = (int*)malloc(*returnSize * sizeof(int));int i  = 0;preorder(root,a,&i);return a;}

 

5. 另一颗树的子树

LeetCode
有点难度

 

思路+代码

把原树中所有子树都找出来与subRoot比较

怎么找出所有子树？
遍历
每个结点都是一个子树的根

 //查找相同的树
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;//遍历，跟root中所有子树都比较一遍
if(isSameTree(root,subRoot))
return true;return  isSubtree(root->left,subRoot)|| isSubtree(root->right,subRoot);}

 

6.二叉树遍历

题目

遍历

 

代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreateTree(char* str,int* pi)
{if(str[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = BuyNode(str[(*pi)++]);root->left = CreateTree(str,pi);root->right = CreateTree(str,pi);return root;
}void InOrder(BTNode* root)
{if(root == NULL)return;InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}int main()
{
char str[100];scanf("%s",str);int i = 0;BTNode* root = CreateTree(str, &i);InOrder(root);return 0;}

 

7.二叉树的层序遍历

准备环节

层序遍历需要用到队列，可以找之前写过的队列代码拷贝一份，添加现有项
包含一下队列的头文件就可以使用了

但有个小问题: 之前队列里面的数据类型是整数，层数遍历里面存的是结点（结构体）
所以得把typedef int* QDataType; 整型
改为typedef BTNode* QDataType; 结点

如果报错还得在typedef之前加一个前置声明
struct BinaryTreeNode;
 

代码实现

void leveIOrder(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");QueueDestroy(&q);
}

 

8.判断二叉树是否是完全二叉树

思路+代码

用层序遍历的方法最简单

int BinaryTreeComplete(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){QueuePush(&q, front->left);QueuePush(&q,front->right);}else{//遇到null以后就跳出break;}}//如果后面全是null，则是完全二叉树//如果null后面还有非空，则不是完全二叉树while(!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){ QueueDestroy(&q); return false;}}  QueueDestroy(&q); return true;
}