大型网站建设费用,做网站的一般都包维护吗,石家庄新钥匙网站,物联网系统二叉树#xff08;1#xff09;#xff1a;深入理解数据结构第一弹——二叉树#xff08;1#xff09;——堆-CSDN博客
二叉树#xff08;2#xff09;#xff1a;深入理解数据结构第二弹——二叉树#xff08;2#xff09;——堆排序及其时间复杂度-CSDN博客
前言…二叉树1深入理解数据结构第一弹——二叉树1——堆-CSDN博客
二叉树2深入理解数据结构第二弹——二叉树2——堆排序及其时间复杂度-CSDN博客
前言 在前面我们讲了堆及其应用帮助我们初步了解了二叉树的一些原理但那与真正的二叉树仍有不同今天我们就来正式学习一下二叉树的基本结构及其基本操作 目录 一、什么是二叉树
二、二叉树的节点结构
三、二叉树的遍历
前序遍历
中序遍历
后序遍历
四、二叉树的基本操作
1、创建二叉树
2、前序、中序、后序
3、求二叉树的节点个数
4、求二叉树叶子节点的个数
5、树的高度
6、二叉树第k层的节点个数
7、二叉树查找值为x的节点
五、完整代码实例
总结 一、什么是二叉树 在前面的文章中我们已经提到过二叉树的结构及其特点这里我们不过多赘述有不理解的可以点文章开头的链接去前面看一下 二、二叉树的节点结构 二叉树有左右子树之分且二叉树与我们所学的其他数据结构不同的点在于之前我们所学的都是各类插入或者删除等等但是二叉树需要做的操作是运用递归遍历所以二叉树的节点结构与之前几个有很大不同 typedef int TreeDataType;
typedef struct Tree
{TreeDataType a;struct Tree* left;struct Tree* right;
}Tree;节点结构里面定义有两个递归是为了方便后面的遍历
三、二叉树的遍历
二叉树的遍历是我们学习二叉树首先要了解的东西我们都知道二叉树其实就是一串数组那我们是如何访问他们的呢这里就牵扯到了遍历顺序的问题。
二叉树的遍历有三种形式前序、中序和后序 前序遍历 特点按照“根-左-右”的顺序遍历二叉树。特点首先访问根节点然后递归地前序遍历左子树最后递归地前序遍历右子树。应用常用于复制一棵树、计算表达式的值等。 中序遍历 特点按照“左-根-右”的顺序遍历二叉树。特点先递归地中序遍历左子树然后访问根节点最后递归地中序遍历右子树。应用常用于二叉搜索树可以得到一个递增的有序序列。 后序遍历 特点按照“左-右-根”的顺序遍历二叉树。特点先递归地后序遍历左子树然后递归地后序遍历右子树最后访问根节点。应用常用于释放二叉树的内存空间或者计算表达式的值。 例如
四、二叉树的基本操作 我先把主函数给出接下来就将按照主函数中的这些功能一步一步来实现 int main()
{Tree* root CreatTree();//前序printf(前序);PrevTree(root);printf(\n);//中序printf(中序);HalfTree(root);printf(\n);//后序printf(后序);PostTree(root);printf(\n);//节点个数int count BTreeSize(root);printf(BTreeSize:%d\n, count);//叶子节点个数printf(BTreeLeafSize:%d\n, BTreeLeafSize(root));//树的高度printf(BTreeHigh:%d\n, BTreeHigh(root));//二叉树第k层节点个数printf(BTreeLevelKSize:%d\n, BTreeLevelKSize(root, 3));//二叉树查找值为x的节点return 0;
}
1、创建二叉树
//二叉树
typedef int TreeDataType;
typedef struct Tree
{TreeDataType a;struct Tree* left;struct Tree* right;
}Tree;
//初始化二叉树
Tree* TreeInit(TreeDataType x)
{Tree* m (Tree*)malloc(sizeof(Tree));if (m NULL){perror(TreeInit);return NULL;}m-a x;m-left NULL;m-right NULL;return m;
}
//创建一个二叉树
Tree* CreatTree()
{Tree* n1 TreeInit(3);Tree* n2 TreeInit(5);Tree* n3 TreeInit(6);Tree* n4 TreeInit(7);Tree* n5 TreeInit(9);n1-left n2;n1-right n3;n2-left n4;n2-right n5;return n1;
}2、前序、中序、后序 前序、中序和后序其实就是数据按照上面图片中的形式进行遍历 //前序
void PrevTree(Tree* root)
{if (root NULL){printf(N );return;}printf(%d , root-a);PrevTree(root-left);PrevTree(root-right);
}
//中序
void HalfTree(Tree* root)
{if (root NULL){printf(N );return;}HalfTree(root-left);printf(%d , root-a);HalfTree(root-right);
}
//后序
void PostTree(Tree* root)
{if (root NULL){printf(N );return;}PostTree(root-left);PostTree(root-right);printf(%d , root-a);
}运行结果 3、求二叉树的节点个数
//二叉树节点个数
int BTreeSize(Tree* root)
{//分治的思想if (root NULL){return 0;}return BTreeSize(root-left) BTreeSize(root-right)1 ;
}用到了递归的思想下面的内容都要用递归来解决如果递归学的不太好建议画图来看这些过程如何进行的
运行结果 4、求二叉树叶子节点的个数
//二叉树叶子节点个数
int BTreeLeafSize(Tree* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}运行结果 5、树的高度
//求二叉树高度
int BTreeHigh(Tree* root)
{if (root NULL){return 0;}int leftHigh BTreeHigh(root-left);int rightHigh BTreeHigh(root-right);return leftHigh rightHigh ? leftHigh 1 : rightHigh 1;
}运行结果 6、二叉树第k层的节点个数
//二叉树第k层节点个数
int BTreeLevelKSize(Tree* root, int k)
{assert(k 0);if (root NULL){return 0;}if (k 1){return 1;}return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}运行结果 7、二叉树查找值为x的节点
//二叉树查找值为x的节点
Tree* BTreeFind(Tree* root,int x)
{if (root NULL)return NULL;if (root-a x)return root;Tree* ret1 BTreeFind(root-left, x);if (ret1){return ret1;}Tree* ret2 BTreeFind(root-right, x);if (ret2){return ret2;}
}五、完整代码实例
//二叉树
typedef int TreeDataType;
typedef struct Tree
{TreeDataType a;struct Tree* left;struct Tree* right;
}Tree;
//初始化二叉树
Tree* TreeInit(TreeDataType x)
{Tree* m (Tree*)malloc(sizeof(Tree));if (m NULL){perror(TreeInit);return NULL;}m-a x;m-left NULL;m-right NULL;return m;
}
//创建一个二叉树
Tree* CreatTree()
{Tree* n1 TreeInit(3);Tree* n2 TreeInit(5);Tree* n3 TreeInit(6);Tree* n4 TreeInit(7);Tree* n5 TreeInit(9);n1-left n2;n1-right n3;n2-left n4;n2-right n5;return n1;
}
//前序
void PrevTree(Tree* root)
{if (root NULL){printf(N );return;}printf(%d , root-a);PrevTree(root-left);PrevTree(root-right);
}
//中序
void HalfTree(Tree* root)
{if (root NULL){printf(N );return;}HalfTree(root-left);printf(%d , root-a);HalfTree(root-right);
}
//后序
void PostTree(Tree* root)
{if (root NULL){printf(N );return;}PostTree(root-left);PostTree(root-right);printf(%d , root-a);
}
//二叉树节点个数
int BTreeSize(Tree* root)
{//分治的思想if (root NULL){return 0;}return BTreeSize(root-left) BTreeSize(root-right)1 ;
}
//二叉树叶子节点个数
int BTreeLeafSize(Tree* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
}
//求二叉树高度
int BTreeHigh(Tree* root)
{if (root NULL){return 0;}int leftHigh BTreeHigh(root-left);int rightHigh BTreeHigh(root-right);return leftHigh rightHigh ? leftHigh 1 : rightHigh 1;
}
//二叉树第k层节点个数
int BTreeLevelKSize(Tree* root, int k)
{assert(k 0);if (root NULL){return 0;}if (k 1){return 1;}return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
}
//二叉树查找值为x的节点
Tree* BTreeFind(Tree* root,int x)
{if (root NULL)return NULL;if (root-a x)return root;Tree* ret1 BTreeFind(root-left, x);if (ret1){return ret1;}Tree* ret2 BTreeFind(root-right, x);if (ret2){return ret2;}
}
int main()
{Tree* root CreatTree();//前序printf(前序);PrevTree(root);printf(\n);//中序printf(中序);HalfTree(root);printf(\n);//后序printf(后序);PostTree(root);printf(\n);//节点个数int count BTreeSize(root);printf(BTreeSize:%d\n, count);//叶子节点个数printf(BTreeLeafSize:%d\n, BTreeLeafSize(root));//树的高度printf(BTreeHigh:%d\n, BTreeHigh(root));//二叉树第k层节点个数printf(BTreeLevelKSize:%d\n, BTreeLevelKSize(root, 3));//二叉树查找值为x的节点return 0;
}
运行结果 总结 总而言之二叉树其实是对我们运用递归来遍历数据的考察由于篇幅原因这里我们只对二叉树的结构进行了大致的讲解有不理解的地方欢迎与我私信或者在评论区中指出 创作不易还请各位大佬点个小小的赞
