简单的树的递归、非递归创建,前序中序后序遍历
c语言写着还挺带感

#include<stdlib.h>#define null 0struct tree{struct tree* left;int value;struct tree* right;};typedef struct tree Tree;Tree* root;Tree* insert_rcs(Tree* root, int value){//只在叶节点位置插入 if(root == null){root = malloc(sizeof(Tree));root->value = value;root->left = null;root->right = null;//返回新增的叶节点 return root;}if(root->value > value){root->left = insert_rcs(root->left, value);}else{root->right = insert_rcs(root->right, value);}return root;}Tree* insert_no_rcs(Tree* root, int value){Tree* newnode = malloc(sizeof(Tree));newnode->value = value;newnode->left = null;newnode->right = null;if(root == null){root = newnode;return root;}//p为工作指针 Tree* p = root;//p节点是插入节点，pre节点时插入节点的父节点 Tree* pre;while(p){pre = p;if(p->value > value){p = p->left;}else{p = p->right;}}if(pre->value > newnode->value){pre->left = newnode;}else{pre->right = newnode;}return root;}//前序遍历 void pre_print_rcs(Tree* root){if(root != null){printf("value: %d \t",root->value);pre_print_rcs(root->left);pre_print_rcs(root->right);}}Tree* Stack[20];int top = -1;//前序遍历 非递归 void pre_print_no_rcs(Tree* root){//top != -1 这个条件一定要加上，这是处理单枝情况 while(root != null || top != -1){if(root != null){printf("%d \t",root->value);if(top+1 != 20){Stack[++top] = root;root = root->left;}}else{root = Stack[top--]->right;}}}//中序遍历void in_print_rcs(Tree* root){if(root != null){in_print_rcs(root->left);printf("value: %d \t",root->value);in_print_rcs(root->right);}}//中序遍历 非递归 void in_print_no_rcs(Tree* root){//top != -1 这个条件一定要加上，这是处理单枝情况 while(root != null || top != -1){if(root != null){if(top+1 != 20){Stack[++top] = root;root = root->left;}}else{root = Stack[top--];printf("%d \t",root->value);root = root->right;}}}//后序遍历void post_print_rcs(Tree* root){if(root != null){post_print_rcs(root->left);post_print_rcs(root->right);printf("value: %d \t",root->value);}}Tree* Q[20];int front;int rear;//层序遍历 //输出队头元素，并将左右子树如队列 void level_print(Tree* root){front = rear = 0;if(root != null){Q[++rear] = root;while(rear != front){Tree* p = Q[++front];printf("%d \t",p->value);if(p->left != null){Q[++rear] = p->left;}if(p->right != null){Q[++rear] = p->right;}}}}Tree* create_no_rcs(int* list, int n){int i;for(i=0; i<n; i++){root = insert_no_rcs(root, list[i]);}return root;}Tree* create_rcs(int* list, int n){int i;for(i=0; i<n; i++){root = insert_rcs(root, list[i]);}return root;}int main(){int list[10] = {6,9,7,4,5,2,1,8,12,0};//root = create_no_rcs(list, 10); root = create_rcs(list, 10);//pre_print_rcs(root);//pre_print_no_rcs(root);in_print_rcs(root);in_print_no_rcs(root);//post_print_rcs(root);//level_print(root);return 0;}