首页 > 代码库 > 浅谈数据结构之二叉树存储结构实现(七)
浅谈数据结构之二叉树存储结构实现(七)
树：是n个结点的有限集；n=0时称为空树。在任意一棵非空树中，有且只有一个特定的结点称为根结点；其余的结点可分为m(m>0)个互不相交的有限集，其中每一个有限集都是一棵子树。结点拥有的子树数称为结点的度；度为0的结点称为叶结点或者终端结点，度不为0的结点称为分支结点或者非终端结点；树的度就是树内各结点的度的最大值。
二叉树的特点有：(1).每个结点最多有两棵子树，所以二叉树不存在度大于2的结点(注意：不是只有两棵子树，而是最多有两棵子树，没有子树或者有一颗子树都是可以的);(2).左子树和右子树都是有顺序的，次序不能任意颠倒；(3).即使只有一棵子树，也要区分清它是左子树还是右子树。
对于树这种一对多的结构来说，简单的顺序存储和链式存储结构都不能满足树的存储结构的实现；不过可以利用顺序存储与链式存储的特点来实现树的存储结构的表示。但对于二叉树这种特殊的树来说，它的顺序存储结构完全可以实现；用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲和孩子的关系，左右兄弟的关系。二叉树的链式存储结构，我们一般称为二叉链表，即为它设计一个数据域和两个指针域，其中两个指针域分别存放指向左孩子和右孩子的指针。
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。二叉树的遍历方式主要有四种：(1).前序遍历，规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树；(2).中序遍历，规则是若二叉树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树；(3).后序遍历，若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历左右子树，最后访问根结点；(4).层序遍历，规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是从根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序依次访问。
二叉树存储结构的实现，遍历方式源程序代码如下所示：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <math.h> 4 5 #define OK 1 6 #define ERROR 0 7 #define TRUE 1 8 #define FALSE 0 9 10 #define MAXSIZE 100 /* 存储空间初始分配量 */ 11 #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */ 12 #define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */ 13 14 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 15 typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ 16 typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */ 17 18 typedef struct 19 { 20 int level,order; /* 结点的层,本层序号(按满二叉树计算) */ 21 }Position; 22 23 TElemType Nil=0; /* 设整型以0为空 */ 24 25 Status visit(TElemType c) 26 { 27 printf("%d ",c); 28 return OK; 29 } 30 31 /* 构造空二叉树T。因为T是固定数组，不会改变，故不需要& */ 32 Status InitBiTree(SqBiTree T) 33 { 34 int i; 35 for(i=0;i<MAX_TREE_SIZE;i++) 36 T[i]=Nil; /* 初值为空 */ 37 return OK; 38 } 39 40 /* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */ 41 Status CreateBiTree(SqBiTree T) 42 { 43 int i=0; 44 printf("请按层序输入结点的值(整型)，0表示空结点，输99结束。结点数≤%d:\n",MAX_TREE_SIZE); 45 while(i<10) 46 { 47 T[i]=i+1; 48 49 if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此结点(不空)无双亲且不是根 */ 50 { 51 printf("出现无双亲的非根结点%d\n",T[i]); 52 exit(ERROR); 53 } 54 i++; 55 } 56 while(i<MAX_TREE_SIZE) 57 { 58 T[i]=Nil; /* 将空赋值给T的后面的结点 */ 59 i++; 60 } 61 62 return OK; 63 } 64 65 /* 初始条件: 二叉树T存在 */ 66 /* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */ 67 Status BiTreeEmpty(SqBiTree T) 68 { 69 if(T[0]==Nil) /* 根结点为空,则树空 */ 70 return TRUE; 71 else 72 return FALSE; 73 } 74 75 /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */ 76 int BiTreeDepth(SqBiTree T) 77 { 78 int i,j=-1; 79 for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */ 80 if(T[i]!=Nil) 81 break; 82 i++; 83 do 84 j++; 85 while(i>=powl(2,j)); /* 计算2的j次幂。 */ 86 return j; 87 } 88 89 /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */ 90 /* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */ 91 TElemType Value(SqBiTree T,Position e) 92 { 93 return T[(int)powl(2,e.level-1)+e.order-2]; 94 } 95 96 /* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */ 97 /* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */ 98 Status Assign(SqBiTree T,Position e,TElemType value) 99 { 100 int i=(int)powl(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */ 101 if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */ 102 return ERROR; 103 else if(value=http://www.mamicode.com/=Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 给双亲赋空值但有叶子（不空） */ 104 return ERROR; 105 T[i]=value; 106 return OK; 107 } 108 109 /* 初始条件: 二叉树T存在,e是T中某个结点 */ 110 /* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */ 111 TElemType Parent(SqBiTree T,TElemType e) 112 { 113 int i; 114 if(T[0]==Nil) /* 空树 */ 115 return Nil; 116 for(i=1;i<=MAX_TREE_SIZE-1;i++) 117 if(T[i]==e) /* 找到e */ 118 return T[(i+1)/2-1]; 119 return Nil; /* 没找到e */ 120 } 121 122 123 /* 初始条件: 二叉树T存在,e是T中某个结点 */ 124 /* 操作结果: 返回e的左孩子。若e无左孩子,则返回＂空＂ */ 125 TElemType LeftChild(SqBiTree T,TElemType e) 126 { 127 int i; 128 if(T[0]==Nil) /* 空树 */ 129 return Nil; 130 for(i=0;i<=MAX_TREE_SIZE-1;i++) 131 if(T[i]==e) /* 找到e */ 132 return T[i*2+1]; 133 return Nil; /* 没找到e */ 134 } 135 136 /* 初始条件: 二叉树T存在,e是T中某个结点 */ 137 /* 操作结果: 返回e的右孩子。若e无右孩子,则返回＂空＂ */ 138 TElemType RightChild(SqBiTree T,TElemType e) 139 { 140 int i; 141 if(T[0]==Nil) /* 空树 */ 142 return Nil; 143 for(i=0;i<=MAX_TREE_SIZE-1;i++) 144 if(T[i]==e) /* 找到e */ 145 return T[i*2+2]; 146 return Nil; /* 没找到e */ 147 } 148 149 /* 初始条件: 二叉树T存在,e是T中某个结点 */ 150 /* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */ 151 TElemType LeftSibling(SqBiTree T,TElemType e) 152 { 153 int i; 154 if(T[0]==Nil) /* 空树 */ 155 return Nil; 156 for(i=1;i<=MAX_TREE_SIZE-1;i++) 157 if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */ 158 return T[i-1]; 159 return Nil; /* 没找到e */ 160 } 161 162 /* 初始条件: 二叉树T存在,e是T中某个结点 */ 163 /* 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂ */ 164 TElemType RightSibling(SqBiTree T,TElemType e) 165 { 166 int i; 167 if(T[0]==Nil) /* 空树 */ 168 return Nil; 169 for(i=1;i<=MAX_TREE_SIZE-1;i++) 170 if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */ 171 return T[i+1]; 172 return Nil; /* 没找到e */ 173 } 174 175 /* PreOrderTraverse()调用 */ 176 void PreTraverse(SqBiTree T,int e) 177 { 178 visit(T[e]); 179 if(T[2*e+1]!=Nil) /* 左子树不空 */ 180 PreTraverse(T,2*e+1); 181 if(T[2*e+2]!=Nil) /* 右子树不空 */ 182 PreTraverse(T,2*e+2); 183 } 184 185 /* 初始条件: 二叉树存在 */ 186 /* 操作结果: 先序遍历T。*/ 187 Status PreOrderTraverse(SqBiTree T) 188 { 189 if(!BiTreeEmpty(T)) /* 树不空 */ 190 PreTraverse(T,0); 191 printf("\n"); 192 return OK; 193 } 194 195 /* InOrderTraverse()调用 */ 196 void InTraverse(SqBiTree T,int e) 197 { 198 if(T[2*e+1]!=Nil) /* 左子树不空 */ 199 InTraverse(T,2*e+1); 200 visit(T[e]); 201 if(T[2*e+2]!=Nil) /* 右子树不空 */ 202 InTraverse(T,2*e+2); 203 } 204 205 /* 初始条件: 二叉树存在 */ 206 /* 操作结果: 中序遍历T。*/ 207 Status InOrderTraverse(SqBiTree T) 208 { 209 if(!BiTreeEmpty(T)) /* 树不空 */ 210 InTraverse(T,0); 211 printf("\n"); 212 return OK; 213 } 214 215 /* PostOrderTraverse()调用 */ 216 void PostTraverse(SqBiTree T,int e) 217 { 218 if(T[2*e+1]!=Nil) /* 左子树不空 */ 219 PostTraverse(T,2*e+1); 220 if(T[2*e+2]!=Nil) /* 右子树不空 */ 221 PostTraverse(T,2*e+2); 222 visit(T[e]); 223 } 224 225 /* 初始条件: 二叉树T存在 */ 226 /* 操作结果: 后序遍历T。 */ 227 Status PostOrderTraverse(SqBiTree T) 228 { 229 if(!BiTreeEmpty(T)) /* 树不空 */ 230 PostTraverse(T,0); 231 printf("\n"); 232 return OK; 233 } 234 235 /* 层序遍历二叉树 */ 236 void LevelOrderTraverse(SqBiTree T) 237 { 238 int i=MAX_TREE_SIZE-1,j; 239 while(T[i]==Nil) 240 i--; /* 找到最后一个非空结点的序号 */ 241 for(j=0;j<=i;j++) /* 从根结点起,按层序遍历二叉树 */ 242 if(T[j]!=Nil) 243 visit(T[j]); /* 只遍历非空的结点 */ 244 printf("\n"); 245 } 246 247 /* 逐层、按本层序号输出二叉树 */ 248 void Print(SqBiTree T) 249 { 250 int j,k; 251 Position p; 252 TElemType e; 253 for(j=1;j<=BiTreeDepth(T);j++) 254 { 255 printf("第%d层: ",j); 256 for(k=1;k<=powl(2,j-1);k++) 257 { 258 p.level=j; 259 p.order=k; 260 e=Value(T,p); 261 if(e!=Nil) 262 printf("%d:%d ",k,e); 263 } 264 printf("\n"); 265 } 266 } 267 268 269 int main() 270 { 271 Status i; 272 Position p; 273 TElemType e; 274 SqBiTree T; 275 276 InitBiTree(T); 277 CreateBiTree(T); 278 printf("1.建立二叉树后,树的深度=%d\n",BiTreeDepth(T)); 279 280 printf("2.层序遍历二叉树: "); 281 LevelOrderTraverse(T); 282 283 printf("3.前序遍历二叉树: "); 284 PreOrderTraverse(T); 285 286 printf("4.中序遍历二叉树: "); 287 InOrderTraverse(T); 288 289 printf("5.后序遍历二叉树: "); 290 PostOrderTraverse(T); 291 292 printf("6.修改结点的层号2,本层序号1;\n"); 293 p.level=2; 294 p.order=1; 295 e=Value(T,p); 296 printf("7.待修改结点的原值为%d,请输入新值: %d\n",e,36); 297 e=36; 298 Assign(T,p,e); 299 300 printf("8.前序遍历二叉树: "); 301 PreOrderTraverse(T); 302 303 printf("9.后序遍历二叉树: "); 304 PostOrderTraverse(T); 305 306 printf("10.结点%d的双亲为%d;左右孩子分别为",e,Parent(T,e)); 307 printf("%d,%d;左右兄弟分别为",LeftChild(T,e),RightChild(T,e)); 308 printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e)); 309 310 ClearBiTree(T); 311 printf("11.清空二叉树后，树的深度=%d\n",BiTreeDepth(T)); 312 313 return 0; 314 }
浅谈数据结构之二叉树存储结构实现(七)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。