樹的遍歷有3種：先根遍歷、中根遍歷、后根遍歷；
先根遍歷：如果該二叉樹為空樹，則空操作，否則先訪問根結點，再先根遍歷左子樹，最后先根遍歷右子樹，
1 //該二叉樹用二叉鏈表存盤，結點型別BiTreeNode 2 void pre_oder(BiTreeNode *root){ 3 if(root!=NULL){ 4 cout << root->data;//訪問結點（這里是輸出結點資訊） 5 pre_oder(root->leftchild);//先根遍歷左子樹 6 pre_oder(root->rightchild);//先根遍歷右子樹 7 } 8 }
中根遍歷：如果該二叉樹為空樹，則空操作，否則先中根遍歷左子樹，再訪問根結點，最后中根遍歷右子樹，
//該二叉樹用二叉鏈表存盤，結點型別BiTreeNode void in_oder(BiTreeNode *root){ if(root!=NULL){ in_oder(root->leftchild);//中根遍歷左子樹 cout << root->data;//訪問結點（這里是輸出結點資訊） in_oder(root->rightchild);//中根遍歷右子樹 } }
后根遍歷：如果該二叉樹為空樹，則空操作，否則先后根遍歷左子樹，再后根遍歷右子樹，最后訪問根結點，
1 //該二叉樹用二叉鏈表存盤，結點型別BiTreeNode 2 void back_oder(BiTreeNode *root){ 3 if(root!=NULL){ 4 back_oder(root->leftchild);//后根遍歷左子樹 5 back_oder(root->rightchild);//后根遍歷右子樹 6 cout << root->data;//訪問結點（這里是輸出結點資訊） 7 } 8 }
如果把cout << root->data陳述句抹去，這三種演算法是完全相同的，只是訪問結點的時機不同，
每次訪問某子樹時，都要先經過子樹的根，訪問完該子樹的左子樹后又會路過該子樹的根，訪問完右子樹后還會路過根，所以每個節點都會被路過三次，
如果在第一次路過時訪問，就是先根遍歷，如果是第二次，就是中根遍歷，最后一次則是后根遍歷，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90061.html
標籤：其他