当前位置: 首页> 汽车> 行情 > 推广电影链接赚佣金_代理记账公司如何寻找客户_百度网站建设_如何弄一个自己的网站

推广电影链接赚佣金_代理记账公司如何寻找客户_百度网站建设_如何弄一个自己的网站

时间:2025/7/10 20:06:34来源:https://blog.csdn.net/2401_88328558/article/details/145969290 浏览次数: 0次
推广电影链接赚佣金_代理记账公司如何寻找客户_百度网站建设_如何弄一个自己的网站

实现链式结构的二叉树

    • 实现链式结构的二叉树
      • 遍历
        • 前序遍历
        • 中序遍历
        • 后序遍历
      • 节点个数
      • 叶子节点个数
      • ⼆叉树第k层结点个数
      • ⼆叉树的深度/⾼度
      • 查找值为X的节点
      • 二叉树的销毁
    • 层序遍历
    • 判断二叉树是否为完全二叉树

⽤链表来表⽰⼀棵⼆叉树,即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 ,

其结构如下:

typedef int BTDataType; // ⼆叉链 
typedef struct BinaryTreeNode 
{ struct BinTreeNode* left; // 指向当前结点左孩⼦ struct BinTreeNode* right; // 指向当前结点右孩⼦ BTDataType val; // 当前结点值域 
}BTNode;

遍历

前中后序遍历

前序遍历

也叫先根遍历

先遍历根节点,再遍历左子树,最后遍历右子树

左右根

image-20250122120904177 image-20250122121456060

A->B->D->NULL->NULL->NULL->C->E->NULL->NULL->F->NULL->NULL

//前序遍历--根左右
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}
中序遍历

先遍遍历左子树,,再遍历根节点,最后遍历右子树

左根右

image-20250122120908431 image-20250122122358193

NULL->D->NULL->B->NULL->A->NULL->E->NULL->C->NULL->F->NULL

//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
后序遍历

先遍历左子树,再遍历右子树,最后遍历根节点

左右根

image-20250122120912308 image-20250122123010493

NULL->NULL->D->NULL->B->NULL->NULL->E->NULL->NULL->F->C->A

//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

节点个数

节点个数 = 1(根节点)+ 左子树节点个数 + 右子树节点个数

// ⼆叉树结点个数 
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}//节点个数 = 1(根节点)+ 左子树节点个数 + 右子树节点个数return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

叶子节点个数

叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数

//⼆叉树叶⼦结点个数 
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);
}

⼆叉树第k层结点个数

当k == 1,直接在当前节点返回,

当k != 1,继续向下一层递归,k-1

//⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

⼆叉树的深度/⾼度

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root == 0){return 0;}//高度 = max(左子树,右子树)+ 1return 1 + max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right));
}

查找值为X的节点

//⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

二叉树的销毁

使用后序遍历

//⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

层序遍历

按照层次依次遍历(从上到下,从左到右)

广度优先遍历

image-20250218160303782

思路:

使用队列,根节点入队,循环判断队列是否为空,不为空取队头,将队头结点左右孩子入队(非空)

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头,出队,将左右孩子(非空)入队BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);if (top->left){QueuePush(&q,top->left);}if (top->right){QueuePush(&q, top->right);}}QueueDestory(&q);
}

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头,出队,将左右孩子(非空)入队BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//入队QueuePush(&q, top->left);QueuePush(&q, top->right);}//如果存在非空结点,是非完全二叉树while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}
关键字:推广电影链接赚佣金_代理记账公司如何寻找客户_百度网站建设_如何弄一个自己的网站

版权声明:

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

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

责任编辑: