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

开胃前菜 基础概念选择题

  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 11
    B 10
    C 8
    D 12

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

  1. 一个具有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;
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>