首页 > 代码库 > 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;>
运行结果为:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。