怎么看网站是哪家公司做的,做威士忌的网站,厦门seo关键词排名,做网站哪个简单点5.树和二叉树
5.1树和二叉树的定义
树形结构#xff08;非线性结构#xff09;#xff1a;结点之间有分支#xff0c;具有层次关系。
5.1.1树的定义
树#xff08;Tree#xff09;是n#xff08;n≥0#xff09;个结点的有限集。
若n0#xff0c;称为空树#x…5.树和二叉树
5.1树和二叉树的定义
树形结构非线性结构结点之间有分支具有层次关系。
5.1.1树的定义
树Tree是nn≥0个结点的有限集。
若n0称为空树若n0则它满足如下两个条件 有且仅有一个特定的称为根Root的结点其余结点可分为mm≥0个互不相交的有限集T1,T2,…Tm其中每一个集合本身又是一棵树并称为根的子树SubTree。
**树是n个结点的有限集。**显然树的定义是一个递归的定义。 树的其他表示形式 5.1.2树的基本术语 **根结点**非空树中无前驱结点的结点。 **结点的度**结点拥有的子树数。 **树的度**树内各结点的度的最大值。 **叶子结点**度为0的点也称为终端结点。 **分支结点**度≠0的结点也称为非终端结点。 **内部结点**根结点以外的分支结点称为内部结点。 **双亲结点**结点的子树的根称为该结点的孩子该结点称为孩子的双亲。 **兄弟结点**结点之前有共同的双亲结点称为兄弟结点。 **堂兄弟结点**双亲在同一层的结点。 **结点的祖先**从根到该结点所经分支上的所有结点。 **结点的子孙**以某结点为根的子树中的任一结点。 **树的深度**树中结点的最大层次。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XagGN3sY-1691068168684)(https://ts1.cn.mm.bing.net/th/id/R-C.fe38e3b271e2321ef483becbb761c23b?rik2QonkZPTVvq%2btgriuhttp%3a%2f%2fpic.baike.soso.com%2fp%2f20131206%2f20131206141836-722390134.jpgehkmNDvDkeq8qFKHHsXCLhiWhru8%2fGKWK1lU%2f3sEGzBvh4%3drislpidImgRawr0sres1sresct1)]
有序树树中结点的各子树从左至右有次序最左边的为第一个孩子。
**无序树**树中结点的各子树无次序。
**森林**是mm≥0颗互不相交的树的集合。把根结点删除树就变成了森林。
一棵树可以看成是一个特殊的森林。
给森林中的各子树加上一个双亲结点森林就变成了树。
树一定是森林但森林不一定是树。
5.1.3树结构和线性结构的比较
线性结构树结构第一个数据元素无前驱根结点只有一个无双亲最后一个数据元素无后继叶子结点可以有多个无孩子其他数据元素一个前驱一个后继其他结点中间结点一个双亲多个孩子一对一一对多
5.1.4二叉树的定义
为什么要重点研究每结点最多只有两个“叉”的树
二叉树的机构最简单规律性最强可以证明所有树都能转为唯一对应的二叉树不失一般性。
普通树多叉树若不转化为二叉树则运算很难实现
二叉树在树结构的应用中起着非常重要的作用因为对二叉树的许多操作算法简单而任何树都可以与二叉树相互转换这样就解决了树的存储结构及其运算中存在的复杂性。
二叉树是nn≥0个结点的有限集它或者是空集n0或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。
特点
每个结点最多有两孩子二叉树中不存在度大于2的结点。子树有左右之分其次序不能颠倒。二叉树可以是空集合根可以有空的左子树或空的右子树 注意二叉树不是树的特殊情况它们是两个概念。 二叉树结点的子树要区分左子树和右子树即使只有一颗子树也要进行区分说明它是左子树还是右子树。 树当结点只有一个孩子时就无须区分他是左还是右的次序。因此二者是不同的。这是二叉树与树的最主要的区别。 也就是二叉树每个结点位置或者说次序都是固定的可以是空但是不可以说它没有位置而树的结点位置是相对于别的结点来说的没有别的结点时它就无所谓左右了。 二叉树的五种基本形态 注意虽然二叉树与树概念不同但有关树的基本术语对二叉树都适用。 5.2树和二叉树的类型定义
CreateBiTreeTdefinition
初始条件definition给出二叉树T的定义。
操作结果按definition构造二叉树T。
PreOrderTraverseT
初始条件二叉树T存在。
操作结果先序遍历T对每个结点访问一次。
InOrderTraverseT
初始条件二叉树T存在。
操作结果中序遍历T对每个结点访问一次。
POSTOrderTraverseT
初始条件二叉树T存在。
操作结果后序遍历T对每个结点访问一次。
5.3二叉树的性质和存储结构
5.3.1二叉树的性质 性质1在二叉树的第 i 层上至多有 2i-1个结点i≥1。 性质2深度为 k 的二叉树至多有2k-1个结点k≥1。 深度为k时至少有 k 个结点。 性质3对任何一颗二叉树T如果其叶子数为n0度为2的结点数为n2则 n0n21。 总边数为B B n - 1 或 B n2 * 2 n1 * 1 总结点数为n n n2 * 2 n1 * 1 1 或者 n n2 n1 n0
5.3.2两种特殊形式的二叉树
1、满二叉树
一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。 特点
每一层上的结点数都是最大结点数即每层都满。叶子结点全部在最底层。
对满二叉树结点位置进行编号
编号规则从根结点开始自上而下自左而右。每一结点位置都有元素。 满二叉树在同样深度的二叉树中结点个数最多。 满二叉树在同样深度的二叉树中叶子结点个数最多。 2、完全二叉树
深度为k的具有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点——对应时称之为完全二叉树。 注意在满二叉树中从最后一个结点开始连续去掉任意个结点即是一颗完全二叉树。 一定是连续的去掉 特点
叶子只可能分布在层次最大的两层上。对任一结点如果其右子树的最大层次为i则其左子树的最大层次必为 i 或 i 1。
满二叉树一定是完全二叉树完全二叉树不一定满二叉树。
5.3.3完全二叉树的性质 **性质4**具有 n 个结点的完全二叉树的深度为 [log2n] 1。 注意[ x ]称作x的底表示不大于x的最大整数。 表明了完全二叉树结点数n与完全二叉树深度k之间的关系。 性质5如果对一棵有n个结点的完全二叉树深度为[ log2n ]1的结点按层序编号从第1层到第[log2n]1层每层从左到右则对任一结点 i 1≤ i ≤ n有 如果 i 1则结点 i 是二叉树的根无双亲如果 i 1则其双亲是结点 [i / 2]。如果2in则结点i为叶子结点无左孩子否则其左孩子是结点2i。如果2i 1n则结点i无右孩子否则其右孩子是结点 2i 1。 表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系。
5.3.4二叉树的存储结构
二叉树的存储结构分为顺序存储结构以及链式存储结构二叉链表三叉链表。
1、二叉树的顺序存储结构
实现按满二叉树的结点层次编号依次存放二叉树中的数据元素。 二叉树顺序存储表示
#define MAXSIZE 100
typedef int SqBiTree[MAXSIZE];
SqBiTree bt;二叉树的顺序存储缺点
**最坏情况**深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。
特点
结点间关系蕴含在其存储位置中浪费空间适于存满二叉树和完全二叉树
2、二叉树的链式存储结构 二叉链表存储结构
typedef struct BiNode {int data;struct BiNode* lchild, * rchild;//左右孩子
}BiNode,*BiTree;在n个结点的二叉链表有__n1__个空指针域。 分析必有2n个链域。除根结点外每个结点有且仅有一个双亲所以只会有 n-1 个结点的链域存放指针指向非空子女结点。 空指针数目 2n -n-1n1 三叉链表 typedef struct TriTNode{int data;struct TriTNode *lichild,*parent,*rchild;
}TriTNode,*TriTree;5.4遍历二叉树和线索二叉树
5.4.1遍历二叉树
遍历定义——顺着某一条搜索路径巡访二叉树中的结点使得每个结点均被访问一次而且仅被访问一次又称周游。
“访问”的含义很广可以是对结点做各种处理如输出结点的信息修改结点的数据值等但要求这种访问不破坏原来的数据结构。
遍历目的——得到树中所有结点的一个线性排列。
遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提是二叉树一切运算的基础和核心。
1、遍历二叉树算法描述
遍历方法依次遍历二叉树中的三个组成部分便是遍历了整个二叉树。 则遍历整个二叉树方案共有
ABC、ACB、BAC、BCA、CAB、CBA六种。
若规定先左后右则只有前三种情况
ABC —— 先根序遍历
BAC —— 中根序遍历
BCA —— 后根序遍历。
先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空则空操作 否则若二叉树为空则空操作 否则若二叉树为空则空操作 否则1访问根结点1中序遍历左子树1后序遍历左子树2先序遍历左子树2访问根结点2后序遍历右子树3先序遍历右子树。3中序遍历右子树。3访问根结点。
由二叉树的递归定义可知遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。 2、根据遍历序列确定二叉树
若二叉树中各结点的值均不相同则二叉树结点的先序序列中序序列和后序序列都是唯一的。由二叉树的先序序列和中序序列或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树。
3、遍历的算法思想
先序遍历根左右
若二叉树为空则空操作若二叉树非空
访问根结点D
前序遍历左子树L
前序遍历右子树R
bool PreOrderTraverse(BiTree T) {if (T NULL) return true;//空二叉树else {visit(T);//访问根结点PreOrderTraverse(T-lchild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}
}void Pre(BiTree T) {if (T ! NULL) {printf(%d\t, T-data);Pre(T-lchild);Pre(T-rchild);}
}中序遍历左根右
若二叉树为空则空操作若二叉树非空
中序遍历左子树L
访问根结点D
中序遍历右子树R
bool InOrderTraverse(BiTree T) {if (T NULL) return true;else {InOrderTraverse(T-lchild);//递归遍历左子树visit(T);//访问根结点InOrderTraverse(T-rchild);//递归遍历右子树}
}后序遍历左右根
若二叉树为空则空操作若二叉树非空
后序遍历左子树L
后序遍历右子树R
访问根结点D
bool PostOrderTraverse(BiTree T) {if (T NULL) return true;else {PostOrderTraverse(T-lchild);//递归遍历左子树PostOrderTraverse(T-rchild);//递归遍历右子树visit(T);//访问根结点}
}遍历算法的分析
如果去掉输出语句从递归的角度看三种算法是完全相同的或者说这三种算法的访问路径是相同的只是访问结点的时机不同。 从虚线的出发点到终点的路径上每个结点都要经过 3 次。 第一次经过时访问 先序遍历 第二次经过时访问 中序遍历 第三次经过时访问 后序遍历 4、遍历二叉树的非递归算法
中序遍历非递归算法
二叉树中序遍历的非递归算法的关键在中序遍历过某结点的整个左子树后如何找到该结点的根以及右子树。
基本思想
建立一个栈根结点进栈遍历左子树根结点出栈输出根结点遍历右子树
bool InOrderTraver(BiTree T) {BiTree p,q;SqStack S;InitStack(S);p T;while (p||!StackEmpty(S)){if (p) {Push(S, p);p p-lchild}else {Pop(S, q);printf(%c, q-data);p q-rchild;}}return true;
}二叉树的层次遍历 对于一颗二叉树从根结点开始按从上到下从左到右的顺序访问每一个结点。每个结点仅仅访问一次。
**算法设计思路**使用一个队列
将根结点进队队不空时循环从队列中出列一个结点*p访问它 若它有左孩子结点将左孩子结点进队若它有右孩子结点将右孩子结点进队。
使用队列类型定义如下
void LevelOrder(BTNode *b){BTNode *p;SqQueue *qu;InitQueue(qu);EnQueue(qu,b);//根结点指针进入队列while(!QueueEmpty(qu)){DeQueue(qu,p);//出队结点pprintf(%c,p-data);if(p-lchild!NULL)enQueue(qu,p-lchild);//有左孩子时将其进队if(p-rchild!NULL)enQueue(qu,p-rchild);//有右孩子时将其进队}
}5.4.2二叉树遍历算法的应用
1、二叉树的建立
按先序遍历序列建立二叉树的二叉链表 例已知先序序列为ABCDEGF 1从键盘输入二叉树的结点信息建立二叉树的存储结构
2在建立二叉树的过程中按照二叉树先序方式建立。 对于上图所示二叉树按下列顺序读入字符
ABC##DE#G##F###
bool CreatBiTree(BiTree T) {char* ch;scanf(%c, ch);if (ch #) T NULL;else {if (!(T (BiNode*)malloc(sizeof(BiNode))))return false;T-data ch;//生成根结点CreatBiTree(T-lchild);//构建左子树CreatBiTree(T-rchild);//构建右子树}return true;
}2、复制二叉树
算法思想
如果是空树递归结束否则申请新结点空间复制根节点 递归复制左子树递归复制右子树
int Copy(BiTree T, BiTree NewT) {if (T NULL) {NewT NULL;return 0;}else {NewT new BiNode;NewT-data T-data;Copy(T-lchild, NewT-lchild);Copy(T-rchild, NewT-rchild);}
}3、计算二叉树深度
如果是空树则深度为0否则递归计算左子树的深度记为m递归计算右子树的深度记为n二叉树的深度则为m与n的较大者加1。
int Depth(BiTree T) {if (T NULL) return 0;//如果是空树返回0else {int m Depth(T-lchild);int n Depth(T-rchild);if (m n) return(m 1);else return(n 1);}
}4、计算二叉树结点总数
如果是空树则结点个数为0否则结点个数为左子树的结点个数 右子树的结点个数再 1
int NodeCount(BiTree T) {if (T NULL)return 0;elsereturn NodeCount(T-lchild) NodeCount(T-rchild) 1;
}5、计算二叉树叶子结点数
如果是空树则叶子结点个数为0否则为左子树的叶子结点个数 右子树的叶子结点个数。
int LeafCount(BiTree T) {if (T NULL)return 0;//如果是空树返回0if (T-lchild NULL T-rchild NULL)return 1;//如果是叶子结点返回1elsereturn LeafCount(T-lchild) LeafCount(T-rchild);
}5.4.3线索二叉树 问题为什么要研究线索二叉树 当用二叉链表作为二叉树的存储结构时可以很方便地找到某个结点的左右孩子但一般情况下无法直接找到该结点在某种遍历序列中的前驱和后继结点。 提出的问题如何寻找特定遍历序列中二叉树结点的前驱和后继
解决方法
通过遍历寻找——费时间再增设前驱、后继指针域——增加了存储负担。利用二叉链表中的空指针域。
回顾二叉树链表中空指针域的数量
具有n个结点的二叉链表中一共有2n个指针域因为n个结点中有n-1个孩子即2n个指针域中有n-1个用来指示结点的左右孩子其余n1个指针域为空。
利用二叉链表中的空指针域
如果某结点的左孩子为空则将空的左孩子指针域改为指向其前驱如果某结点的右孩子为空则将空的右孩子指针域改为指向其后继——这种改变指向的指针称为“线索”
加上了线索的二叉树称为线索二叉树Threaded Binary Tree
对二叉树按某种遍历次序使其改变为线索二叉树的过程叫线索化。
为了区分lchild和rchild指针到底是指向孩子的指针还是指向前驱或者后继的指针对二叉链表中每个结点增设两个标志域ltag和rtag并约定
ltag 0 lchild指向该结点的左孩子
ltag 1 lchild指向该结点的前驱
rtag 0 rchild指向该结点的右孩子
rtag 1 rchild指向该结点的后继
线索二叉树结点的结构为
typedef struct BiThrNode {int data;int ltag, rtag;struct BiThrNode* lchild, * rchild;
}BiThrNode,*BiThrTree;5.5树和森林
树Tree是nn≥0个结点的有限集。若n0称为空树若n0
有且仅有一个特定的称为根Root的结点其余结点可分为mm≥0个互不相交的有限集T1,T2,T3,…,Tm
森林是mm≥0棵互不相交的树的集合。
5.5.1树的存储结构
1、双亲表示法
实现定义结构数组存放树的结点每个结点含两个域
数据域存放结点本身信息。双亲域指示本结点的双亲结点在数组中的位置。 C语言的类型描述
typedef struct PTNode{TElemType data;int parent;//双亲位置域
}PTNode;树结构
#define MAXSIZE 100
typedef struct{PTNode nodes[MAXSIZE];int r,n;//根结点的位置和结点个数
}PTree;2、孩子链表
把每个结点的孩子结点排列起来看成是一个线性表用单链表存储则n个结点由n个孩子链表叶子的孩子链表为空表。而n个头指针又组成一个线性表用顺序表含n个元素的结构数组存储。 C语言的类型描述
孩子结点结构child | next
typedef struct CTNode{int child;struct CTNode *next;
}*ChildPtr;双亲结点结构data | firstchild
typedef struct{TElemType data;ChildPtr firstchild;//孩子链表头指针
}CTBox;树结构
typedef struct{CTBox nodes[MAXSIZE];int n,r;//结点数和根结点的位置
}CTree;特点找孩子容易找双亲难。
3、孩子兄弟表示法
也称为二叉树表示法二叉链表表示法。
实现用二叉链表作为树的存储结构链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。
typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;5.5.2树与二叉树的转换
将树转化为二叉树进行处理利用二叉树的算法来实现对树的操作。
由于树和二叉树都可以用二叉链表作存储结构则以二叉链表作为媒介可以导出树与二叉树之间的一个对应关系。
1、树转二叉树
树转二叉树转换步骤兄弟相连留长子 加线在兄弟之间加一连线。 抹线对每个结点除了其左孩子外去除其与其余孩子之间的关系。 旋转以树的根结点为轴心将整数顺时针转45°。
2、二叉树转树
二叉树转树步骤左孩右右连双亲去掉原来右孩线
加线若p结点是双亲结点的左孩子则将p的右孩子右孩子的右孩子…沿分支找到的所有右孩子都与p的双亲用线连起来。抹线抹掉原二叉树中双亲与右孩子之间的连线。调整将结点按层次排列形成树结构。 5.5.3森林和二叉树的转化
1、森林转二叉树
森林转换成二叉树树边二叉根相连
将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一课树根结点为二叉树的根再以根结点为轴心顺时针旋转构成二叉树型结构。 2、二叉树转森林
二叉树转换成森林去掉全部右孩线孤立二叉再还原。 抹线将二叉树中根结点与其右孩子连线及沿又分支搜索到的所有右孩子间连线全部抹掉使之变成孤立的二叉树。 还原将孤立的二叉树还原成树。
5.5.4树与森林的遍历
1、树的遍历 先根次序遍历 若树不空则先访问根结点然后依次先根遍历各课子树。 后根次序遍历 若树不空则先依次后根遍历各棵子树然后访问根结点。 按层次遍历 若树不空则自上而下自左而右访问树中每个结点。
2、森林的遍历
将森林看作三部分构成
森林中第一棵树的根结点森林中第一棵树的子树森林森林中其他树构成的森林。 先序遍历依次从左至右对森林中的每一棵树进行先根遍历 若森林不为空则 访问森林中第一棵树的根结点先序遍历森林中第一棵树的子树森林先序遍历森林中除第一棵树之外其余树构成的森林。 中序遍历依次从左至右对森林中的每一颗树进行后根遍历 若森林不为空则 中序遍历森林中第一棵树的子树森林访问森林中第一棵树的根结点中序遍历森林中除第一棵树之外其余树构成的森林。
