小型电子商务网站规划,创建网页,如何从下载的视频查到原网站,如何在网站后台做网页目录
1.相同的树 2.二叉树中查找值为x的节点
3.单值二叉树
4.对称二叉树 5.二叉树的前序遍历
6.另一颗树的子树
层序遍历#xff1a;
7.二叉树遍历
8.判断二叉树是否是完全二叉树 一个特殊的性质#xff1a; 1.相同的树
题目链接#xff1a;力扣#xff08;LeetC…目录
1.相同的树 2.二叉树中查找值为x的节点
3.单值二叉树
4.对称二叉树 5.二叉树的前序遍历
6.另一颗树的子树
层序遍历
7.二叉树遍历
8.判断二叉树是否是完全二叉树 一个特殊的性质 1.相同的树
题目链接力扣LeetCode 思路 这道题我们可以把它分为三个子问题分别是根与根、左子树与左子树、右子树与右子树之间的比较而且最好是用前序的方式即先比较根要是根都不相等后面的就不用比较了而子树也可以在再分为根、左子树、右子树......直到不能分为止所以每次递归调用如果根的值不相等就返回false如果相等就继续往下比较。 注意要分全为空、只有一个为空、全不为空三种情况处理。 代码如下
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);
} 2.二叉树中查找值为x的节点
这道题是延续我们上节内容 思路 这道题思路很简单也是分为查找根、左子树、右子树三个子问题先找根的值如果相等就返回根节点如果不等继续找左子树如果相等返回左子树的节点如果不相等继续找右子树如果相等返回右子树节点如果不等则继续上面过程。 但是这道题我们要求返回的是节点所以在某次递归中如果找到了节点就要先把它保存下来然后再返回到这次递归的上一级如果不保存那节点极大可能返回不到函数外面。总而言之递归是一级一级往上返回的如果递归有返回值每次递归都要确保能接收到下一次递归返回的值。 代码如下
#includestdio.h
#includestdlib.h
#includeassert.htypedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail\n);return NULL;}node-left NULL;node-right NULL;node-data x;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}
//二叉树中查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1){return ret1;}BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2){return ret2;}return NULL;
}
int main()
{BTNode* root CreatBinaryTree();BTNode* p BinaryTreeFind(root, 3);printf(%d\n, p-data);return 0;
}
3.单值二叉树
题目链接力扣LeetCode 思路 这道题我们可以先比较根节点和左子树的值然后比较根节点和右子树的值当左子树不为空且它和根节点的值不相等时返回false当右子树不为空且它和根节点的值不相等时返回false当左右子树都和根节点相等时继续递归直到rootNULL返回true这时truetruetrue返回true。 代码如下
bool isUnivalTree(struct TreeNode* root) {if(rootNULL){return true;}if(root-left!NULLroot-val!root-left-val){return false;}if(root-right!NULLroot-val!root-right-val){return false;}return isUnivalTree(root-left)isUnivalTree(root-right);
}
4.对称二叉树
题目链接力扣LeetCode 思路 这道题默认有一个根节点该节点不用比较所以我们可以比较根节点下的左子树和右子树这就需要两个参数我们可以把左子树的根节点和右子树的根节点作为左根和右根传给函数_isSymmetric()然后把左根的左子树和右根的右子树比较左根的右子树和右根的左子树比较如果不等返回false如果相等继续递归直到全部为空返回truetruetruetrue返回true。 代码如下
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(rightRoot-left,leftRoot-right);}
bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root-left,root-right);
} 5.二叉树的前序遍历
题目链接力扣LeetCode 思路 这道题看起来很简单只需要按照根、左子树、右子树的顺序依次访问即可但是有很多坑 1. 需要自己malloc数组但是数组大小不知道所以还要写一个函数用来计算二叉树大小 2. malloc数组之后就不能在原函数中写递归了否则每次递归都会malloc一个空间所以又得专门写一个递归的函数。 3.二叉树节点的值要存储到数组中必然要使用下标但是下标在调用中不能传值否则每次递归调用后栈帧销毁栈帧中形参i后的值不能返回上一级递归往数组中存放数据就会出错。 下面来看一个经典的错误
int TreeSize(struct TreeNode* root){return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}void _preorderTraversal(struct TreeNode* root, int*a,int i){if(rootNULL){return;}a[i]root-val;_preorderTraversal(root-left,a,i);_preorderTraversal(root-right,a,i);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSizeTreeSize(root);int*a(int*)malloc(*returnSize*sizeof(int));int i0;_preorderTraversal(root, a,i);return a;
} 可以看到下面用例执行错误了 为什么呢
画一下递归调用图就知道了 所以以后在递归时如果需要传下标最好传地址用指针接收。
正确代码如下
int TreeSize(struct TreeNode* root){return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}void _preorderTraversal(struct TreeNode* root, int*a,int* pi){if(rootNULL){return;}a[(*pi)]root-val;_preorderTraversal(root-left,a,pi);_preorderTraversal(root-right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSizeTreeSize(root);int*a(int*)malloc(*returnSize*sizeof(int));int i0;_preorderTraversal(root, a,i);return a;
}
6.另一颗树的子树 思路 这道题本质还是找两颗相同的树只不过一个树必须得是另外一个树的子树那我们可以复用上文中“相同的树”的代码然后遍历找到第一棵树的所有子树与第二棵树比较如果不同继续遍历只要左右子树中有一个子树与第二颗树相同就返回true。 题目链接力扣LeetCode
代码如下
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;}if(isSameTree(root,subRoot)){return true;}return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}
在讲下一道题之前我们先来学习一下二叉树的层序遍历。
层序遍历 二叉树的层序遍历是一层一层往下走的我们可以用队列来实现它用队列保存二叉树每一层的节点先让根节点入队保存并打印根节点的值然后根节点出队让它的左右孩子入队相当于第一层出队的同时带第二层入队一层带一层直到队列中所有节点都为NULL就说明二叉树遍历结束了。 层序需要队列的代码这里只列出层序的核心代码关于队列部分的代码可以在栈与队列章节中找到 数据结构-栈和队列一-CSDN博客
层序代码
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q,front-left);if (front-right)QueuePush(q,front-right);}printf(\n);DestoryQueue(q);
}
注意这里就是三层嵌套了队列Queue中有头尾节点和队列大小size头尾节点中有next指针和数据data而数据data中存放的是二叉树的节点指针所以我们在Queue.h中要把数据类型改成二叉树节点指针 三层嵌套的关系如下图 所以我们每次pop的都是队列的节点而front是指向二叉树节点的指针它没有被pop所以可以找到二叉树节点的数据和它的左右孩子。
再补充一个内容那就是二叉树的销毁 二叉树销毁最好用后序先销毁左右子树最后销毁根节点不建议使用前序否则先销毁根节点就找不到左右子树了又要重新构建二叉树比较麻烦。 //二叉树的销毁
void BTreeDestory(BTNode* root)
{if (root NULL){return;}BTreeDestory(root-left);BTreeDestory(root-right);free(root);
}
7.二叉树遍历
题目链接二叉树遍历_牛客题霸_牛客网 这道题其实包含了二叉树的创建和遍历 相当于给一个字符串要求把给字符串恢复成一个二叉树然后输出它的中序遍历那abc##de#g##f###它是前序遍历的我们就用前序把它恢复成二叉树 创建二叉树时也是先创建根节点然后创建左子树、右子树。 注意在传数组下标时传地址用指针接收。 代码如下
#include stdio.h
#includestdlib.h
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail\n);return NULL;}node-left NULL;node-right NULL;node-data x;return node;
}
//创建二叉树
BTNode*CreateTree(char*a,int*pi)
{if(a[*pi]#){(*pi);return NULL;}BTNode*rootBuyNode(a[*pi]);(*pi);root-leftCreateTree(a,pi);root-rightCreateTree(a,pi);return root;
}
//中序遍历
void InOrder(BTNode*root)
{if(rootNULL){return;}InOrder(root-left);printf(%c ,root-data);InOrder(root-right);}
int main()
{char a[100];scanf(%s,a);int i0;BTNode*rootCreateTree(a,i);InOrder(root);printf(\n);return 0;
}
8.判断二叉树是否是完全二叉树 思路 这道题就要使用到层序遍历了我们说层序遍历是一层带一层的入队和出队的过程而完全二叉树的每一层都是按顺序排放的让它的每一层数据入队然后出队直到遇见空如果是完全二叉树那此时最后一个数据出队后后面应该全为NULL而非完全二叉树就不全是NULL了如下图 所以当我们遇到空时就跳出循环然后判断后面的是否全为空一旦有非空那就不是完全二叉树。 代码如下
//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q,root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//遇到空就跳出if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);}//检查后面的节点有没有非空//有非空就不是完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){DestoryQueue(q);return false;}}DestoryQueue(q);return true;
}
二叉树的一个特殊的性质 对任何一棵二叉树, 如果度为0的叶结点个数为n0 , 度为2的分支结点个数为 n1,则有 n0n1 1 简单推导一下
对二叉树增加一个度为1的节点就一定会减少一个度为0的节点同时增加的这个节点度也为0此时度为0和度为2的节点个数相当于没变 而增加一个度为2的节点就一定会减少一个度为1的同时会增加一个度为0的节点 所以二叉树中度为0的节点总是比度为2的节点个数多一个。
下面我们来做道题 在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 答案是A 假设度为0的节点有n0个度为1的有n1个度为2的有n2个根据上文学过的性质可得 n0 n1 n0-12n而此时要整除叶子节点一定是整数个n1必然是1所以可得n0 2n/2 n 好了到今天为止我们二叉树就告一段落了其实二叉树还有很多问题这些留到后面C的时候学习
下节内容会接着讲解排序敬请期待。。。
