首页 > 代码库 > C++ implementation of DF Traversal

C++ implementation of DF Traversal

如下图:

 

 

这里我们实现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 Preordervoid 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 Inordervoid 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 Postordervoid 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 TreeNode* Insert(Node *root,char data) {	if(root == NULL) {		root = new Node();		root->data = http://www.mamicode.com/data;>


运行结果为: