二叉树的创建与四种遍历之递归版本
程序员文章站
2022-07-05 09:20:32
...
#include <stdio.h> #include <stdlib.h> #define maxValue 1000 struct binTreeNode{ int data; binTreeNode * left,*right; }; binTreeNode * root; /* 递归创建二叉树,返回根节点指针 输入要求:类似先根遍历的输入顺序,如果哪个节点的孩子为空,那么输入0 例如针对 1 2 3 4 5 6 7 输入顺序为: 1 2 4 0 0 5 0 0 3 6 0 0 7 0 0 针对 1 2 3 4 5 0 7 输入顺序为: 1 2 4 0 0 5 0 0 3 0 7 0 0 */ binTreeNode * recCreateBinTree() { int _data = 0; binTreeNode * r; scanf("%d",&_data); if(_data == 0) r = NULL; else { r = (binTreeNode*)malloc(sizeof(binTreeNode)); r->data = _data; r->left = recCreateBinTree(); r->right = recCreateBinTree(); } return r; } /* 递归版本的先根遍历 */ void recPreOrder(binTreeNode *root) { if(root != NULL) { printf("%d\n",root->data); recPreOrder(root->left); recPreOrder(root->right); } } /* 递归版本的中根遍历 */ void recInOrder(binTreeNode *root) { if(root != NULL) { recInOrder(root->left); printf("%d\n",root->data); recInOrder(root->right); } } /* 递归版本的后根遍历 */ void recPostOrder(binTreeNode *root) { if(root != NULL) { recPostOrder(root->left); recPostOrder(root->right); printf("%d\n",root->data); } } /* 层次遍历 利用数组模拟队列 但是当元素多于1000时候,不可处理 */ void leverOrder(binTreeNode * root) { binTreeNode * queue[1000]; binTreeNode *tmp; int head = 0; int tail = 0; if(root != NULL) { queue[tail] = root; //队列操作,while前边先压入首元素 tail ++ ; while(tail > head) { tmp = queue[head]; //弹出队列头元素 head ++; printf("%d\n",tmp->data); //针对首元素的操作 //压入后继元素 if(tmp->left != NULL) { queue[tail] = tmp->left; tail ++ ; } if(tmp->right != NULL) { queue[tail] = tmp->right; tail ++; } } } } /* 层次遍历 利用数组模拟队列 而且利用取余,模拟循环队列 */ void leverOrder2(binTreeNode * root) { binTreeNode * queue[maxValue]; binTreeNode *tmp; int head = 0; int tail = 0; if(root != NULL) { queue[tail] = root; //队列操作,while前边先压入首元素 tail ++ ; while(tail != head) { tmp = queue[head]; //弹出队列头元素 head = (head + 1) % maxValue; printf("%d\n",tmp->data); //针对首元素的操作 //压入后继元素 if(tmp->left != NULL) { queue[tail] = tmp->left; tail = (tail + 1)% maxValue; } if(tmp->right != NULL) { queue[tail] = tmp->right; tail = (tail + 1)% maxValue; } } } } int main() { freopen("in.txt","r",stdin); root = recCreateBinTree(); fclose(stdin); printf("preOrder:\n"); recPreOrder(root); printf("inOrder:\n"); recInOrder(root); printf("postOrder:\n"); recPostOrder(root); printf("leverOrder:\n"); leverOrder2(root); return 0; }
下一篇: 二叉树的创建与四种遍历之递归版本