怎么做微拍网站,建设厅网站如何查询企业信息,网站建设包含哪些,荣耀手机商城**
一#xff1a;树的基本术语
1.定义 树是一种非线性结构#xff0c;只有一个根结点#xff0c;除根结点外每个孩子结点可以有多个后继#xff0c;没有后继的结点叫叶子结点。 2.概念 根结点#xff1a;没有前驱#xff1b; 孩子#xff1a;有前驱的结点#xff1b;…**
一树的基本术语
1.定义 树是一种非线性结构只有一个根结点除根结点外每个孩子结点可以有多个后继没有后继的结点叫叶子结点。 2.概念 根结点没有前驱 孩子有前驱的结点 双亲结点孩子结点的前驱 叶子没有孩子结点 结点度结点的分支数
树的度一棵树中最大结点度数 树的深度树的层次数目 有序树结点的子树从左到右有顺序 森林多棵互不相交的树的集合 3.二叉树 **特点特殊的树每个结点最多有两棵子树有左右顺序之分。 性质 1.第i层上最多2^(i-1)个结点最少0个 2.深度k最多2^k-1个结点最少k个结点 3.对于二叉树终端结点叶子结点数为n0,度为2的结点数为n2,则n0n21; 4.总结点数n,分支数B,则nB1,nn0n1n2,Bn12*n2; 5.具有n个结点的完全二叉树的深度:[log2^n]1;
二叉树的存储结构 对于非线性结构顺序二叉树仅适用于完全二叉树所有在这采用链式存储。
以下为二叉树的链式存储及基本操作 包含三种递归遍历。
#define CHAR /* 字符型 *//* #define INT /* 整型二者选一 */#includestring.h#includectype.h#includemalloc.h /* malloc()等 */#includelimits.h /* INT_MAX等 */#includestdio.h /* EOF(^Z或F6),NULL */#includestdlib.h /* atoi() */#includeio.h /* eof() */#includemath.h /* floor(),ceil(),abs() */#includeprocess.h /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status是函数的类型,其值是函数结果状态代码如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */#ifdef CHARtypedef char TElemType;TElemType Nil ; /* 字符型以空格符为空 */#endif#ifdef INTtypedef int TElemType;TElemType Nil0; /* 整型以0为空 */#endif/* c6-2.h 二叉树的二叉链表存储表示 */typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild; /* 左右孩子指针 */}BiTNode,*BiTree;Status InitBiTree(BiTree *T){ /* 操作结果: 构造空二叉树T */*TNULL;return OK;}void CreateBiTree(BiTree *T){ /* 算法6.4:按先序次序输入二叉树中结点的值可为字符型或整型在主程中 *//* 定义构造二叉链表表示的二叉树T。变量Nil表示空子树。有改动 */TElemType ch;#ifdef CHARscanf(%c,ch);#endif#ifdef INTscanf(%d,ch);#endifif(chNil) /* 空 */*TNULL;else{*T(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)-datach; /* 生成根结点 */CreateBiTree((*T)-lchild); /* 构造左子树 */CreateBiTree((*T)-rchild); /* 构造右子树 */}}Status BiTreeEmpty(BiTree T){ /* 初始条件: 二叉树T存在 *//* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */if(T)return FALSE;elsereturn TRUE;}#define ClearBiTree DestroyBiTreeint BiTreeDepth(BiTree T){ /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */int i,j;if(!T)return 0;if(T-lchild)iBiTreeDepth(T-lchild);elsei0;if(T-rchild)jBiTreeDepth(T-rchild);elsej0;return ij?i1:j1;}TElemType Root(BiTree T){ /* 初始条件: 二叉树T存在。操作结果: 返回T的根 */if(BiTreeEmpty(T))return Nil;elsereturn T-data;}void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1有改动 *//* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */if(T) /* T不空 */{Visit(T-data); /* 先访问根结点 */PreOrderTraverse(T-lchild,Visit); /* 再先序遍历左子树 */PreOrderTraverse(T-rchild,Visit); /* 最后先序遍历右子树 */}}void InOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 *//* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */if(T){InOrderTraverse(T-lchild,Visit); /* 先中序遍历左子树 */Visit(T-data); /* 再访问根结点 */InOrderTraverse(T-rchild,Visit); /* 最后中序遍历右子树 */}}void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 *//* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */if(T) /* T不空 */{PostOrderTraverse(T-lchild,Visit); /* 先后序遍历左子树 */PostOrderTraverse(T-rchild,Visit); /* 再后序遍历右子树 */Visit(T-data); /* 最后访问根结点 */}}Status visitT(TElemType e){#ifdef CHARprintf(%c ,e);#endif#ifdef INTprintf(%d ,e);#endifreturn OK;}void main(){int i;BiTree T,p,c;TElemType e1,e2;InitBiTree(T);printf(构造空二叉树后,树空否%d(1:是 0:否) 树的深度%d\n,BiTreeEmpty(T),BiTreeDepth(T));e1Root(T);if(e1!Nil)#ifdef CHARprintf(二叉树的根为: %c\n,e1);#endif#ifdef INTprintf(二叉树的根为: %d\n,e1);#endifelseprintf(树空无根\n);#ifdef CHARprintf(请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n);#endif#ifdef INTprintf(请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n);#endifCreateBiTree(T);printf(建立二叉树后,树空否%d(1:是 0:否) 树的深度%d\n,BiTreeEmpty(T),BiTreeDepth(T));e1Root(T);if(e1!Nil)#ifdef CHARprintf(二叉树的根为: %c\n,e1);#endif#ifdef INTprintf(二叉树的根为: %d\n,e1);#endifelseprintf(树空无根\n);printf(先序递归遍历二叉树:\n);PreOrderTraverse(T,visitT);printf(\n);printf(中序递归遍历二叉树:\n);InOrderTraverse(T,visitT);printf(\n);printf(后序递归遍历二叉树:\n);PostOrderTraverse(T,visitT);}
4.线索二叉树 特征LTag0:lchild域指示结点的左孩子 ———LTag1:lchild域指示结点的前驱 ———RTag0:lchild域指示结点的右孩子 ———RTag1:lchild域指示结点的后继 以这种结点结构构成的二叉树链表作为二叉树的存储结构叫做线索链表其中指向前驱和后继的指针叫做线索加上线索的二叉树叫线索二叉树。
5.树、二叉树、森林之间的转换 1.树和二叉树 树转化成二叉树1.加线兄弟相连2.抹线长兄为父3.旋转顺时针旋转90度 二叉树转化树过程相反。 2. 把如图所示的树转化成二叉树。
2.森林转化成二叉树 先把每棵树转换成二叉树把第二棵树根结点当作第一棵树的兄弟依次这样操作。
3.二叉树转化成森林 二叉树的根结点的右孩子必是森林孩子结点的右子树为兄弟。
6.赫夫曼树应用 定义又称最优树是一类带权值最短路径的树。 路径长度树中一个结点到另一个结点的分支数之和。 带权路径长度各分支数与上面的权值乘积之和。 树的带权路径长度WPL
最优二叉树或赫夫曼树:WPL最小的树。
**
详细问题请浏览本人其它博客谢谢关注
**
