使用C ++程序实现预遍历
在预遍历中，首先要遍历根，然后是左子树，然后是右子树，即顺序为NLR（节点从左到右），其中Node是当前节点。
在此，
N（过程节点，即当前根）
L（递归遍历左子树）
R（递归遍历右子树）
可以通过两种方式进行预遍历：
1.递归
算法：
preorder(root)
c. visit the root
a. Traverse the left subtree (preorder(root->left))
b. Traverse the right subtree (preorder(root->right))2.通过非递归方法
通过使用堆栈来实现此方法。
a. push the root into the stack
b. repeat while stack is not empty
1. pop an node from the stack and print it
2. push right child and then left child of the node into the stackC++代码实现预遍历
#include<iostream>
#include<stack>
using namespace std;
/*structure to store a BST*/
struct node
{
int info;
node *left,*right;
};
/*Method to create a newNode if a tree does not exist*/
node *newNode(int n)
{
node *ptr=new node;
ptr->info=n;
ptr->left=ptr->right=NULL;
return ptr;
}
/*Method to insert given node in the BST */
node *insert(node* node,int info)
{
if(node==NULL)
{
return newNode(info);
}
if(info < node->info)
{
node->left=insert(node->left,info);
}
else
{
node->right=insert(node->right,info);
}
return node;
}
/*Method to print preorder traversal of a BST*/
void preorder(node *root)
{
if(root == NULL)
{
return ;
}
stack<node*> stack;
stack.push(root);
while(!stack.empty())
{
node *curr=stack.top();
cout<<curr->info<<" ";
stack.pop();
if(curr->right)
{
stack.push(curr->right);
}
if(curr->left)
{
stack.push(curr->left);
}
}
}
int main(){
node* root=newNode(60);
insert(root,50);
insert(root,70);
insert(root,40);
insert(root,30);
insert(root,80);
insert(root,75);
insert(root,65);
insert(root,45);
insert(root,55);
insert(root,90);
insert(root,67);
cout<<"Preorder traversal :";
/*Call/invoke statement for preorder method*/
preorder(root);
cout<<endl;
return 0;
}输出结果
Preorder traversal :60 50 40 30 45 55 70 65 67 80 75 90
热门推荐
1 如何训练狗狗不叫
2 训练狗狗不叫
3 训练狗狗随行
4 怎么训练狗狗不叫
7 训练比熊狗狗教程
10 上海狗狗训练
11 怎么训练狗狗上厕所
12 训练狗狗趴下
13 狗狗服从训练
14 训练狗狗拒食
15 训练狗狗笑
16 训练狗狗大便
17 训练狗狗立
18 训练狗狗捡东西