树是一种非线性的数据结构
1,树是由 n(n>=0)个结点组成的有限集合
如果n = 0 ,称为空树
如果n > 0,则:
有一个特定的称之为根(root)的结点,它只有直接后继,但没有直接前驱
除了根以外的其他结点划分为:m(m>=0)个互不相交的有限集合,T0,T1,T2…Tn-1,每个集合又是一棵树,并且称之为根的子树
2,树中的概念:
树的结点包括一个数据及若干指向子树的分支
结点拥有的子树树称为结点的度
度为0的结点称为叶结点
度不为0的结点称为分支结点
树的度的定义为所有结点中的度的最大值
3,树中结点之间的关系
(1)结点的直接后继称为该结点的孩子
(2)相应的该结点称为孩子的双亲
(3)结点的孩子的孩子的……称为该结点的子孙
(4)相应的该结点称为子孙的祖先
(5)同一个双亲的孩子之间互称兄弟
4,树的深度或高度
(1)结点的层次
(2)根为第1层
(3)根的孩子为第2层
(4)……
(5)树中结点的最大层次称为树的深度或高度
5,如果树中结点的各子树从左向右是有次序的,子树间不能互换位置,则称该树为有序树,否则为无序树。
6,森林是由 n(n >=0)棵互不相交的树组成的集合
7,树的相关操作
树的操作
树的一些常用操作
->创建树
->销毁树
->清空树
->插入结点
->删除结点
->获取结点
->获取根结点
->获取树的结点数
->获取树的高度
->获取树的度
树在程序中表现为一种特殊的数据类型
树的操作在程序中的表现为一组函数
Tree:
Tree*Tree_Create();
voidTree_Destroy(Tree* tree);
voidTree_Clear(Tree* tree);
intTree_Insert(Tree* tree, TreeNode* node, int pos);
TreeNode*Tree_Delete(Tree* tree, int pos);
TreeNode*Tree_Get(Tree* tree, int pos);
TreeNode*Tree_Root(Tree* tree);
intTree_Height(Tree* tree);
intTree_Count(Tree* tree);
intTree_Degree(Tree* tree);
再来说下,这里树的基本存储结构。假定我们初始有一棵树,那么我们如何来规定他的存储结构呢?
首先,我们规定每个树结点中有三个属性(1)表示其父亲的指针(2)表示结点中的数据(3)表示孩子的链表,这里为什么是个链表呢?因为一个结点的的孩子可能有一个,也有可能有多个,所以用一个链表表示最为合适了。
第二,每个树之间的关系,我们可以模仿二叉树中的先序遍历思想,对这颗树进行遍历,我们知道,遍历的结果肯定是个序列,那么我们此时就可以果断的把这种序列认为是一种链表结构,那么后期对于树的操作也就可以移植到链表上来了。
最后,关于树的深度、度、删除、根结点的获取与计算,都是在表示那颗树的结点上来操作的。那么这里特别说明一下,由于整个树存在两个链表,所以对于每次删除,插入都要向两个链表中删除和插入。(一个结点既要存在于他父亲的孩子链表中,又要存在于表示整棵树的链表中)
这里我们用到了链表的知识,如果对于链表不熟悉,可以参阅链表的实现与操作(C语言实现)。这里有详尽的代码。
源代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #ifndef _GTREE_H_ #define _GTREE_H_ typedef void GTree; typedef void GTreeData; typedef void (GTree_Printf)(GTreeData*); GTree* GTree_Create(); void GTree_Destroy(GTree* tree); void GTree_Clear(GTree* tree); int GTree_Insert(GTree* tree, GTreeData* data, int pPos); GTreeData* GTree_Delete(GTree* tree, int pos); GTreeData* GTree_Get(GTree* tree, int pos); GTreeData* GTree_Root(GTree* tree); int GTree_Height(GTree* tree); int GTree_Count(GTree* tree); int GTree_Degree(GTree* tree); void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div); #endif |
CPP实现部分:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 | #include "stdafx.h" #include <malloc.h> #include "GTree.h" #include "LinkList.h" //树中的结点 typedef struct _tag_GTreeNode GTreeNode; struct _tag_GTreeNode { GTreeData* data; GTreeNode* parent; LinkList* child; }; //树 typedef struct _tag_TLNode TLNode; struct _tag_TLNode { LinkListNode header; GTreeNode* node; }; //打印树 static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div) { int i = 0 ; if ( (node != NULL) && (pFunc != NULL) ) { for (i= 0 ; i<format; i++)= "" {= "" printf( "%c" ,= "" div);= "" }= "" pfunc(node-= "" >data); printf( "\n" ); for (i= 0 ; i<linklist_length(node->child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); recursive_display(trNode->node, pFunc, format + gap, gap, div); } } } static void recursive_delete(LinkList* list, GTreeNode* node) { if ( (list != NULL) && (node != NULL) ) { GTreeNode* parent = node->parent; int index = - 1 ; int i = 0 ; //将结点从表示树的链表中删除 for (i= 0 ; i<linklist_length(list); i++)= "" {= "" tlnode*= "" trnode= "(TLNode*)LinkList_Get(list," i);= "" if (= "" trnode-= "" >node == node ) { LinkList_Delete(list, i); free(trNode); index = i; break ; } } //如果index>0,则表明他有父亲 if ( index >= 0 ) { if ( parent != NULL ) { //将他从他父亲的孩子链表中删除 for (i= 0 ; i<linklist_length(parent->child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i); if ( trNode->node == node ) { LinkList_Delete(parent->child, i); free(trNode); break ; } } } //如果他有儿子,将他的儿子们都杀死 while ( LinkList_Length(node->child) > 0 ) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0 ); recursive_delete(list, trNode->node); } LinkList_Destroy(node->child); free(node); } } } static int recursive_height(GTreeNode* node) { int ret = 0 ; if ( node != NULL ) { int subHeight = 0 ; int i = 0 ; for (i= 0 ; i<linklist_length(node->child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); subHeight = recursive_height(trNode->node); if ( ret < subHeight ) { ret = subHeight; } } ret = ret + 1 ; } return ret; } static int recursive_degree(GTreeNode* node) { int ret = - 1 ; if ( node != NULL ) { int subDegree = 0 ; int i = 0 ; ret = LinkList_Length(node->child); for (i= 0 ; i<linklist_length(node->child); i++) { TLNode* trNode = (TLNode*)LinkList_Get(node->child, i); subDegree = recursive_degree(trNode->node); if ( ret < subDegree ) { ret = subDegree; } } } return ret; } GTree* GTree_Create() { return LinkList_Create(); } void GTree_Destroy(GTree* tree) { GTree_Clear(tree); LinkList_Destroy(tree); } void GTree_Clear(GTree* tree) { GTree_Delete(tree, 0 ); } int GTree_Insert(GTree* tree, GTreeData* data, int pPos) { LinkList* list = (LinkList*)tree; //传进被插入的树,表示的实质为链表 //合法性判断 int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list)); //所插入的结点必须在树当中, //故而是pPos < LinkList_Length(list) if ( ret ) { TLNode* trNode = (TLNode*)malloc(sizeof(TLNode)); //创建一个结点,用于记录保存树的链表中的结点 TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode)); //孩子(是个链表) TLNode* pNode = (TLNode*)LinkList_Get(list, pPos); //从表示树的链表中获取要插入结点父母亲 GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode)); //要插入的结点,用于接收传进来的data ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL); //树中结点不能为空,该结点 if ( ret ) { cNode->data = data; //保存数据 cNode->parent = NULL; //现在还弄不清他的父母亲是谁 cNode->child = LinkList_Create(); //要插入的结点的孩子是个链表 trNode->node = cNode; //将要插入的结点赋值给表示树的链表 cldNode->node = cNode; //将要插入的结点赋值给树结点中的孩子链表 LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list)); //向表示树的链表中插入 if ( pNode != NULL ) //如果要插入的结点有父节点,就向父节点的子结点链表插入该结点 { cNode->parent = pNode->node; //认亲的过程 //正式加入大家庭 LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child)); } } else { free(trNode); free(cldNode); free(cNode); } } return ret; } //删除结点 GTreeData* GTree_Delete(GTree* tree, int pos) { TLNode* trNode = (TLNode*)LinkList_Get(tree, pos); GTreeData* ret = NULL; if ( trNode != NULL ) { ret = trNode->node->data; recursive_delete(tree, trNode->node); } return ret; } //获得指定位置的结点 GTreeData* GTree_Get(GTree* tree, int pos) { TLNode* trNode = (TLNode*)LinkList_Get(tree, pos); GTreeData* ret = NULL; if ( trNode != NULL ) { ret = trNode->node->data; } return ret; } //获得根结点 GTreeData* GTree_Root(GTree* tree) { return GTree_Get(tree, 0 ); } //求树的高度 int GTree_Height(GTree* tree) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0 ); int ret = 0 ; if ( trNode != NULL ) { ret = recursive_height(trNode->node); } return ret; } //求树的结点个数 int GTree_Count(GTree* tree) { return LinkList_Length(tree); } //求树的度 int GTree_Degree(GTree* tree) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0 ); int ret = - 1 ; if ( trNode != NULL ) { ret = recursive_degree(trNode->node); } return ret; } void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div) { TLNode* trNode = (TLNode*)LinkList_Get(tree, 0 ); if ( (trNode != NULL) && (pFunc != NULL) ) { recursive_display(trNode->node, pFunc, 0 , gap, div); } } </linklist_length(node-></linklist_length(node-></linklist_length(parent-></linklist_length(list);></linklist_length(node-></format;></malloc.h> |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | // 树.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "GTree.h" #include <stdlib.h> void printf_data(GTreeData* data) { printf( "%c" , ( int )data); } int _tmain( int argc, _TCHAR* argv[]) { GTree* tree = GTree_Create(); int i = 0 ; GTree_Insert(tree, (GTreeData*) 'A' , - 1 ); GTree_Insert(tree, (GTreeData*) 'B' , 0 ); GTree_Insert(tree, (GTreeData*) 'C' , 0 ); GTree_Insert(tree, (GTreeData*) 'D' , 0 ); GTree_Insert(tree, (GTreeData*) 'E' , 1 ); GTree_Insert(tree, (GTreeData*) 'F' , 1 ); GTree_Insert(tree, (GTreeData*) 'H' , 3 ); GTree_Insert(tree, (GTreeData*) 'I' , 3 ); GTree_Insert(tree, (GTreeData*) 'J' , 3 ); printf( "Tree Height: %d\n" , GTree_Height(tree)); printf( "Tree Degree: %d\n" , GTree_Degree(tree)); printf( "Full Tree:\n" ); GTree_Display(tree, printf_data, 2 , ' ' ); printf( "Get Tree Data:\n" ); for (i= 0 ; i<gtree_count(tree); i++)= "" {= "" printf_data(gtree_get(tree,= "" i));= "" printf( "\n" );= "" }= "" printf( "get=" " root=" " data:\n" );= "" printf_data(gtree_root(tree));= "" gtree_delete(tree,= "" 3 );= "" printf( "after=" " deleting=" " d:\n" );= "" gtree_display(tree,= "" printf_data,= "" 2 ,= "" &# 39 ;-&# 39 ;);= "" gtree_clear(tree);= "" clearing= "" tree:\n ");=" " '.');=" " gtree_destroy(tree);=" " system(" pause ");=" " return=" " 0;=" " <=" " pre=" "><br> 运行结果: <p></p> <p><strong></strong></p> <pre class = "brush:java;" >Tree Height: 3 Tree Degree: 3 Full Tree: A B E F C D H I J Get Tree Data: A B C D E F H I J Get Root Data: A After Deleting D: A --B ----E ----F --C After Clearing Tree: 请按任意键继续. . . </pre><br> <br> <p></p> <p><strong><br> </strong></p> <p><strong>如有错误,望不吝指出。</strong></p> <br> <br> </gtree_count(tree);></stdlib.h> |
联系客服