二叉树的三种递归遍历和建树

二叉树的三种递归遍历方式和建树方法（c语言）

中序遍历

void InorderTraversal(BinTree BT ){ if(!BT) return ; InorderTraversal(BT -> Left); printf("%c ",BT->data); InorderTraversal(BT -> Right); }

前序遍历

void PreorderTraversal( BinTree BT ){ if(!BT) return ; printf("%c ",BT->data); PreorderTraversal(BT -> Left); PreorderTraversal(BT -> Right); }

后序遍历

void PostorderTraversal( BinTree BT ){ if(!BT) return ; PostorderTraversal(BT -> Left); PostorderTraversal(BT -> Right); printf("%c ",BT->data); }

层序遍历 这里本来需要用到队列来进行，我只用了数组进行模拟。

void LevelorderTraversal( BinTree BT ){ struct TNode *Tode[200]; Tode[1] = BT; int now = 1,cnt = 1; while(now <= cnt){ printf("%c ",Tode[now]->data); if(Tode[now]->Left)Tode[++cnt] = Tode[now]->Left; if(Tode[now]->Right)Tode[++cnt] = Tode[now]->Right; now ++; } }

建立二叉树

BinTree CreatBinTree(){ char str[200]; scanf("%s",str); BinTree BT = (Position)malloc(sizeof(struct TNode)); BT->data = str[0]; child(BT,str,1); child(BT,str,0); return BT; } void child(BinTree root,char str[],int x){ // 我能想到的比较笨的办法吧 pos ++; if(str[pos] == '\0'){ return ; } if(str[pos] == '#'){ if(x == 1) root ->Left = NULL; else root -> Right = NULL; } else { BinTree BT = (Position)malloc(sizeof(struct TNode)); BT -> data = str[pos]; if(x == 1) root ->Left = BT; else root -> Right = BT; child(BT ,str,1); child(BT ,str,0); } }

交换左右儿子

void Exchang(BinTree root){ if(!root) return ; Position lc,rc; lc = root -> Left; rc = root -> Right; root -> Left = rc; root -> Right = lc; Exchang(root -> Left); Exchang(root -> Right); }