如何完美吃下二叉树？——二叉树练习题

文章目录

开胃前菜 基础概念选择题

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

度为0的比度为2的永远多一个

（任何二叉树都满足）
叶子结点的度为0，所以：199+1

1. 下列数据结构中，不适合采用顺序存储结构的是（ ）A 非完全二叉树 B 堆 C 队列 D 栈
2. 在具有 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，不然算出的是小数

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

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

1. 一个具有767个节点的完全二叉树，其叶子节点个数为（） A 383B 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;voidPreOrderCompare(structTreeNode* 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(structTreeNode* root){`在这里插入代码片`
    if(root ==NULL)return true;

    flag = true;PreOrderCompare(root, root->val);return flag;}

思路2+代码

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

bool isUnivalTree(structTreeNode* 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;//递归 returnisUnivalTree(root->left)&&isUnivalTree(root->right);}

递归展开图

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

2. 检查两颗树是否相同

题目

LeetCode

代码

bool isSameTree(structTreeNode* p,structTreeNode* q){//两个都为空if(p ==NULL&& q ==NULL)return true;//两个都为空，至少一个不为空if(p ==NULL|| q ==NULL)return false;//两个不为空但值不相等if(p->val != q->val)return false;//递归returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

3. 对称二叉树

题目

LeetCode

思路+代码

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

bool isSymmetric(structTreeNode* root){if(root ==NULL)return true;returnisSymmetricSubTree(root->left,root->right);}

4. 二叉树的前序遍历

题目

LeetCode

代码

intTreeSize(structTreeNode* root){return root ==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}voidpreorder(structTreeNode* 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(structTreeNode* 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(structTreeNode* p,structTreeNode* q){//两个都为空if(p ==NULL&& q ==NULL)return true;//两个都为空，至少一个不为空if(p ==NULL|| q ==NULL)return false;//两个不为空但值不相等if(p->val != q->val)return false;//递归returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

bool isSubtree(structTreeNode* root,structTreeNode* subRoot){if(root ==NULL)return false;//遍历，跟root中所有子树都比较一遍if(isSameTree(root,subRoot))return true;returnisSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

6.二叉树遍历

题目

遍历

代码

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefchar BTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode* left;structBinaryTreeNode* 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)++;returnNULL;}
    BTNode* root =BuyNode(str[(*pi)++]);
    root->left =CreateTree(str,pi);
    root->right =CreateTree(str,pi);return root;}voidInOrder(BTNode* root){if(root ==NULL)return;InOrder(root->left);printf("%c ",root->data);InOrder(root->right);}intmain(){char str[100];scanf("%s",str);int i =0;
    BTNode* root =CreateTree(str,&i);InOrder(root);return0;}

7.二叉树的层序遍历

准备环节

层序遍历需要用到

队列

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

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

int*

QDataType;

整型 

改为typedef

BTNode*

QDataType;

结点

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

struct BinaryTreeNode;

代码实现

voidleveIOrder(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.判断二叉树是否是完全二叉树

思路+代码

用层序遍历的方法最简单

intBinaryTreeComplete(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;}