如下图:
这里我们实现DFS中的三种遍历方法。
相关的如下:
相关算法的介绍不再赘述。
首先对于preorder traversal 的步骤为:
其他两种算法略。
具体递归调用分析, 注意学会画stack frame的图分析。 这里不再赘述。
代码如下:
/* Binary Tree Traversal - Preorder, Inorder, Postorder */ #include<iostream> using namespace std; struct Node { char data; Node *left; Node *right; }; //Function to visit nodes in Preorder void Preorder(Node *root) { // base condition for recursion // if tree/sub-tree is empty, return and exit if(root == NULL) return; cout << root->data; // Print data Preorder(root->left); // Visit left subtree Preorder(root->right); // Visit right subtree } //Function to visit nodes in Inorder void Inorder(Node *root) { if(root == NULL) return; // base case Inorder(root->left); //Visit left subtree cout << root->data; //Print data Inorder(root->right); // Visit right subtree } //Function to visit nodes in Postorder void Postorder(Node *root) { if(root == NULL) return; // base case Postorder(root->left); // Visit left subtree Postorder(root->right); // Visit right subtree cout << root->data; // Print data } // Function to Insert Node in a Binary Search Tree Node* Insert(Node *root,char data) { if(root == NULL) { root = new Node(); root->data = data; root->left = root->right = NULL; } else if(data <= root->data) root->left = Insert(root->left,data); else root->right = Insert(root->right,data); return root; } int main() { /*Code To Test the logic Creating an example tree M / B Q / \ A C Z */ Node* root = NULL; root = Insert(root,'M'); root = Insert(root,'B'); root = Insert(root,'Q'); root = Insert(root,'Z'); root = Insert(root,'A'); root = Insert(root,'C'); //Print Nodes in Preorder. cout<<"Preorder: "; Preorder(root); cout<<"\n"; //Print Nodes in Inorder cout<<"Inorder: "; Inorder(root); cout<<"\n"; //Print Nodes in Postorder cout<<"Postorder: "; Postorder(root); cout<<"\n"; }
运行结果为: