二叉排序树 先序遍历 中序遍历 后序遍历(非数组)

#include <stdio.h> #include <stdlib.h> typedef struct Tree { int data; struct Tree *left; struct Tree *right; }*tree; void InsertTree(tree p,int num) { tree T; T = p; int i; int sign; //sign 标记“现在要插入的” 结点是父结点的“左还是右结点” i=0;tree q,tmp; q =(tree ) malloc( sizeof(struct Tree) ); q->data = num; q->left =NULL; q->right =NULL; while(T) { if(num > T->data ) { tmp = T; T= T->right;sign =1;} //是父结点的右节点，则标记为 1 else { tmp = T; T= T->left; sign =0;} if(T ==NULL && sign == 1) { tmp ->right = q;} if(T ==NULL && sign == 0) { tmp ->left = q;} }} void PreOrder(tree p) { if(p) { printf("%d,",p->data); PreOrder(p->left); PreOrder(p->right); } }void InOrder(tree p) { if(p) { InOrder(p->left); printf("%d,",p->data); InOrder(p->right); } } void PostOrder(tree p) { if(p) {PostOrder(p->left); PostOrder(p->right); printf("%d,",p->data); } } //先序遍历，中序遍历，后序遍历思想基本一致： //(1)最左结点（ 且是已经访问 ）依次进栈， //(2)右结点（ 左结点为空或左结点已访问且是已经访问 ）依次进栈 //(3)叶子结点 (或未访问的（左或右） + 空子树) 出栈 //先序遍历，中序遍历二叉排序树中序遍历二叉排序树中序遍历，后序遍历输出原则： //(1) 先序遍历 进栈的均输出 //(2) 中序遍历 “无左子树” 输出 //(3) 后序遍历 void PreOrder1(tree p) { tree T = p; int i; tree q[100]; i =1; q[0]= T;int k ; k = 0; int rs[100];int ls[100]; //rs[],ls[]数组存放的是“当前节点”的左、右结点是否访问 . int j; for(j=0; j<100 ;j++) { rs[j] =0;ls[j] =0; } while( i != 0) {if(i==1 && k == 0){q[i] = T;printf("%d\n",q[i]->data);}while(T->left && ls[i] == 0) {T =T->left;ls[i] = 1;i++; q[i] = T;k++;ls[i] =0; rs[i] = 0;printf("%d,",q[i]->data); } if(( T->left ==NULL && T->right && rs[i] ==0 ) || (ls[i] ==1 && T->right&& rs[i] ==0 ) ){T = T->right;rs[i] =1;k++; i++;q[i] = T;ls[i] =0; rs[i] = 0;printf("%d,",q[i]->data); }if( (T->left ==NULL && rs[i] == 1 ) ||(T->left ==NULL && T->right == NULL)||(T->right ==NULL && ls[i] == 1 ) ||( rs[i] ==1&& ls[i] == 1 ) ){i--; k++;T = q[i];}} } void InOrder1(tree p) { tree T = p; int i; tree q[100]; i =1; q[0]= T; q[i] = T;int k ; k = 0; int rs[100];int ls[100]; int j; for(j=0; j<100 ;j++) { rs[j] =0;ls[j] =0; } while( i != 0) { while(T->left && ls[i] == 0) {T =T->left;ls[i] = 1;i++; q[i] = T;k++;ls[i] =0; rs[i] = 0; } if(( T->left ==NULL && T->right && rs[i] ==0 ) || (ls[i] ==0 ) ){ printf("%d,",q[i]->data); //“无”左结点就输出。

。。T = T->right;==1 && T->right&& rs[i]rs[i] =1;k++; i++;q[i] = T;ls[i] =0; rs[i] = 0;}if( (T->left ==NULL && rs[i] == 1 ) ||(T->left ==NULL && T->right == NULL)||(T->right ==NULL && ls[i] == 1 ) ||( rs[i] ==1&& ls[i] == 1 ) ){if((ls[i] == 0 && rs[i] == 0) || ( ls[i] == 1 && q[i]->right == NULL) ) //尚未访问的，或左节点已访问的输出printf("%d,",q[i]->data);i--; k++; T = q[i];}} } void PostOrder1(tree p) { tree T = p; int i; tree q[100]; i =1; q[0]= T; q[i] = T;int k ; k = 0; int rs[100];int ls[100]; int j; for(j=0; j<100 ;j++) { rs[j] =0;ls[j] =0; } while( i != 0) { while(T->left && ls[i] == 0) {T =T->left;ls[i] = 1;i++; q[i] = T;k++;ls[i] =0; rs[i] = 0; } if(( T->left ==NULL && T->right && rs[i] ==0 ) || (ls[i] ==1 && T->right&& rs[i] ==0 ) ){T = T->right;rs[i] =1;k++; i++;q[i] = T;ls[i] =0; rs[i] = 0;}if( (T->left ==NULL && rs[i] == 1 ) ||(T->left ==NULL && T->right == NULL)||(T->right ==NULL && ls[i] == 1 ) ||( rs[i] ==1&& ls[i] == 1 ) ){printf("%d,",q[i]->data); //为空的之后输出i--; k++; T = q[i];}} } void main() { tree p =NULL; int num; scanf("%d",&num);p =(tree) malloc( sizeof(struct Tree) ); p->data = num; p->left =NULL; p->right =NULL;} int i; for(i=1; i<=9;i++) {scanf("%d",&num); InsertTree(p,num);} PreOrder(p); printf("\n"); InOrder(p); printf("\n"); PostOrder(p); printf("\n"); PreOrder1(p); printf("\n"); InOrder1(p); printf("\n"); PostOrder1(p); printf("\n");

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-138876-1.html