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