当前位置: 首页> 财经> 产业 > app制作公司十强_国产网站开发工具公司_网站可以自己做吗_国外网站排行

app制作公司十强_国产网站开发工具公司_网站可以自己做吗_国外网站排行

时间:2025/7/9 6:46:12来源:https://blog.csdn.net/2301_79706435/article/details/141602060 浏览次数:0次
app制作公司十强_国产网站开发工具公司_网站可以自己做吗_国外网站排行

目录

一、二叉树的基本结构

二、二叉树的遍历

1.前序

2.中序

3.后序 

4.层序遍历 

三.计算二叉树的相关参数

1.计算节点总个数

 2.计算叶子节点的个数

 3.计算树的高度

4.计算第k层的子树个数

 5.查找树中val为x的节点

 四.刷题

1.单值二叉树

2.检查两棵树是否相同

3.一棵树是否对称


二叉树的实现源码_gitee


一、二叉树的基本结构

 这里的二叉树比堆的定义更广泛,

heap=>完全二叉树/满二叉树

二叉树=>二叉,不成图(没有闭合圈)

二、二叉树的遍历

1.前序

NULL用‘#’表示,下面实例的val是char类型

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}

这里使用的是递归式的遍历,因为二叉树可以看作子树,而子树又可以看作根和子树

注意,这里的return 是指返回上一层的递归,下面是部分运行逻辑

2.中序

void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);}

3.后序 

void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}

4.层序遍历 

这里要使用队列,先根节点入队,根节点出队后,对应的左右子树节点入队,左子树节点作为根节点出队,再有对应的左右子树节点入队,以此类推

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while(!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);printf("%c ", cur->_data);if (cur->_left)QueuePush(&q, cur->_left);if(cur->_right)QueuePush(&q, cur->_right);}}


这是带有换行效果的层序遍历,实现原理是需要记录每一层的个数,方便pop 完一层接一个换行

void BinaryTreeLevelOrder(BTNode* root)
{Queue Bq;QueueInit(&Bq);QueuePush(&Bq, root);int popnum = QueueSize(&Bq);while(!QueueEmpty(&Bq)){while(popnum--){BTNode* cur = QueueFront(&Bq);QueuePop(&Bq);printf("%c ", cur->_data);if(cur->_left!=NULL){QueuePush(&Bq, cur->_left);}if(cur->_right!=NULL){QueuePush(&Bq, cur->_right);}}popnum = QueueSize(&Bq);printf("\n");}}

三.计算二叉树的相关参数

1.计算节点总个数

思路1:遍历二叉树,不过要传入一个可以记录的参数,为了这个参数可以随遍历而变化,不能传入实参拷贝为形参这一套

解决方法:

1.使用static参数,在函数内定义,只要把static的值最后return,在全局则可以不用,直接查static的值,弊端:这个函数不能再同一个程序里重复调用,因为static的值不会再从0开始 

2.在参数列表里多传入一个int *size,每次++时就(*size)++,在进入下一个递归


 思路2:递归计数,

当root==NULL,   return 0;

当root不为NULL时,return 1+左子树的个数+右子树的个数

int BinaryTreeSize(BTNode* root)
{
if(root==NULL)
{return 0;
}
return 1 + BinaryTreeSize(root->_right) + BinaryTreeSize(root->_left);}

 2.计算叶子节点的个数

思路:递归计数,叶子节点时左右子树都为NULL时,

int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL) { return 0; }if(root->_left==NULL&&root->_right==NULL){return 1;}return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

 3.计算树的高度

int nummax(int p1, int p2)
{return p1 > p2 ? p1 : p2;}
int tree_height(BTNode* root)
{if(root==NULL){return 0;}return 1 + nummax(height(root->_left),height(root->_right));}

4.计算第k层的子树个数

 思路:距离root为k,那么距离root的下一层为k-1,当k==1时,就是递归到第k层了

root==NULL,return 0

root!=NULL&&k==1,return 1;

其他情况:return knum(root->left,k-1)  +  knum(root->right,k-1)

int knum(BTNode* root,int k)
{if(root==NULL){return 0;}if (k == 1){return 1;}return knum(root->left, k - 1) + knum(root->right, k - 1);}

 5.查找树中val为x的节点

思路:递归遍历+比较是否为x

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == x){return root; }BTNode* node1 = BinaryTreeFind(root->_left, x);if (node1) { return node1; }return BinaryTreeFind(root->_right, x);}

 

6.判断是否为完全二叉树

思路:以层序遍历对二叉树进行收集(此时NULL也收入),在每个节点开始pop时,判断是否为NULL,一旦为NULL,则跳出循环,开始判断NULL之后的队列是否全为NULL,

如果全为NULL==>是完全二叉树

如果不是==>不是

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);if (cur == NULL)break;QueuePush(&q, cur->_left);QueuePush(&q, cur->_right);}while (!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);if (cur != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;}

 

 四.刷题

1.单值二叉树

bool _isUnivalTree(struct TreeNode* root,int val)
{
if(root==NULL)
return true;if(root->val!=val)
return false;return _isUnivalTree(root->left,val)&&_isUnivalTree(root->right,val);}bool isUnivalTree(struct TreeNode* root) {int val=root->val;
return _isUnivalTree(root,val);}

2.检查两棵树是否相同

 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(p->right, q->right);}

3.一棵树是否对称

bool issame(struct TreeNode* p1, struct TreeNode* p2)
{if (p1 == NULL && p2 == NULL){return true;}if (p1 == NULL || p2 == NULL){return false;}if (p1->val != p2->val) { return false; }return issame(p1->left, p2->right)&&issame(p1->right, p2->left);
}
bool isSymmetric(struct TreeNode* root) {if(root==NULL){return true;}return issame(root->left, root->right);}


关键字:app制作公司十强_国产网站开发工具公司_网站可以自己做吗_国外网站排行

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: