树的知识点总结-数据结构
|
** 一：树的基本术语1.定义 树是一种非线性结构，只有一个根结点，除根结点外每个孩子结点可以有多个后继，没有后继的结点叫叶子结点。 2.概念 根结点：没有前驱； 孩子：有前驱的结点； 双亲结点：孩子结点的前驱； 叶子：没有孩子结点 结点度：结点的分支数； 树的度：一棵树中最大结点度数； 树的深度：树的层次数目； 有序树：结点的子树从左到右有顺序； 森林：多棵互不相交的树的集合； 3.二叉树 **特点：特殊的树，每个结点最多有两棵子树，有左右顺序之分。 性质： 1.第i层上最多2^(i-1)个结点，最少0个； 2.深度k，最多2^k-1个结点，最少k个结点； 3.对于二叉树，终端结点（叶子结点）数为n0,度为2的结点数为n2,则n0=n2+1; 4.总结点数n,分支数B,则n=B+1,n=n0+n1+n2,B=n1+2*n2; 5.具有n个结点的完全二叉树的深度:[log2^n]+1; 二叉树的存储结构： 对于非线性结构，顺序二叉树仅适用于完全二叉树，所有在这采用链式存储。 以下为二叉树的链式存储及基本操作 包含三种递归遍历。 #define CHAR /* 字符型 */ /* #define INT /* 整型（二者选一） */ #include #include #include #include #include #include #include #include #include /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ #ifdef CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空 */ #endif #ifdef INT typedef int TElemType; TElemType Nil=0; /* 整型以0为空 */ #endif /* c6-2.h 二叉树的二叉链表存储表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; Status InitBiTree(BiTree *T) { /* 操作结果: 构造空二叉树T */ *T=NULL; return OK; } void CreateBiTree(BiTree *T) { /* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中 */ /* 定义），构造二叉链表表示的二叉树T。变量Nil表示空（子）树。有改动 */ TElemType ch; #ifdef CHAR scanf("%c",&ch); #endif #ifdef INT scanf("%d",&ch); #endif if(ch==Nil) /* 空 */ *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; /* 生成根结点 */ CreateBiTree(&(*T)->lchild); /* 构造左子树 */ CreateBiTree(&(*T)->rchild); /* 构造右子树 */ } } Status BiTreeEmpty(BiTree T) { /* 初始条件: 二叉树T存在 */ /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */ if(T) return FALSE; else return TRUE; } #define ClearBiTree DestroyBiTree int BiTreeDepth(BiTree T) { /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */ int i,j; if(!T) return 0; if(T->lchild) i=BiTreeDepth(T->lchild); else i=0; if(T->rchild) j=BiTreeDepth(T->rchild); else j=0; return i>j?i+1:j+1; } TElemType Root(BiTree T) { /* 初始条件: 二叉树T存在。操作结果: 返回T的根 */ if(BiTreeEmpty(T)) return Nil; else return 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,Visit是对结点操作的应用函数 */ /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) { InOrderTraverse(T->lchild,Visit); /* 先中序遍历左子树 */ Visit(T->data); /* 再访问根结点 */ InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */ } } void PostOrderTraverse(BiTree T,Visit是对结点操作的应用函数 */ /* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) /* T不空 */ { PostOrderTraverse(T->lchild,Visit); /* 先后序遍历左子树 */ PostOrderTraverse(T->rchild,Visit); /* 再后序遍历右子树 */ Visit(T->data); /* 最后访问根结点 */ } } Status visitT(TElemType e) { #ifdef CHAR printf("%c ",e); #endif #ifdef INT printf("%d ",e); #endif return OK; } void main() { int i; BiTree T,p,c; TElemType e1,e2; InitBiTree(&T); printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%dn",BiTreeEmpty(T),BiTreeDepth(T)); e1=Root(T); if(e1!=Nil) #ifdef CHAR printf("二叉树的根为: %cn",e1); #endif #ifdef INT printf("二叉树的根为: %dn",e1); #endif else printf("树空，无根n"); #ifdef CHAR printf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)n"); #endif #ifdef INT printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)n"); #endif CreateBiTree(&T); printf("建立二叉树后,e1); #endif else printf("树空，无根n"); printf("先序递归遍历二叉树:n"); PreOrderTraverse(T,visitT); printf("n"); printf("中序递归遍历二叉树:n"); InOrderTraverse(T,visitT); printf("n"); printf("后序递归遍历二叉树:n"); PostOrderTraverse(T,visitT); } 4.线索二叉树 特征：LTag=0:lchild域指示结点的左孩子 ———LTag=1:lchild域指示结点的前驱 ———RTag=0:lchild域指示结点的右孩子 ———RTag=1:lchild域指示结点的后继 以这种结点结构构成的二叉树链表作为二叉树的存储结构，叫做线索链表，其中指向前驱和后继的指针叫做线索，加上线索的二叉树叫线索二叉树。 5.树、二叉树、森林之间的转换 1.树和二叉树： 树转化成二叉树：1.加线：兄弟相连；2.抹线：长兄为父；3.旋转：顺时针旋转90度； 二叉树转化树：过程相反。 2. 把如图所示的树转化成二叉树。
2.森林转化成二叉树： 先把每棵树转换成二叉树，把第二棵树根结点当作第一棵树的兄弟，依次这样操作。 3.二叉树转化成森林： 二叉树的根结点的右孩子必是森林，孩子结点的右子树为兄弟。
6.赫夫曼树应用 定义：又称最优树，是一类带权值最短路径的树。 路径长度：树中一个结点到另一个结点的分支数之和。 带权路径长度：各分支数与上面的权值乘积之和。 树的带权路径长度：WPL 最优二叉树或赫夫曼树:WPL最小的树。 ** 详细问题请浏览本人其它博客，谢谢关注** （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
