福州建设人才网站,做网站需要了解什么东西,南宁法拍房源信息,网页设计工作室文章目录 1. 二叉树的链式结构2. 二叉树的创建和实现相关功能2.1 创建二叉树2.2 二叉树的前#xff0c;中#xff0c;后序遍历2.2.1 前序遍历2.2.2 中序遍历2.2.3 后序遍历 2.3 二叉树节点个数2.4 二叉树叶子结点个数2.5 二叉树第k层结点个数2.6 二叉树的深度/高度2.7 二叉树… 文章目录 1. 二叉树的链式结构2. 二叉树的创建和实现相关功能2.1 创建二叉树2.2 二叉树的前中后序遍历2.2.1 前序遍历2.2.2 中序遍历2.2.3 后序遍历 2.3 二叉树节点个数2.4 二叉树叶子结点个数2.5 二叉树第k层结点个数2.6 二叉树的深度/高度2.7 二叉树查找值为x的结点2.8 层序遍历2.9 判断二叉树是否为完全二叉树2.10 二叉树的销毁 3. 源代码 1. 二叉树的链式结构
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链三叉链在结构上比二叉链多了一个指向父节点的指针域。 在这里先使用二叉链来实现二叉树
2. 二叉树的创建和实现相关功能
2.1 创建二叉树
用链表来实现二叉树每个链表结点都由一个数据域和左右指针域组成
//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;接下来我们来实现创建节点的函数
首先使用malloc函数创建一个节点大小的空间如果创建失败就打印错误信息创建成功则把数据存储在新节点的数据域中再将新节点的左右孩子指针指向空最后返回新节点即可
//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}下面我们来创建一棵如图所示的二叉树
BTNode* CreateTree()
{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 node3;node2-left node4;node2-right node5;node3-left node6;return node1;
}2.2 二叉树的前中后序遍历
下面来简单介绍一下前中后序遍历的规则 下面来根据上面所示的二叉树进行前中后序遍历
2.2.1 前序遍历
前序遍历就是先打印根节点的值再遍历根节点的左子树最后遍历根节点的右子树也就是根左右
//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}根据以上代码进入函数先打印根节点存储的值再递归左子树左子树递归完后再递归右子树。不要忘了如果遇到空节点记得要返回。
前序遍历的步骤
打印根节点的值为1递归左子树创建根节点左孩子节点2的函数栈帧打印节点2的值为2创建节点2的左孩子节点4的函数栈帧打印节点4的值为4创建节点4的左孩子节点的函数栈帧节点4的左孩子节点为空返回节点4的函数栈帧创建节点4的右孩子节点的函数栈帧节点4的右孩子节点为空返回节点4的函数栈帧节点4的函数栈帧被销毁返回节点2的函数栈帧创建节点2的右孩子节点5的函数栈帧打印节点5的值为5创建节点5的左孩子节点的函数栈帧节点5的左孩子节点为空返回节点5的函数栈帧创建节点5的右孩子节点的函数栈帧节点5的右孩子节点为空返回节点5的函数栈帧节点5的函数栈帧被销毁返回节点2的函数栈帧节点2的函数栈帧被销毁返回根节点的函数栈帧创建根节点的右孩子节点3的函数栈帧打印节点3的值为3创建节点3的左孩子节点6的函数栈帧打印节点6的值为6创建节点6的左孩子节点的函数栈帧节点6的左孩子节点为空返回节点6的函数栈帧创建节点6的右孩子节点的函数栈帧节点6的右孩子节点为空返回节点6的函数栈帧节点6的函数栈帧被销毁返回节点3的函数栈帧创建节点3的右孩子节点的函数栈帧节点3的右孩子节点为空返回节点3的函数栈帧节点3的函数栈帧被销毁返回根节点的函数栈帧根节点的函数栈帧被销毁
所以前序遍历的结果为1 2 4 5 3 6
中序遍历和后序遍历与前序遍历的思路一样只是打印节点的值和递归左右子树的顺序不同而已
2.2.2 中序遍历
思路先遍历根节点的左子树再打印根节点的值最后遍历根节点的右子树也就是左根右
中序遍历的结果4 2 5 1 6 3
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}2.2.3 后序遍历
思路先遍历根节点的左子树再遍历根节点的右子树最后打印根节点的值也就是左右根
后序遍历的结果4 5 2 6 3 1
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}2.3 二叉树节点个数
思路先递归根节点的左子树再递归根节点的右子树如果递归到空节点就返回0最后返回左子树节点个数和右子树节点个数的和再加一
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}2.4 二叉树叶子结点个数
思路第一种情况如果递归到的当前节点为空就返回0第二种情况如果节点的左右子树为空时说明该节点为叶子节点则返回1第三种情况如果递归到的节点既不是空又不是叶子节点则继续递归该节点的左右子树即返回该节点左右子树的叶子节点 return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(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);
}2.5 二叉树第k层结点个数
思路因为根节点是第一层所以每次向下遍历时将k减一当k1时当前节点就是在第k层返回1即可所以只需一直递归节点的左右子树每次递归节点的左右子树时还要让k减一。当递归到的节点为空时只需返回0即可要先判断节点为不为空如果不为空再判断当前节点是不是在第k层。
//二叉树第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);
}2.6 二叉树的深度/高度
思路因为二叉树的左右子树的高度可能不一样所以要分开递归二叉树的左右子树然后再取最大值即可。当递归到空节点时返回0否则继续递归当前节点的左右子树最后返回左右子树深度的最大值再加一(因为当前的根节点也是一层)
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDepth BinaryTreeDepth(root-left);int rightDepth BinaryTreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}2.7 二叉树查找值为x的结点
思路先遍历根节点的左子树如果找到了值为x的节点就返回该节点的地址右子树也无需再遍历了如果没有找到再遍历右子树如果找到了就返回该节点的地址没有找到则返回空。再遍历的过程中先判断节点是否为空如果为空就返回空不为空的话再判断该节点的值是不是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;
}2.8 层序遍历
这里需要借助队列不熟悉的可以看一下数据结构—队列
层序遍历是指从根节点开始一层一层遍历二叉树从上至下从左至右依次访问节点如下图该二叉树的层序遍历结果为1 2 3 4 5 6 使用队列这个数据结构来实现层序遍历队列的特点是先进先出。首先将根节点放入队列中再将根节点出队最后将根节点的左右孩子节点入队。将根节点的左孩子2出队然后将根节点的左孩子2的左右孩子节点入队以此类推……一直到队列为空 //层序遍历
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.9 判断二叉树是否为完全二叉树
思路同样还是借助队列这个数据结构与层序遍历不同的是当节点的左右孩子节点为空时也要进行入队操作当队头为空时就退出循环然后还需要判断队列里有没有不为空的节点如果有说明二叉树不为完全二叉树如果没有说明二叉树为完全二叉树
//判断二叉树是否为完全二叉树
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){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}2.10 二叉树的销毁
思路因为要销毁整个二叉树包括根节点所以这里传递的是二级指针去接收一级指针的地址这样就实现了形参改变实参。先销毁根节点的左子树和右子树也就是递归到叶子节点开始销毁然后往上一层一层地进行销毁最后再销毁根节点。
//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}3. 源代码
Tree.h头文件
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;//创建二叉树新节点
BTNode* buyNode(BTDataType x);
//创建一个二叉树
BTNode* CreateTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);Tree.c源文件
#include Tree.h
#include Queue.h
//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}
//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}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层结点个数
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 NULL){return 0;}int leftDepth BinaryTreeDepth(root-left);int rightDepth BinaryTreeDepth(root-right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
//二叉树查找值为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;
}
//层序遍历
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);
}
//判断二叉树是否为完全二叉树
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){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}test.c源文件
#include Tree.hBTNode* CreateTree()
{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 node3;node2-left node4;node2-right node5;node3-left node6;return node1;
}void BinaryTreeTest01()
{BTNode* node1 CreateTree();PreOrder(node1);printf(\n);InOrder(node1);printf(\n);PostOrder(node1);printf(\n);printf(%d\n, BinaryTreeSize(node1));printf(%d\n, BinaryTreeLeafSize(node1));printf(第%d层结点个数为%d\n, 3, BinaryTreeLevelKSize(node1, 3));printf(%d\n, BinaryTreeDepth(node1));if (BinaryTreeFind(node1, 10) NULL){printf(没有找到\n);}else{printf(找到了\n);}LevelOrder(node1);printf(\n);printf(%s\n, BinaryTreeComplete(node1) true ? 是完全二叉树 : 不是完全二叉树);BinaryTreeDestory(node1);
}
int main()
{BinaryTreeTest01();return 0;
}对以上内容有不同看法的欢迎来讨论希望对大家的学习有帮助多多支持哦
