医疗网站seo怎么做,赣县人才网招聘信息网,做视频网站需要哪些技术指标,如何更改asp网站自定义产品顺序前言#xff1a; 在上篇文章【数据结构】二叉树——顺序结构——堆及其实现中#xff0c;实现了二叉树的顺序结构#xff0c;使用堆来实现了二叉树这样一个数据结构#xff1b;现在就来实现而二叉树的链式结构。 一、链式结构 链式结构#xff0c;使用链表来表示一颗二叉树…前言 在上篇文章【数据结构】二叉树——顺序结构——堆及其实现中实现了二叉树的顺序结构使用堆来实现了二叉树这样一个数据结构现在就来实现而二叉树的链式结构。 一、链式结构 链式结构使用链表来表示一颗二叉树即用链来指示二叉树中元素的逻辑关系。通常的就是链表中每个节点右三个域组成数据域和左右指针域左右指针分别指向该节点的左孩子节点和右孩子节点的存储地址。 链式结构分为二叉链和三叉链三叉链比而二叉链多一个指向父节点的指针域。 这里使用二叉链来实现。
二、二叉树链式结构实现相关功能
在实现之前先来看一下具体要实现哪些功能 首先就是二叉树的结构我们使用链表来实现链表的每一个节点都由数值域和左右指针域组成。 二叉树链式结构的节点
typedef int TreeDataType;
typedef struct TreeNode
{TreeDataType data;struct TreeNode* left;struct TreeNode* right;
}TreeNode;二叉树链式结构如上接下来再来看一下二叉树链式结构实现的相关功能
//二叉树的前序排序
int PreOrder(TreeNode* root);
//二叉树的中序排序
int InOrder(TreeNode* root);
//二叉树的后序遍历
int AfterOrter(TreeNode* root);
//二叉树节点个数
int BinaryTreeSize(TreeNode* root);
//二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root);
//二叉树第k层节点个数
int BinaryTreeLevelKSize(TreeNode* root, int k);
//二叉树的深度
int BinaryTreeDepth(TreeNode* root);
//查找二叉树值为x的节点
TreeNode* BinaryTreeFind(TreeNode* root, TreeDataType x);
//层序遍历
void LevelOrder(BTNode* root)
//判断是否为满二叉树
bool BinaryTreeComplete(BTNode* root)
//二叉树的销毁
void TreeDesTroy(TreeNode** root); 2.1、二叉树前、中、后序遍历
这里前序、中序和后序遍历什么意思呢 说白了这三种遍历其实就是以对二叉树访问的顺序来遍历二叉树
这里以前序遍历为例遍历二叉树 现在有一个这样的二叉树用前序遍历来访问这颗二叉树这里访问并输出访问到的数据 首先访问根节点输出访问到的数据 1 再访问左子树 再访问其左子树的根节点输出访问到的数据 2 再接着访问左子树 再访问其左子树的根节点输出访问到的数据 4 再接着访问左子树 此时访问到了空节点就直接回退回退到其父节点的函数栈帧访问父节点的右子树 访问4这个节点的右子树也为空此时节4这个点为根节点的左子树已经访问 结束了回退到其父节点的函数栈帧访问其父节点的右子树 访问2这个节点的右子树先输出右子树的根节点数据 5 再访问根节点5的左子树 这里节点5的左右节点都为空这里省略一些过程此时5这个节点访问结束回退到2这个节点而2这个节点右子树访问结束也已经访问结束了此时再回退到根节点访问根节点的右子树。 此时访问根节点的右子树的根节点输出访问到的数据 3 再接着访问3这个节点的左子树 这里3这个节点的左右节点都为空访问就直接返回回退到根节点就说明根节点的右子树访问已经结束此时二叉树已经变了结束。 这里前序遍历的输出结果为 1 2 4 5 3
这三个前、中、后序遍历本质上没啥差别这里直接看实现代码
//二叉树的前序排序
void PreOrder(TreeNode* root)
{if (root NULL){return;}//输出数据printf(%d , root-data);//遍历左子树PreOrder(root-left);//遍历右子树PreOrder(root-right);
}
//二叉树的中序排序
void InOrder(TreeNode* root)
{if (root NULL){return;}//遍历左子树InOrder(root-left);//输出数据printf(%d , root-data);//遍历右子树InOrder(root-right);
}
//二叉树的后序遍历
void AfterOrter(TreeNode* root)
{if (root NULL){return;}//遍历左子树AfterOrter(root-left);//遍历右子树AfterOrter(root-right);//输出数据printf(%d , root-data);
} 这里我们来测试代码对不对我们先创建一个二叉树然后看输出结果是否正确、
TreeNode* BuyNode(TreeDataType x)
{TreeNode* newnode (TreeNode*)malloc(sizeof(TreeNode));if (newnode NULL){perror(malloc);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}void test()
{TreeNode* node1 BuyNode(1);TreeNode* node2 BuyNode(2);TreeNode* node3 BuyNode(3);TreeNode* node4 BuyNode(4);TreeNode* node5 BuyNode(5);node1-left node2;node1-right node3;node2-left node4;node2-right node5;//前序遍历PreOrder(node1);printf(\n);//中序遍历InOrder(node1);printf(\n);//后序遍历AfterOrter(node1);printf(\n);
}
int main()
{test();return 0;
} 这里代码没有问题。 2.2、二叉树节点个数 这里二叉树的链式结构我们是使用递归来实现的那我们该如何去计算二叉树的节点个数呢 思路 遍历二叉树遍历到空节点就返回0不是空节点就返回其左子树和右子树节点个数之和再加一 代码如下
//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
} 2.3、二叉树叶子结点个数 所谓叶子节点就是左右子节点都为空的节点我们就利用这个特点来判断 思路 遍历二叉树遍历到空节点就返回空遍历到节点的左右节点都为空返回1否则就返回节点的左子树和右子树的叶子结点之和。 代码如下
//二叉树叶子节点个数
int BinaryTreeLeafSize(TreeNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
} 2.4、二叉树第k层节点个数 求二叉树第k层节点的个数我们先来看这样的一个图 通过图我们可以看到每次向下遍历一层k-1当k1时正好是第k层 思路 遍历二叉树遍历到空节点就返回 0 遍历到k1时就返回1否则就返回该节点左子树和右子树中第k - 1层的节点个数。 这里需要注意要在判断k1之前判断节点是否为空。
代码如下
//二叉树第k层节点个数
int BinaryTreeLevelKSize(TreeNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
} 2.5、二叉树的深度 求二叉树的深度我们这里是将二叉树的左子树和右子树分开依次遍历的显然我们不能像上面一样返回遍历左子树和右子树的和这里就返回其中最大的。 思路 遍历二叉树遍历到空节点就返回空定义两个值记录其节点左子树和右子树的深度再加一返回其中最大的即可。 理解这里定义两个值记录其左右子树的深度加一加一就是记录当前这一层。
代码如下
//二叉树的深度
int BinaryTreeDepth(TreeNode* root)
{if (root NULL){return 0;}int depth_left BinaryTreeDepth(root-left) 1;int depth_right BinaryTreeDepth(root-right) 1;return (depth_left depth_right) ? depth_left : depth_right;
} 2.6、查找二叉树中值为 x 的节点 查找相对来说就比较简单了遍历二叉树为空就返回NULL值为x就返回该节点的地址如果遍历过程中函数返回值不为NULL就证明找到了直接返回即可。 思路 遍历二叉树遍历到空节点就返回NULL判断节点的值是否为x是就返回该节点的地址不是。就创建指针变量接受其左右子树遍历的结果如果不为NULL就直接返回该返回值。为空则继续遍历。 代码如下
//查找二叉树值为x的节点
TreeNode* BinaryTreeFind(TreeNode* root, TreeDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}TreeNode* pleft BinaryTreeFind(root-left, x);if (pleft)return pleft;TreeNode* pright BinaryTreeFind(root-right, x);if (pright)return pright;return NULL;
}
到这里来看一下这些代码是否正确 对于这样的一个二叉树代码输出结果都正确。 2.7、层序遍历
这里层序遍历我们需要借用队列这样一个数据结构前面有详细讲解
大致思路如此 将根节点数据放入队列中然后出队列并且把该节点的左右子节点插入到队列当中。 将1这个节点出队列再把左右子节点插入到队列当中 再出队头节点将其左右子节点插入队列当中 依次类推当队头数据左右子节点为空就不进插入队列这一操作。 代码如下 这里用到了对列相关代码详细代码在上篇
//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){//取队头打印BTNode* front QueueFront(q);printf(%d , front-data);QueuePop(q);//队头节点的左右孩子入队列if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}//队列为空QueueDestroy(q);
} 2.8、判断二叉树是否为满二叉树 判断二叉树是否为满二叉树还是借用队列这样的数据结构和层序遍历有相似之处与层序遍历不同的是这里即便左右子节点为空有进行入队列操作当队头数据为空就判断队列剩余数据是否都为空如果都为空就证明二叉树为满二叉树否则就不是满二叉树。 代码如下
//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);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 ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 2.9、二叉树的销毁 这里为了测试这些代码就手动创建了一个二叉树这些都是动态开辟的空间养成好习惯手动释放动态开辟的空间。
这里需要注意的是使用后序遍历先是否底层的节点
代码如下
// 二叉树销毁
void BinaryTreeDesTroy(TreeNode** root)
{if (*root NULL){return;}BinaryTreeDesTroy(((*root)-left));BinaryTreeDesTroy(((*root)-right));free(*root);*root NULL;
}
感谢各位大佬支持并指出问题 如果本篇内容对你有帮助可以一键三连支持以下感谢支持
