网站icp备案咋做,营销型类型网站多少钱些,网站建设邮,东莞网站建没创作不易#xff0c;感谢三连#xff01;#xff01;
一、选择题
1、某二叉树共有 399 个结点#xff0c;其中有 199 个度为 2 的结点#xff0c;则该二叉树中的叶子结点数为#xff08; #xff09; A.不存在这样的二叉树 B.200 C.198 D.199解析#xff1a;选B感谢三连
一、选择题
1、某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A.不存在这样的二叉树 B.200 C.198 D.199解析选B根据n0n21的结论这个结论不清楚的看博主的关于二叉树概念的文章有证明就是度为0的节点始终比度为2的节点多一个所以这题就很显然选B了
2、在具有 2n 个结点的完全二叉树中叶子结点个数为
A n B n1 C n-1 D n/2解析选A 原因如下 3、一棵完全二叉树的节点数位为531个那么这棵树的高度为 A 11 B 10 C 8 D 12解析选B根据结论——满二叉树的节点N数量2^h-1,如果高度为8那么节点最多有255个当高度为10时节点最多有1023个所以高度只能是10
4、一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386解析选B因为度为2的节点数肯定并度为0的节点数少1个所以n0和n2一个是奇数一个是偶数所以n1只能是偶数又因为完全二叉树n1只有可能是0或者1所以n1只能取0所以n0384n2383
5、一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为。 A(11 5 7 2 3 17) B(11 5 7 2 17 3) C(17 11 7 2 3 5) D(17 11 7 5 3 2) E(17 7 11 3 5 2) F(17 7 11 3 2 5)解析选C 先画出来再不断向下调整 6、最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后其结果是 A[3257468] B[2357468] C[2345786] D[2345678] 解析选C还是画出来再调整
二、单值二叉树
OJ单值二叉树 bool isUnivalTree(struct TreeNode* root)
{if(rootNULL)//abac-bcreturn true;if(root-leftroot-left-val!root-val)return false;if(root-rightroot-right-val!root-val)return false;return isUnivalTree(root-left)isUnivalTree(root-right);
}
三、检查两棵树是否相同
OJ判断两棵树是否相同 这个在博主讲解二叉树链式存储中有仔细分析过了
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if(pNULLqNULL)return true;if(pNULL||qNULL)return false;if(p-val!q-val)return false;//此时得到的节点存在且节点值相同的情况return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}
四、对称二叉树 OJ对称二叉树 bool _isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot)
{//都为空对称if(leftrootNULLrightrootNULL)return true;//一个为空一个不为空不对称if(leftrootNULL||rightrootNULL)return false;//都不为空就可以看值了如果值不相等不对称if(leftroot-val!rightroot-val)return false;//此时都不为空且值相等就走递归找下一个//左树的左子树要跟右树的右子树相比//左树的右子树要跟右树的左子树相比return _isSymmetric(leftroot-left,rightroot-right)_isSymmetric(leftroot-right,rightroot-left);
}bool isSymmetric(struct TreeNode* root)
{if(rootNULL)return true;//根不对称就去找左右子树比 相当于是拆成两棵树的了return _isSymmetric(root-left,root-right);
}
五、二叉树的前序遍历
OJ二叉树的前序遍历 int TreeSize(struct TreeNode* root)
{return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;
}
void _preorder(struct TreeNode* root,int *a,int *i)
{if(rootNULL)return ;a[(*i)]root-val;_preorder(root-left,a,i);_preorder(root-right,a,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//returnsize是结点数*returnSizeTreeSize(root);int *a(int *)malloc(*returnSize*sizeof(int));int i0;_preorder(root,a,i);return a;
} 六、二叉树的中序遍历
OJ二叉树的中序遍历 int i0;int TreeSize(struct TreeNode* root)
{return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;
}
void _inorderTraversal(struct TreeNode* root,int *a)
{if(rootNULL)return ;_inorderTraversal(root-left,a);a[i]root-val;_inorderTraversal(root-right,a);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{//returnsize是结点数*returnSizeTreeSize(root);int *a(int *)malloc(*returnSize*sizeof(int));i0;//全局变量一定要记得赋0_inorderTraversal(root,a);//必须构造新函数去递归因为在原函数递归会不断创建新的数组return a;
}
注这题跟上题是差不多的我稍微改了一下这里数组的下标我不用指针去接受参数了而是直接设置一个全局变量i要注意的是因为力扣的测试可能会多次调用这个函数所以我们一定要在递归函数运行前让i0否则就会i就会一直叠加下去导致越界 还有一个注意事项就是这里千万不要使用静态的局部变量虽然他也同样可以在函数栈帧销毁时不被释放但是他的作用域很小不能让我们在主函数中让i0
但是尽量少使用全局变量
七、二叉树的后序遍历
OJ二叉树的后序遍历 void _postorder(struct TreeNode* root,int *arr,int *arrsize)
{if(rootNULL)return;_postorder(root-left,arr,arrsize);_postorder(root-right,arr,arrsize);arr[(*arrsize)]root-val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize)
{int *arr(int*)malloc(100*sizeof(int));*returnSize0;_postorder(root,arr,returnSize);return arr;
} 注这题和前两题差不多但是又进行了改进我们发现了题目的一个条件 也就是说我们动态开辟100个空间的话是绝对不会越界的所以就不需要通过自己封装一个treesize函数来计算节点个数数量了 那我们要怎么去让returnsize返回节点个数的值的方法就是把*returnsize初始化为0作为下标每次放进一个值的时候*returnsize就会一次当后序遍历结束的时候returnsize恰好又多了一次正好表示节点个数的数量
八、另一颗树的子树
OJ另一颗树的子树 bool isSametree(struct TreeNode* p,struct TreeNode* q)//比较两个树的递归函数
{if(pNULLqNULL)return true;if(pNULL||qNULL)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(rootNULL)return false;//为空就不比较的因为subRoot是至少有一个节点的。if(isSametree(root,subRoot))return true;return isSubtree(root-left, subRoot)||isSubtree(root-right, subRoot);//左子树和右子树只要有一个找到了就返回true
} 关键就是我们每遍历到一个节点都要尝试把他往下遍历去和另外一个子树进行比较所以单独封装了一个比较两个树是否相同的函数该树每遍历一次节点就去调用一次最后在用||操作符因为左子树和右子树只要有一个找到就可以了
九、二叉树的构建及遍历
OJ二叉树的构建及遍历 typedef char BTDataType;
typedef struct BTtreeNode
{BTDataType val;struct BTtreeNode*left;struct BTtreeNode*right;
}BTtreeNode;BTtreeNode* BuyNode(BTDataType x)
{BTtreeNode*newnode(BTDataType*)malloc(sizeof(BTDataType));newnode-leftnewnode-rightNULL;newnode-valx;if(newnodeNULL){perror(malloc fail);exit(1);}return newnode;
}BTtreeNode* CreateTree(BTDataType*a,int *pi)
{if(a[*pi]#){(*pi);return NULL;}BTtreeNode*rootBuyNode(a[(*pi)]);root-leftCreateTree(a,pi);root-rightCreateTree(a,pi);return root;
}void InOrder(BTtreeNode*root)
{if(rootNULL)return;InOrder(root-left);printf(%c ,root-val);InOrder(root-right);
}int main()
{char arr[100];scanf(%s,arr);int i0;BTtreeNode*rootCreateTree(arr,i);InOrder(root);printf(\n);return 0;
}
这题就是将二叉树的构建和链式结构的中序遍历结合起来了
