對(duì)于三種遍歷方式來說，均為先左后右！區(qū)別在于根結(jié)點(diǎn)的位置順序

先序遍歷：根——左——右

中序遍歷：左——根——右

后序遍歷：左——右——根

（所謂先中后的順序，是指根結(jié)點(diǎn)D先于子樹還是后于子樹出現(xiàn)）

?如上圖：

先序遍歷的結(jié)果為：A B C D E F G H

中序遍歷的結(jié)果為：B D C E A F H G

后序遍歷的結(jié)果為：D E C B H G F A

---

定義樹的結(jié)點(diǎn)類型

typedef struct BinaryNode{char ch;struct BinaryNode* lchild;struct BinaryNode* rchild;
}BinaryNode;

根據(jù)圖例創(chuàng)建二叉樹

void CreateBinaryTree()
{//創(chuàng)建結(jié)點(diǎn) BinaryNode node1={'A',NULL,NULL};BinaryNode node2={'B',NULL,NULL};BinaryNode node3={'C',NULL,NULL};BinaryNode node4={'D',NULL,NULL};BinaryNode node5={'E',NULL,NULL};BinaryNode node6={'F',NULL,NULL};BinaryNode node7={'G',NULL,NULL};BinaryNode node8={'H',NULL,NULL};//創(chuàng)建結(jié)點(diǎn)關(guān)系node1.lchild=&node2;node1.rchild=&node6;node2.rchild=&node3;node3.lchild=&node4;node3.rchild=&node5;node6.rchild=&node7;node7.lchild=&node8;
}

遞歸實(shí)現(xiàn)先序遍歷

void RecursionFirst(BinaryNode* root)
{ if(root==NULL)//遍歷到空結(jié)點(diǎn)return;cout<<(root->ch)<<" "; //輸出根結(jié)點(diǎn)RecursionFirst(root->lchild);//要點(diǎn)：雖然一左一右看似連在一起，其實(shí)是將首個(gè)根結(jié)點(diǎn)的左子樹全部遍歷完畢，才會(huì)去遍歷右子樹 RecursionFirst(root->rchild);//先序遍歷的順序?yàn)?#xff1a;根-左-右 	
}

遞歸實(shí)現(xiàn)中序遍歷

void RecursionMiddle(BinaryNode* root)
{if(root==NULL)return;RecursionMiddle(root->lchild);cout<<(root->ch)<<" "; RecursionMiddle(root->rchild);//中序遍歷的順序?yàn)?#xff1a;左-根-右 	
}

遞歸實(shí)現(xiàn)后序遍歷

void RecursionLast(BinaryNode* root)
{if(root==NULL)return;RecursionLast(root->lchild);RecursionLast(root->rchild);cout<<(root->ch)<<" "; //后序遍歷的順序?yàn)?#xff1a;左-右-根 
}

在CreateBinaryTree方法中添加函數(shù)調(diào)用

	//遍歷結(jié)點(diǎn)cout<<"先序遍歷："<<endl; RecursionFirst(&node1); cout<<endl; cout<<"中序遍歷："<<endl; RecursionMiddle(&node1);cout<<endl; cout<<"后序遍歷："<<endl; RecursionLast(&node1);cout<<endl; 

頭文件及主函數(shù)

int main(int argc, char** argv) {CreateBinaryTree();//主函數(shù)只負(fù)責(zé)調(diào)用即可 return 0;
}

運(yùn)行結(jié)果如下：與結(jié)果相一致

?