二叉树代码
|
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 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 |
#include <stdio.h> #include <malloc.h> #include <iostream> #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct node { ElemType data; //数据元素 struct node* lchild; //指向左孩子节点 struct node* rchild; //指向右孩子节点 } BTNode; //二叉树本身有节点，是无形的树（因为链表节点结构） //，创建以及输出二叉树，则是为了视觉效果 ，但反过来没有了创建，也不行 void CreateBTree(BTNode*& b, char* str) //创建二叉树 { BTNode* St[MaxSize], * p = NULL; int top = -1, k, j = 0; char ch; b = NULL; //建立的二叉树初始时为空 ch = str[j]; while (ch != '\0') //str未扫描完时循环 { switch (ch) { case '(':top++; St[top] = p; k = 1; break; //为左孩子节点 case ')':top--; break; case ',':k = 2; break; //为孩子节点右节点 default:p = (BTNode*)malloc(sizeof(BTNode)); p->data = ch; p->lchild = p->rchild = NULL; if (b == NULL) //*p为二叉树的根节点 b = p; else //已建立二叉树根节点 { switch (k) { case 1:St[top]->lchild = p; break; case 2:St[top]->rchild = p; break; } } } j++; ch = str[j]; } } void DestroyBTree(BTNode*& b) { if (b != NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } //查找某个节点 BTNode* FindNode(BTNode* b, ElemType x) { BTNode* p; if (b == NULL) return NULL; else if (b->data == x) return b; else { p = FindNode(b->lchild, x); if (p != NULL) return p; else return FindNode(b->rchild, x); } } //返回某个节点的左节点 BTNode* LchildNode(BTNode* p) { return p->lchild; } //返回某个节点的右节点 BTNode* RchildNode(BTNode* p) { return p->rchild; } //返回树的高度 int BTHeight(BTNode* b) { int lchildh, rchildh; if (b == NULL) return(0); //空树的高度为0 else { lchildh = BTHeight(b->lchild); //求左子树的高度为lchildh rchildh = BTHeight(b->rchild); //求右子树的高度为rchildh return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); } } void DispBTree(BTNode* b) { if (b != NULL) { /*printf("%c", b->data);*/ cout << b->data; if (b->lchild != NULL || b->rchild != NULL) { printf("("); //有孩子节点时才输出( DispBTree(b->lchild); //递归处理左子树 if (b->rchild != NULL) printf(","); //有右孩子节点时才输出, DispBTree(b->rchild); //递归处理右子树 printf(")"); //有孩子节点时才输出) } } } void PreOrder(BTNode* b) //先序遍历的递归算法 { if (b != NULL) { //printf("%c ", b->data); //访问根结点 cout << b->data << " "; PreOrder(b->lchild); //先序遍历左子树 PreOrder(b->rchild); //先序遍历右子树 } } void InOrder(BTNode* b) //中序遍历的递归算法 { if (b != NULL) { InOrder(b->lchild); //中序遍历左子树 //printf("%c ", b->data); //访问根结点 cout << b->data << " "; InOrder(b->rchild); //中序遍历右子树 } } void PostOrder(BTNode* b) //后序遍历的递归算法 { if (b != NULL) { PostOrder(b->lchild); //后序遍历左子树 PostOrder(b->rchild); //后序遍历右子树 //printf("%c ", b->data); //访问根结点 cout << b->data << " "; } } //-------------------------------------------------------- //--循环队列基本运算算法---------------------------------- //-------------------------------------------------------- typedef struct { BTNode* data[MaxSize]; //存放队中元素 int front, rear; //队头和队尾指针 } SqQueue; //顺序队类型 void InitQueue(SqQueue*& q) //初始化队列 { q = (SqQueue*)malloc(sizeof(SqQueue)); q->front = q->rear = 0; } void DestroyQueue(SqQueue*& q) //销毁队列 { free(q); } bool QueueEmpty(SqQueue* q) //判断队列是否为空 { return(q->front == q->rear); } bool enQueue(SqQueue*& q, BTNode* e) //进队列 { if ((q->rear + 1) % MaxSize == q->front) //队满上溢出 return false; q->rear = (q->rear + 1) % MaxSize; q->data[q->rear] = e; return true; } bool deQueue(SqQueue*& q, BTNode*& e) //出队列 { if (q->front == q->rear) //队空下溢出 return false; q->front = (q->front + 1) % MaxSize; e = q->data[q->front]; return true; } //-------------------------------------------------------- //层次遍历输出二叉树 void LevelOrder(BTNode* b) { BTNode* p; SqQueue* qu; InitQueue(qu); //初始化队列 enQueue(qu, b); //根结点指针进入队列 while (!QueueEmpty(qu)) //队不为空循环 { deQueue(qu, p); //出队节点p printf("%c ", p->data); //访问节点p if (p->lchild != NULL) //有左孩子时将其进队 enQueue(qu, p->lchild); if (p->rchild != NULL) //有右孩子时将其进队 enQueue(qu, p->rchild); } } /** 根据先序遍历和中序遍历求出二叉树 扩展知识：这里理解一下指针就是数组的： int a[3] ={1,2,3}; int *b =a; int *c =a+2; cout<<a<<endl;//0x6ffe00 cout<<*b<<endl;//1 cout<<*c<<endl; //3 //指向指针的指针，和链表那样，d指针和b指针指向同一个地址 int *d = b; cout<<d<<endl;//0x6ffdf0 cout<<*d<<endl;//1 //指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数， int count =c-b; cout<<count<<endl; */ BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length); BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder); BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length) { if (preorder == NULL || inorder == NULL || length <= 0) { return NULL; } return ConstructCoreByPreAndIn(preorder, preorder + length - 1, inorder, inorder + length - 1); } //startPreOrder表示PreOrder的起始地址，endPreOrder表示PreOrder的结束地址 BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder) { //rootVal表示跟节点数据 ElemType rootVal = *startPreOrder;//{ 1, 2, 4, 7, 3, 5, 6, 8 }; // 前序遍历的第一个数字为根节点 BTNode* root = new BTNode(); root->data = rootVal; root->lchild = NULL; root->rchild = NULL; // 如果输入的只有一个数字,这里是把地址作比较！ if (startPreOrder == endPreOrder) { // 如果中序遍历也只有一个数字并且这两个数字相等 if (startInOrder == endInOrder && *startPreOrder == *startInOrder) { return root; } else { //throw exception("Invalid input"); cout << "Invalid Input" << endl; return NULL; } } // 在中序遍历中找到根节点位置 ElemType* rootInOrder = startInOrder; while (rootInOrder <= endInOrder && *rootInOrder != rootVal) { rootInOrder++; } if (rootInOrder > endInOrder || *rootInOrder != rootVal) { //throw exception("Invalid Input"); cout << "Invalid Input" << endl; return NULL; } //{ 1, 2, 4, 7, 3, 5, 6, 8 }; //{ 4, 7, 2, 1, 5, 3, 8, 6 };rootInOrder 1 //lefyLength = 3 - 0; //leftPreOrderEnd = 0 + 3; //在中序遍历中找到根节点，根据中序遍历计算左子树长度 // int leftLength = rootInOrder - startInOrder; int* leftPreOrderEnd = startPreOrder + leftLength; //从广度思考去想，root=1的左右子树就是这两个（247）（3568） //那么直接root->lchild和root->rchild给他们和下面main中这句 //BTNode* root = Construct(preOrder, inOrder, 8); //是一样的，这点理解后，就只有一个目的，找出（247）（3568）！ //这就很简单了，后序遍历大同小异 if (leftLength > 0) { //2,4,7 || 4,7,2 root->lchild = ConstructCoreByPreAndIn(startPreOrder + 1, leftPreOrderEnd, startInOrder, rootInOrder - 1); } if (leftLength < endPreOrder - startPreOrder) { //3,5,6,8 || 5,3,8,6 root->rchild = ConstructCoreByPreAndIn(leftPreOrderEnd + 1, endPreOrder, rootInOrder + 1, endInOrder); } return root; } /** 根据中序遍历和后序遍历求出二叉树 */ BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length); BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder); BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length) { if (postorder == NULL || inorder == NULL || length <= 0) { return NULL; } return ConstructCoreByPostAndIn(postorder, postorder + length - 1 , inorder, inorder + length - 1); } BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder) { //rootVal表示跟节点数据 ElemType rootVal = *endPostOrder;//1 // 调试： cout << "k: "<< rootVal << endl; // 后序遍历的最后一个数字为根节点 BTNode* root = new BTNode(); root->data = rootVal; root->lchild = NULL; root->rchild = NULL; // 如果输入的只有一个数字 if (startPostOrder == endPostOrder) { // 如果中序遍历也只有一个数字并且这两个数字相等 if (startInOrder == endInOrder && *startPostOrder == *startInOrder) { return root; } else { cout << "Invalid Input" << endl; return NULL; } } // 在中序遍历中找到根节点位置 ElemType* rootInOrder = startInOrder; while (rootInOrder <= endInOrder && *rootInOrder != rootVal) { rootInOrder++; } if (rootInOrder > endInOrder || *rootInOrder != rootVal) { cout << "xxxInvalid Input" << endl; return NULL; } /** * endPostOrder会每次-1，当兵临到全部递归完跟节点的左子树时，endPostOrder再减去1就会越界了， leftLength就是左子树的长度，在前序和中序遍历时，当其大于0遍历左子树，当其，小于，。。。 对于前序和中序遍历，逼近根节点的左子树时候，是start在逼近，end不动，一步步逼近 对于后续和中序遍历，逼近根节点的左子树时候，是start不动，end在逼近， 这就会出现一个不同的判断现象，start逼近，不会越界，临界值是0；end逼近，会越界，临界值指向-4123123213xxx */ //leftLength左子树的长度,leftPostOrderEnd后序遍历中左子树结束的地址 int leftLength = rootInOrder - startInOrder;//3 //int* leftPreOrderEnd = startPreOrder + leftLength; int* leftPostOrderEnd = startPostOrder + leftLength ;//0+3 if (leftLength > 0) { //传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址） root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1); } //rigthLength = end - start -leftLength //rightLength > 0 等价于 //leftLength <end - start if (leftLength < endPostOrder - startPostOrder) { //cout << *leftPostOrderEnd << *endPostOrder << *rootInOrder << *endInOrder << endl; root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder + 1, endInOrder); } return root; } int main() { BTNode* b; CreateBTree(b, "A(B(D(,G)),C(E,F))"); printf("b:"); DispBTree(b); printf("\n"); printf("先序遍历序列:"); PreOrder(b); printf("\n"); printf("中序遍历序列:"); InOrder(b); printf("\n"); printf("后序遍历序列:"); PostOrder(b); printf("\n"); printf("层次遍历序列:"); LevelOrder(b); printf("\n"); DestroyBTree(b); // ElemType preOrder[8] = { 1, 2, 4, 7, 3, 5, 6, 8 }; ElemType inOrder[8] = { 4, 7, 2, 1, 5, 3, 8, 6 }; ElemType postOrder[8] = { 7, 4, 2, 5, 8, 6, 3, 1 }; BTNode* root = ConstructByPreAndIn(preOrder, inOrder, 8); DispBTree(root); cout << endl; BTNode* root2 = ConstructByPostAndIn(postOrder, inOrder, 8); DispBTree(root); cout << endl; return 0; } |
代码讲解
存储结构
|
1 2 3 4 5 6 7 8 9 10 11 |
typedef struct node { ElemType data; //数据元素 struct node* lchild; //指向左孩子节点 struct node* rchild; //指向右孩子节点 } BTNode; typedef struct linknode{ int data; struct linknode *next; }sqstack; |
采用指针+结点来存储二叉树，链表栈也是如此， BTNode本身也是一个指针节点，可以指向和其一样结构的地址，所以，struct结构体中的结点也是struct结构体类型
根据中后序遍历求树思路
|
1 2 3 |
ElemType preOrder[7] = { 'A','B','D','G','C','E','F' }; ElemType inOrder[7] = { 'D','G','B','A','E','C','F' }; ElemType postOrder[7] = { 'G','D','B','E','F','C','A' }; |
先观察后序遍历和中序遍历的数组分析一下，可以发现，后序遍历的最后一个值就是根节点，又可以从中序遍历中找出根节点，中序遍历的根节点前面都是左子树，根节点的后面都是右子树；这里所说的左右子树是相对于根节点A的。那么，现在我们得到的数据有，根节点A，根节点A左边的所有左子树x，根节点A右边的所有右子树y。对于x，y两棵树，就是和总树一样。又可以使用同样的方法去求根节点和左右子树。这就是递归方法了。
如何把求出的根节点存到结点表示的树中？在使用函数求出根节点A后，在使用函数递归调用，求出的A的左边的左子树的根节点，不就是根结点A的左结点吗？
|
1 2 |
//传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址） root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1); |
|
1 |
root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder + 1, endInOrder); |
这个问题也解决了，最终函数会返回一个头结点root给我们，并且已经帮我们拼接好了root结点下面的所有结点。
指针与数组知识
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
int a[3] ={1,2,3}; int *b =a; int *c =a+2; cout<<a<<endl;//0x6ffe00 cout<<*b<<endl;//1 cout<<*c<<endl; //3 //指向指针的指针，和链表那样，d指针和b指针指向同一个地址 int *d = b; cout<<d<<endl;//0x6ffdf0 cout<<*d<<endl;//1 //指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数， int count =c-b; cout<<count<<endl; // 重合指针相减为0 cout<<"d-b: "<<d-b<<endl; cout<<"------------------------"<<endl; char p[4] = {'a','b','c','d'}; char *q = p; cout<<q<<endl;//abcd cout<<q+2<<endl;//cd |
运行结果：
0x6ffdd0
1
3
0x6ffdd0
1
2
d-b: 0
————————
abcd
cd
