上面二叉树的前序遍历序列为（以0代替NULL）：[1,2,4,8,0,0,9,0,0,5,10,0,0,11,0,0,3,6,12,0,0,0,7,0,0]
根据上面的前序遍历，创建二叉树，并对二叉树进行前序遍历、中序遍历、后续遍历
#include <iostream> #include <vector> using namespace std; int index_num=0; vector<int> num={1,2,4,8,0,0,9,0,0,5,10,0,0,11,0,0,3,6,12,0,0,0,7,0,0}; struct BiTree { int val; BiTree *LeftChildNode; BiTree *RightChildNode; BiTree() : LeftChildNode(NULL), RightChildNode(NULL) {} }; BiTree *CreateBitree_pre(int); void traversing_pre(BiTree *t); void traversing_mid(BiTree *t); void traversing_las(BiTree *t); int main() { BiTree *tree; tree=CreateBitree_pre(0);//前序创建 traversing_pre(tree);//前序遍历 cout<<endl; traversing_mid(tree);//中序遍历 cout<<endl; traversing_las(tree);//后序遍历 return 0; } //前序遍历创建二叉树 BiTree *CreateBitree_pre(int loc) { if (num[loc] != 0 && loc < (int)num.size()) { BiTree *node = new BiTree(); node->val=num[loc]; node->LeftChildNode = CreateBitree_pre(++index_num); node->RightChildNode = CreateBitree_pre(++index_num); return node; } return NULL; } //前序遍历 void traversing_pre(BiTree *t) { if(t!=NULL) { cout<<t->val<<" "; traversing_pre(t->LeftChildNode); traversing_pre(t->RightChildNode); } } //中序遍历 void traversing_mid(BiTree *t) { if(t!=NULL) { traversing_mid(t->LeftChildNode); cout<<t->val<<" "; traversing_mid(t->RightChildNode); } } //后序遍历 void traversing_las(BiTree *t) { if(t!=NULL) { traversing_las(t->LeftChildNode); traversing_las(t->RightChildNode); cout<<t->val<<" "; } }输出结果：
1 2 4 8 9 5 10 11 3 6 12 7 8 4 9 2 10 5 11 1 12 6 3 7 8 9 4 10 11 5 2 12 6 7 3 1
