二叉树的创建与四种遍历之递归版本

#include <stdio.h>#include <stdlib.h>#define maxValue 1000struct binTreeNode{int data;binTreeNode * left,*right;};binTreeNode * root;/*递归创建二叉树，返回根节点指针输入要求：类似先根遍历的输入顺序，如果哪个节点的孩子为空，那么输入0例如针对12345 67输入顺序为:124005003600700针对12345 07输入顺序为:1240050030700*/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);">  您还没有登录,请您登录后再发表评论