【先序遍历】DLR:先根再左再右:A->B->C-D->E->F->G->H
[中序遍历] LDR:先左再根再右:B->D->C->E->A->F->H->G
【后序遍历】LRD:先左再右再中:D->E->C->B->H->G->F->A
图(1)
【先序遍历】DLR:先根再左再右:A->B->D->H->I->E->J->C->F->G
[中序遍历] LDR:先左再根再右:H->D->I->B->J->E->A->F->C->G
【后序遍历】LRD:先左再右再中:H->I->D->J->E->B->F->G->C->A
图(2)
针对图1的三种c++实现:
1 #include<iostream> 2 using namespace std; 3 4 //二叉树节点 5 struct BinaryNode 6 { 7 char ch; 8 BinaryNode* lchild; 9 BinaryNode* rchild; 10 }; 11 void Recursion(BinaryNode* root); 12 //初始化二叉树 13 void CreateBinaryTree() { 14 BinaryNode node1 = { 'A',NULL,NULL }; 15 BinaryNode node2 = { 'B',NULL,NULL }; 16 BinaryNode node3 = { 'C',NULL,NULL }; 17 BinaryNode node4 = { 'D',NULL,NULL }; 18 BinaryNode node5 = { 'E',NULL,NULL }; 19 BinaryNode node6 = { 'F',NULL,NULL }; 20 BinaryNode node7 = { 'G',NULL,NULL }; 21 BinaryNode node8 = { 'H',NULL,NULL }; 22 //建立节点关系 23 node1.lchild = &node2; 24 node1.rchild = &node6; 25 node2.rchild = &node3; 26 node3.lchild = &node4; 27 node3.rchild = &node5; 28 node6.rchild = &node7; 29 node7.lchild = &node8; 30 Recursion(&node1); 31 cout << endl; 32 } 33 //二叉树遍历 34 void Recursion(BinaryNode* root) { 35 if (!root) return; 36 cout << root->ch <<" "; 37 Recursion(root->lchild); //此结果为先序遍历,将第36行向下移动1行和2行分别为中序遍历和后续遍历 38 Recursion(root->rchild); 39 } 40 int main() { 41 CreateBinaryTree(); 42 }
先序遍历:
中序遍历:
后续遍历:
注意:在初始化二叉树函数中不应该使返回类型为BinaryNode* 型 因为返回node1地址时为局部变量,在出这个函数后其地址中的内容会被释放。