接网站开发项目,如何在网站上做免费广告,中国企业在线网,wordpress 弹窗登录下面就是这篇博客要讲的内容
树 二叉树堆
树概念及结构二叉树的概念及结构二叉树的实现堆的概念及运用
这篇博客主要以二叉树为主要内容。
1、树的概念及结构
1.1树的概念#xff1a;
树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限…下面就是这篇博客要讲的内容
树 二叉树堆
树概念及结构二叉树的概念及结构二叉树的实现堆的概念及运用
这篇博客主要以二叉树为主要内容。
1、树的概念及结构
1.1树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
其中有三个注意的点 1树有一个特殊的结点称为根结点根结点没有前驱结点 2除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。 3树形结构中子树之间不能有交集否则就不是树形结构 在第一个图中A节点就是我们的根节点。
1.2树的基本概念
1结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6 2叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等结点为叶结点 3非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等结点为分支结点 4双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 5孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 6兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点 7树的度一棵树中最大的结点的度称为树的度 如上图树的度为6 8结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 9树的高度或深度树中结点的最大层次 如上图树的高度为4 10堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点 11结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先 12子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙
森林由mm0棵互不相交的树的集合称为森林
1.3树的表示
这里就简单的了解其中最常用的孩子兄弟表示法——左孩子右兄弟。
typedef int DataType;
struct Node
{struct Node* firstChild1;// 第一个孩子结点struct Node* pNextBrother;// 指向其下一个兄弟结点DataType data;// 结点中的数据域
};这就是我们树中的一个节点。 表现形式如上图。 这种方式来表示树非常的牛大家可以试想如果我们不用这种方式我们怎样来表示我们的树—— 树的分支数我们知道吗那我们怎样定义我们的分支呢那就只有顺序表那顺序表开多大的空间那样会非常的麻烦而且会浪费我们的空间而上图的方式完美解决了我们的问题。
2、二叉树的概念及结构
2.1 二叉树的概念 形如上图每个节点都最多只有两个分支的数就为我们的二叉树。
2.2 特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
2.3 二叉树的性质非常重要尽量自己尝试着去推导
1、若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。 2、若规定根结点的层数为1则深度为h的二叉树的最大结点数是2^h-1。 3、对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0 n21。 4、若规定根结点的层数为1具有n个结点的满二叉树的深度hlog(n1)。log以2为底 5、对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有
若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子 这三个推论在堆的实现、堆排序中使用所以也希望大家能记住。 由于篇幅原因我这里就不再给大家一步一步推了。
2.4 二叉树的存储
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 1顺序结构
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 顺序结构有什么好处呢 可以用下标来表示父子关系 2链式结构
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left;
// 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data;
// 当前结点值域
}这篇博客先了解我们的链式存储在下一篇我们就介绍顺序存储–堆。
三、二叉树链式结构的实现
3.1 二叉树的遍历前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
这里我画出来前序和中序大家自己来画一下后序遍历这一块可以为我们后面要学的搜索二叉树打下基础这一块也是必须要掌握的。
遍历代码部分
这里我们还没有学会创建我们的树那么我们就用笨办法手动去构建我们的树 1、首先我们要先确定树的形状我这里的是自己随便画的大家可以自己来构建自己想要的树 2代码构建
typedef struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;//二叉树的节点TreeNode* creatTree()
{TreeNode* node1 (TreeNode*)malloc(sizeof(TreeNode));node1-val 1;node1-left node1-right NULL;TreeNode* node2 (TreeNode*)malloc(sizeof(TreeNode));node2-val 2;node2-left node2-right NULL;TreeNode* node3 (TreeNode*)malloc(sizeof(TreeNode));node3-val 3;node3-left node3-right NULL;TreeNode* node4 (TreeNode*)malloc(sizeof(TreeNode));node4-val 4;node4-left node4-right NULL;TreeNode* node5 (TreeNode*)malloc(sizeof(TreeNode));node5-val 5;node5-left node5-right NULL;TreeNode* node6 (TreeNode*)malloc(sizeof(TreeNode));node6-val 6;node6-left node6-right NULL;TreeNode* node7 (TreeNode*)malloc(sizeof(TreeNode));node7-val 7;node7-left node7-right NULL;//创建我们的二叉树节点node1-left node2; node1-right node3;node2-left node4; node2-right node5;node5-right node7; node3-right node6;//链接我们的树return node1;//返回树的根节点
}3、遍历我们的二叉树
void preOrder(TreeNode* root)
{if (root NULL)return;printf(%d , root-val);preOrder(root-left);preOrder(root-right);
}
int main()
{TreeNode* root creatTree();preOrder(root);//前序遍历return 0;
}void inOrder(TreeNode* root)//中序遍历
{if (root NULL)return;inOrder(root-left);printf(%d , root-val);inOrder(root-right);
}大家可以看到代码部分非常的简单但大家一定要明白它是怎样执行的。
3.2 层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 层序遍历就是一层一层访问这里只是简单的介绍这一块我们后面才学。
四、我们学完二叉树要解决的问题
4.1 二叉树的节点个数问题
int treeSize(TreeNode* root)
{if (root NULL)return 0;return treeSize(root-left) treeSize(root-right) 1;
}关于这块的问题我们采用分置的思想。 节点个数 1、根为空–0 2、不为空–左子树右子树1。 这一块对于初学者确实非常的有难度前期我们甚至可以将代码背下来。 大家需要在不断刷题后来慢慢体会。
4.2 二叉树的叶子节点个数问题
int treeLeaveSize(TreeNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return treeLeaveSize(root-left) treeLeaveSize(root-right);
}叶子节点特征左右子树为空。 叶子 1、根为空–0 2、不为空–如果左子树右子树为空就返回1。
4.3 二叉树的高度问题
int treeHeight(TreeNode* root)
{if (root NULL)return 0;int left treeHeight(root-left);int right treeHeight(root-right);return left right ? left 1 : right 1;
}高度 1、根为空–0 2、不为空–左子树与右子树中大的1
当然还有以下问题大家可以自己尝试去解决大家可以自己尝试去锻炼自己分置的思想。
1、单值二叉树。 2、 检查两颗树是否相同。 3、另一颗树的子树。 4、对称二叉树。 5、二叉树的构建与销毁。
总的来说这一部分还是非常的有难度希望大家不要放弃通过刷题去增强自己的信心。
