建设网站要在需求,服务app开发的公司,网站建设协议 模板下载,一级造价师准考证打印时间目录
一.前言
二.模拟实现链式结构的二叉树
2.1二叉树的底层结构
2.2通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
2.3二叉树的销毁
2.4二叉树查找值为x的节点
2.5二叉树节点个数
2.6二叉树叶子节点个数
2.7二叉树第k层节点个数
三.二叉树的遍历
3.1…目录
一.前言
二.模拟实现链式结构的二叉树
2.1二叉树的底层结构
2.2通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
2.3二叉树的销毁
2.4二叉树查找值为x的节点
2.5二叉树节点个数
2.6二叉树叶子节点个数
2.7二叉树第k层节点个数
三.二叉树的遍历
3.1前序遍历
3.2中序遍历
3.3后序遍历
3.4层序遍历 一.前言
详解—数据结构《树和二叉树》-CSDN博客
上一节课我们详解了树和二叉树这一篇博客我来带领大家来模拟实现二叉树
二.模拟实现链式结构的二叉树
2.1二叉树的底层结构 首先有一个数据域 然后有俩个二叉树指针分别指向他们的左孩子和右孩子 typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
2.2通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 1、按照前序遍历先走根再走左子树再走右子树的方法我们首先了解大概思路 2、数组里面的#就相当于为空所以我们先判断if 我们的数组为#就返回空 3、然后我们创建一个节点如果开辟失败返回空我们进行判断 4、然后放入数据 5、再然后递归开始走左子树右子树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int * pi)
{if (# a[*pi]){(*pi);return NULL;}BTNode * root (BTNode *)malloc (sizeof(BTNode));if (root NULL){perror(malloc);return;}root-data a[(*pi)];root-left BinaryTreeCreate(a, n, pi);root-right BinaryTreeCreate(a, n, pi);return root;
} 2.3二叉树的销毁 销毁一颗二叉树 1.首先判断如果是空树直接返回 2.利用递归从最左边的树开始进行一个节点一个节点的删除 void BinaryTreeDestory(BTNode** root)
{if (*root NULL)return;BinaryTreeDestory((*root)-left);BinaryTreeDestory((*root)-right);free(*root);*root NULL;
} 2.4二叉树查找值为x的节点 二叉树的查找在这里我用的前序遍历递归 1.先确定递归的退出条件root等于空就返回 2.然后进行前序遍历 3.判断一下当前节点是不是x 4.在开始走左子树 5.开始走右子树 BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{BTNode* node;if (root NULL)return NULL ;//一开始就是 xif (root-data x){return root;}//前序遍历寻找xnode BinaryTreeFind(root-left, x);if (node)return node;node BinaryTreeFind(root-right, x);if (node)return node;//遍历完找不到返回空return NULL;
} 2.5二叉树节点个数 二叉树的节点个数就是二叉树左子树加上右子树加上根 这里我用的也是递归的方法同学们可以看一下 int BinaryTreeSize(BTNode* root)
{return root NULL ? 0 : BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right) 1;
}
2.6二叉树叶子节点个数 叶节点或终端节点度为0的节点称为叶节点 可以观看上一篇文章取了解叶子节点 详解—数据结构《树和二叉树》-CSDN博客 查找叶子节点也是用的递归方法 首先增加递归退出条件root0 然后如果所在的节点他的左右子树都为空那么他就是叶子节点返回1 最后递归遍历所有的叶子节点进行相加 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);
}
2.7二叉树第k层节点个数 在二叉树中我们想知道每一层有多少个节点 1.确定递归退出条件 2.如果k1返回1代表找到了这一层的一个节点 3.进行递归每一层k-1当k1是找到所在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);}
三.二叉树的遍历
3.1前序遍历 二叉树的遍历了解可以详细看看上一章节 详解—数据结构《树和二叉树》-CSDN博客 前序遍历的遍历方法就是先走根然后左子树右子树 我们这里还是用的递归 1.先确定递归条件 2.打印当前节点 3.走左子树 4.走右子树 void BinaryTreePrevOrder(BTNode * root)
{if (root NULL){return;}printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}
3.2中序遍历 中序遍历的顺序是先走左子树再走根再走右子树 我们的实现方法如下 1.确定递归条件 2.走左子树 3.打印当前节点 4.走右子树 void BinaryTreeInOrder(BTNode* root)
{if (root NULL){return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right);
}
3.3后序遍历 后序遍历的顺序是先走左子树再走右子树再走根 我们的实现方法如下 1.确定递归条件 2.走左子树 3.走右子树 4.打印当前节点 void BinaryTreePostOrder(BTNode* root)
{if (root NULL){return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data);
}
3.4层序遍历 首先我们层序遍历需要用到队列我们先添加前几章写的队列到当前项目中然后进行调用 1.创建并初始化一个队列 2.当根不为空时将根节点入队 3.保存根节点地址访问其数据域之后出队 4.若根节点的左子树不为空入队左子树 5.判断根节点的右子树不为空入队右子树 6.保存队头节点地址访问其数据域之后出队 8.重复上述过程的条件是队列不为空 void BinaryTreeLevelOrder(BTNode* root)
{Queue q;//初始化队列QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%c , front-data);QueuePop(q);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}printf(\n);//销毁队列QueueDestroy(q);
}
