首页 > 代码库 > 算法9---完全二叉树
算法9---完全二叉树
算法9---完全二叉树
树结构的基本特征
（1）在一个树结构中，有且仅有一个节点没有直接前驱，这个节点就是树的根节点；
（2）除了根节点外，其余结个节点有且仅有一个直接前驱；
（3）每个结点都可以有任意多个直接后继；
树有一些基本的概念要清楚
父结点和子结点；
兄弟结点；
结点的度；
树的度；
叶结点；
分支结点；
结点的层数；
树的深度；
有序树；
无序树；
森林；
首先二叉树有两种表示方式，一种是使用数组结构来进行顺序存储，
如下
1 #define MAXLEN 1002 typedef char DATA;3 typedef DATA seqbitree[MAXLEN];4 seqbitree bt;//定义保存二叉树的数组
还有一种方式是采用链表的方法进程存储，大多数情况下都是以这种方式；
这种链式存储结构的定义方式如下：
1 #define MAXLEN 100 2 typedef char DATA; 3 typedef struct chainTree 4 { 5 DATA nodeData; 6 7 struct chainTree *lsonNode; 8 struct chainTree *rsonNode; 9 struct chainTree *parentNode;10 }chainTreeType;
二叉树的完整的操作具体实现如下。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <conio.h> 4 5 #define MAXLEN 20 6 typedef char DATA; 7 typedef struct CBT 8 { 9 DATA data; 10 struct CBT *left; 11 struct CBT *right; 12 }CBTType; 13 14 CBTType *initTree() 15 { 16 CBTType *node; 17 if (node=(CBTType *)malloc(sizeof(CBTType))) 18 { 19 printf("please input the root! \n"); 20 scanf("%s",&node->data); 21 node->left=NULL; 22 node->right=NULL; 23 if (node!=NULL) 24 { 25 return node; 26 } 27 else 28 return NULL; 29 30 } 31 return NULL; 32 } 33 34 35 //查询节点是否存在 36 CBTType *Treefindnode(CBTType *treeNode,DATA data) 37 { 38 39 40 if (treeNode==NULL) 41 { 42 return NULL; 43 } 44 else 45 { 46 if (treeNode->data=http://www.mamicode.com/=data) 47 { 48 return treeNode ; 49 } 50 else 51 { 52 if (treeNode=Treefindnode(treeNode->left,data)) 53 { 54 return treeNode; 55 } 56 else if (treeNode=Treefindnode(treeNode->right,data)) 57 { 58 return treeNode; 59 } 60 else 61 return NULL; 62 } 63 } 64 } 65 66 //增加结点 67 68 void AddTreeNode(CBTType *treeNode) 69 { 70 CBTType *pnode,*parent; 71 DATA data; 72 char flag; 73 if (pnode=(CBTType*)malloc(sizeof(CBTType))) 74 { 75 printf("input the node data \n"); 76 fflush(stdin); 77 scanf("%s",&pnode->data); 78 pnode->left=NULL; 79 pnode->right=NULL; 80 81 printf("input the node‘s parent node\n"); 82 fflush(stdin); 83 scanf("%s",&data); 84 parent=Treefindnode(treeNode,data); 85 if (!parent) 86 { 87 printf("can‘t find the parent node!\n"); 88 free(pnode); 89 return ; 90 } 91 printf("1.add to the left node!\n2.add to the right node!"); 92 do 93 { 94 flag=getch(); 95 flag-=‘0‘; 96 if (flag==1||flag==2) 97 { 98 if (parent==NULL) 99 {100 printf("no parent node,please give parent node first!\n");101 }102 else103 {104 switch(flag)105 {106 case 1: //添加到左节点107 if (parent->left) //左节点不为空108 {109 printf("the lefe node is not empty!\n");110 }111 else112 {113 parent->left=pnode;114 }115 break;116 case 2:117 if (parent->right)118 {119 printf("the right node is not empty!\n");120 }121 else122 parent->right=pnode;123 break;124 default:125 printf("useless parameter!\n");126 }127 }128 }129 }while(flag!=1&&flag!=2);130 131 }132 }133 134 135 //获得左子树136 CBTType *Treeleftnode(CBTType *treeNode)137 {138 if (treeNode)139 {140 return treeNode->left;141 }142 else143 return NULL;144 }145 146 147 //获得右子树148 CBTType *Treerightnode(CBTType *treeNode)149 {150 if (treeNode)151 {152 return treeNode->right;153 }154 else155 return NULL;156 }157 158 159 //判断空树160 161 int Treeisempty(CBTType *TreeNode)162 {163 if(TreeNode)164 return 0;165 else166 return 1;167 }168 169 //计算二叉树的深度170 171 int Treedepth(CBTType *treeNode)172 {173 int depleft,depright;174 if (treeNode==NULL)175 {176 return 0;177 }178 else179 {180 depleft=Treedepth(treeNode->left);181 depright=Treedepth(treeNode->right);182 if (depleft>depright)183 {184 return depleft+1;185 }186 else187 return depright+1;188 }189 }190 191 192 //清空二叉树193 void ClearTree(CBTType *treeNode)194 {195 if (treeNode)196 {197 ClearTree(treeNode->left);198 ClearTree(treeNode->right);199 free(treeNode);200 treeNode=NULL;201 }202 }203 204 205 //显示节点数据206 void display(CBTType *p)207 {208 printf("%c",p->data);209 }210 211 //二叉树的遍历212 //层次遍历213 void levelTree(CBTType *treeNode)214 {215 CBTType *q[MAXLEN];216 int head=0,tail=0;217 if (treeNode)218 {219 tail=(tail+1)%MAXLEN;220 q[tail]=treeNode;221 }222 while(head!=tail)223 {224 head=(head+1)%MAXLEN;225 treeNode=q[head];226 if (treeNode->left!=NULL)227 {228 tail=(tail+1)%MAXLEN;229 q[tail]=treeNode->left;230 }231 if (treeNode->right!=NULL)232 {233 tail=(tail+1)%MAXLEN;234 q[tail]=treeNode->right;235 }236 }237 }238 239 240 241 //先序遍历，中序遍历和后序遍历242 243 void dlrTree(CBTType *p)244 {245 if(p)246 {247 printf("%c\n", p->data);248 dlrTree(p->left);249 dlrTree(p->right);250 }251 }252 253 void ldrTree(CBTType *p)254 {255 if(p)256 {257 dlrTree(p->left);258 printf("%c\n", p->data);259 dlrTree(p->right);260 }261 }262 263 void lrdTree(CBTType *p)264 {265 if(p)266 {267 dlrTree(p->left);268 dlrTree(p->right);269 printf("%c\n", p->data);270 }271 }272 273 274 int main()275 {276 CBTType *root=NULL;277 char flag1;278 char flag2;279 root =initTree();280 do{281 printf("please chose option to add node!\n");282 printf("0.quit\t");283 printf("1.add the bitree node.\n");284 flag1=getch();285 switch(flag1)286 {287 case ‘1‘:288 AddTreeNode(root);289 break;290 case ‘0‘:291 break;292 default:293 ;294 }295 296 }while(flag1!=‘0‘);297 298 299 do{300 printf("please chose the method to travese the tree,input 0 means quit!\n");301 printf("1.xian xu bian li\t");302 printf("2.zhong xu bian li\n");303 printf("3.xian xu bian li\t");304 printf("4.ceng ci bian li\n");305 flag2=getch();306 switch(flag2)307 {308 case ‘0‘:309 break;310 case ‘1‘:311 printf("the answer of dlrTree travese:\n");312 dlrTree(root);313 printf("\n");314 break;315 case ‘2‘:316 printf("the answer of ldrTree travese:\n");317 ldrTree(root);318 printf("\n");319 break;320 case ‘3‘:321 printf("the answer of lrdTree travese:\n");322 lrdTree(root);323 printf("\n");324 break;325 case ‘4‘:326 printf("the answer of levelTree travese:\n");327 levelTree(root);328 printf("\n");329 break;330 default:331 ;332 }333 }while(flag2!=‘0‘);334 335 printf("the depth of the tree is:%d\n", Treedepth(root));336 ClearTree(root);337 root=NULL;338 }
算法9---完全二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。