数据结构——二叉树练习题

目录

单值二叉树 

相同的树 

另一棵树的子树

二叉树的前序遍历

 二叉树的构造及遍历

给大家推荐一款刷题，找工作的好网站——牛客网

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

 

单值二叉树 

思路：根节点跟左子树比较，若相等则继续比，一值比到左子树为空，比完之后再跟右子树比较

 
bool isUnivalTree(struct TreeNode* root){
 if(root==NULL)
 return true;
 if(root->left&&root->val!=root->left->val)
 return false;
 if(root->right&&root->val!=root->right->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; //一个为空，一个不为空，则false
    if(p->val!=q->val)
    return false;//不相等，fasle
    return isSameTree(p->left,q->left)&&isSameTree(q->right,p->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(q->right,p->right);
 
}
 
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
 if(root==NULL)
 return false;
 if(isSameTree(root,subRoot))
 return true;
 return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

二叉树的前序遍历

思路：1.先统计出该二叉树节点的个数

            2.创建一个新的数组，数组大小为二叉树总结点大小

            3.进行前序遍历根，左，右

int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
} //统计个数
 void preorder(struct TreeNode* root,int *a,int *pi)
 {
     if(root==NULL)
     return;
    a[*pi]=root->val;
    (*pi)++;
    preorder(root->left,a,pi);
     preorder(root->right,a,pi);
 }//遍历
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize){
 int n=TreeSize(root);
 int *a=(int*)malloc(sizeof(int)*n);
 int i=0;
 preorder(root,a,&i);
 *returnSize=n;
 return a;
}

 二叉树的构造及遍历

 二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

1.建立一个数组，给数组输入数据，#代表NULL

2.构建一个二叉树，把数组的值输按前序遍历输入到二叉树中，当遇到#时，代表该节点为空

3.将前序遍历好的二叉树，进行中序遍历

#include<stdio.h>
#include<stdlib.h>
typedef char Datatypedef;
typedef struct BinaryTreeNode
{
    Datatypedef data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}TreeNode;//定义二叉树
 
TreeNode* CreateTree(char* arr, int* pi)
{
    if (arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
    tmp->data = arr[*pi];
    (*pi)++;
    tmp->left = CreateTree(arr, pi);
    tmp->right = CreateTree(arr, pi);
    return tmp;
}//创建二叉树，并把数组的值赋值给二叉树，按前序遍历赋值
 
void InorDer(TreeNode* tmp)
{
    if (tmp == NULL)
        return;
    InorDer(tmp->left);
    printf("%c ", tmp->data);
 
    InorDer(tmp->right);
}//前序遍历换为中序遍历
 
int main()
{
    char arr[100];
    scanf("%s", arr);
    int i = 0;
    TreeNode* root = CreateTree(arr, &i);
    InorDer(root);
    return 0;
}