首页 > 其他分享 >TZOJ数据结构实验:树相同、左叶子和、倾斜度、直径、平衡二叉树、最小深度、层次构造二叉树

TZOJ数据结构实验:树相同、左叶子和、倾斜度、直径、平衡二叉树、最小深度、层次构造二叉树

时间:2023-02-20 15:24:38浏览次数:43  
标签:right return int 二叉树 倾斜度 TZOJ root left

5429数据结构实验:树是否相同

int isSameTree(struct TreeNode* p, struct TreeNode* q)//相同返回1,否则返回0
{
    if(p==NULL && q==NULL)return 1;
    if(p==NULL || q==NULL)return 0;
    return p->val==q->val && isSameTree(p->left,q->left) && isSameTree(p->right , q->right);
}

 

5430数据结构实验:左叶子之和

int s;
void dfs(struct TreeNode* root)
{
    if(!root)return ;
    if(root->left)
    {
        if(!root->left->left && !root->left->right)
            s+=root->left->val;
        dfs(root->left);
    }
    if(root->right)dfs(root->right);
}
int sumOfLeftLeaves(struct TreeNode* root)
{
    dfs(root);
    return s;
}

 

5432数据结构实验:二叉树倾斜度

求一棵二叉树的倾斜度,其中一个节点的倾斜度定义为“左子树元素之和”与“右子树元素之和”差的绝对值(空节点的元素值为0),二叉树的倾斜度定义为所有节点的倾斜度之和。

int sum;
void rfs(struct TreeNode* root,int *n)
{
    if(!root)return ;
    *n+=root->val;
    rfs(root->left,n);
    rfs(root->right,n);
} 
void dfs(struct TreeNode* root)
{
    if(!root)return;
    int n=0,m=0;
    rfs(root->left,&n);
    rfs(root->right,&m);
    sum+=abs(n-m);
    dfs(root->left);
    dfs(root->right);
}
int findTilt(struct TreeNode* root)//root为根结点指针,返回倾斜度之和
{
    dfs(root);
    return sum;
}

 

5433数据结构实验:二叉树的直径

求一棵二叉树的直径,即任意两个结点之间的路径长度最大值,路径可以经过根结点,父子节点之间的路径长度定义为1。

int maxn = 0;
int  Depth(struct TreeNode* root)
{
    if(!root)return 0;
    int ls = Depth(root->left);
    int rs = Depth(root->right);
    return ls>rs?(ls+1):(rs+1);
}
void dfs(struct TreeNode* root)
{
    if(!root)return ;
    int n = Depth(root->left),m = Depth(root->right);
    if(n+m>maxn)maxn = n+m;
    dfs(root->left);
    dfs(root->right);
}
int diameterOfBinaryTree(struct TreeNode* root)
{
    dfs(root);
    return maxn;
}

 

5435数据结构实验:对称二叉树

判断一棵二叉树是否关于根节点对称(镜像对称)。

比如下图中左边二叉树是对称的,右边则是非对称的。

int jud(struct TreeNode* l,struct TreeNode* r)
{
    if(!l && !r)return 1;
    if(!l || !r)return 0;
    if(l->val!=r->val)return 0;
    return jud(l->left,r->right) && jud(l->right,r->left);
}
int isSymmetric(struct TreeNode* root)//如果对称返回1,否则返回0
{
    if(!root)return 1;
    return jud(root->left , root->right);
}

 

5439数据结构实验:平衡二叉树

判断一棵二叉树是否是平衡二叉树。

平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树

int cal(struct TreeNode *root,int cnt)
{
    if(!root)return cnt;
    int l = cal(root->left,cnt+1);
    int r = cal(root->right,cnt+1);
    return r>l?r:l;
}
int isBalanced(struct TreeNode *root)//如果是平衡二叉树,返回1,否则返回0
{
    if(!root)return 1;
    int l = cal(root->left,1);
    int r = cal(root->right,1);
    if(l-r>1 || r-l>1)return 0;
    return isBalanced(root->left) && isBalanced(root->right);
}

 

5440数据结构实验:二叉树最小深度

求一棵二叉树的最小深度,即从根节点出发到叶子节点的最小路径上的节点数。

int min(int x,int y)
{
    if(x<y)return x;
    else return y;
}
int minDepth(struct TreeNode *root)
{
    if(root->val==NULL)return NULL;
    if(root->left==NULL && root->right==NULL)return 1;
    if(root->left==NULL)return minDepth(root->right)+1;
    if(root->right==NULL)return minDepth(root->left)+1;
    return min(minDepth(root->left),minDepth(root->right))+1;
}

 

以上是基于二叉树的各种应用,二叉树的层次构造如下

#include <stdio.h>
#include <stdlib.h>
 
struct TreeNode {
    int val;
    struct TreeNode *left,*right;
};
 
struct TreeNode a[520];
 
struct TreeNode* Creat(struct TreeNode* root)
{
    int k=0,i,j,n;
    while(scanf("%d",&n),n!=-1)
        a[k++].val=n;
    for(i=0,j=1;i<k;i++,j++)
    {
        if(i+j>=k||a[i+j].val==0) a[i].left=NULL;
        else a[i].left=&a[i+j];
        if(i+j+1>=k||a[i+j+1].val==0) a[i].right=NULL;
        else a[i].right=&a[i+j+1];
    }
    return &a[0];
}
int main()
{
    struct TreeNode* root=NULL;
    root=Creat(root);
    return 0;
}

 

标签:right,return,int,二叉树,倾斜度,TZOJ,root,left
From: https://www.cnblogs.com/jyssh/p/17137549.html

相关文章