庆阳网站设计定制,天津vi设计公司,WordPress迁移网站打不开,网站架构规划#x1f308;一、树的基本概念
☀️1.树的定义#xff1a;树是一种非线性结构#xff0c;看起来像一棵倒挂的树#xff0c;根朝上#xff0c;而叶朝下。 ☀️2.相关术语
1.根节点#xff1a;图中的A#xff0c;无前驱结点 2.叶节点#xff08;终端节点#xff09;一、树的基本概念
☀️1.树的定义树是一种非线性结构看起来像一棵倒挂的树根朝上而叶朝下。 ☀️2.相关术语
1.根节点图中的A无前驱结点 2.叶节点终端节点度为0的节点 如上图B、C、H、I…等节点为叶节点。 3.分支节点非终端节点度不为0的节点 如上图D、E、F、G…等节点为分支节点。 4.父节点双亲节点如上图A是B的父节点。 5.子节点如上图B是A的孩子节点。 6.兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点。 7.节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6。 8.节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 9.树的度一棵树中最大的节点的度称为树的度 如上图树的度为6。 10.树的高度或深度树中节点的最大层次 如上图树的高度为4。 11.森林由mm0棵互不相交的树的集合称为森林。
注子树不可以相交相交是图
☀️3.树的表示方法
法一有几个孩子就设定几个孩子指针 缺陷孩子数无法改变了。 法二用顺序表存储孩子指针 缺陷define了N孩子数无法改变了。 法三最优方法左孩子右兄弟 父节点只需要一个指针指向最左侧的孩子其他孩子都可以通过左孩子的指针依次找到。 优势当有多个且数量不固定的孩子节点时用该结构也可以。 用该结构访问到每一个孩子 判断节点是否是叶子节点看左孩子是否是空。 法四双亲表示法不支持通过父亲找孩子只支持通过孩子找父亲。并查集中会用 如何检查一片森林中有几棵树数有几个-1就有几棵树。 如何判断两个节点在不在同一棵树上看两个节点的根一不一样。
二、二叉树基本概念
☀️1.二叉树定义
一棵二叉树是结点的一个有限集合该集合或者为空或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
☀️2.二叉树特性
1.二叉树不存在度大于2的结点对于任意的二叉树都是由以下几种情况复合而成的
2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。
☀️3.学习二叉树的意义
二叉树的价值不是存储数据和增删查改仅仅存储数据可以用链表等结构存储没必要用复杂的二叉树来存储数据。二叉树价值在于根节点处存储的值最小最大值可以借此进行排序。
☀️4.特殊的二叉树
1.满二叉树一个二叉树如果每一层的结点数都达到最大值则这个二叉树就是满二叉树。
2.完全二叉树有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树即最后一层的节点从左到右排中间没有空隙。 满二叉树是一种特殊的完全二叉树。
3.单值二叉树
☀️5.关于节点数和序号数的性质及相关题目
性质
1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2i-1个结点。 2.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2h-1。 注错位相减法算满二叉树节点个数
3.对任何一棵二叉树, 如果度为0的叶结点个数为n0, 度为2的分支结点个数为n2,则有n0n21。 4. 若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2(n1)。 5.高度为h的完全二叉树节点数范围是2(h-1)~2h-1。 6.对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 ①若i0i位置节点的父节点序号(i-1)/2i0i为根节点编号无双亲节点。 ②若2i1n左孩子序号为2i12i1n时无左孩子。 ③若2i2n右孩子序号为2i22i2n时无右孩子。
题目
1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为B A 不存在这样的二叉树 B 200 C 198 D 199 分析有199个度为2的节点可得知有1991200个度为0的节点。选B。
2.下列数据结构中不适合采用顺序存储结构的是A A 非完全二叉树 B 堆 C 队列 D 栈 选A。
3.在具有 2n 个结点的完全二叉树中叶子结点个数为A A n B n1 C n-1 D n/2 分析 n0n21,n10或1代入下式得 2nn0n1n22×n21n1 n1此时只能等于1 2n2×n22n2n-1叶子结点n0n-11n选A。
4.一棵完全二叉树的节点数位为531个那么这棵树的高度为B A 11 B 10 C 8 D 12 分析假设树层数为h则完全二叉树节点数范围是2(h-1)~2h-12951221010245125311023,因此该树高度h为10。选B。
5.一个具有767个节点的完全二叉树其叶子节点个数为B A 383 B 384 C 385 D 386 分析假设度为0的节点数为n0度为1的节点数为n1度为2的节点数为n2完全二叉树的n1只能是0或1n0n21, 则n0n1n22 ∗ * ∗n2n11767节点数不可能是小数则n1为0n2值为383叶子节点数n0为384。选B。
☀️6.二叉树的存储结构
1顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
2链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。 三、前中后序遍历二叉树
先手动构建图示的二叉树
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;BTNode* BuyNode(int x) {BTNode* node (BTNode*)malloc(sizeof(BTNode));if (!node) {perror(malloc fail);exit(-1);}node-val x;node-left NULL;node-right NULL;return node;
}
int main() {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 node4;node2-left node3;node4-left node5;node4-right node6;return 0;
}☀️1.前序遍历二叉树 顺序1-2-3-NULL-NULL-NULL-4-5--NULL-NULL-6-NULL-NULL 代码 主函数中调用PreOrder(node1)即
PreOrder(node1);void PreOrder(BTNode* root) {if (!root) {printf(NULL );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}结果
☀️2.中序遍历二叉树 顺序NULL-3-NULL-2-NULL-1-NULL-5-NULL-4-NULL-6-NULL 代码 主函数中调用InOrder(node1)即
InOrder(node1);void InOrder(BTNode* root) {if (!root) {printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}打印结果
☀️3.后序遍历二叉树 顺序 NULL-NULL-3-NULL-2-NULL-NULL-5-NULL-NULL-6-4-1 代码 主函数中调用PostOrder(node1)即
PostOrder(node1);void PostOrder(BTNode* root) {if (!root) {printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}打印结果
