用C++实现顺序遍历
在顺序遍历中，左子树首先是根，然后是右子树，即按照LNR（左节点右）的顺序，其中Node是当前节点。
在此，
L（递归遍历左子树）
N（过程节点，即当前根）
R（递归遍历右子树）
有序遍历可以通过两种方式完成：
1.递归
算法：
inorder(root)
a. Traverse the left subtree (inorder(root->left))
b. visit the root
c. Traverse the right subtree (inorder(root->right))2.通过非递归方法
通过使用堆栈来实现此方法。
a. create an empty stack
b. initialize current node as root node.
c. push current into the stack while current->left != NULL
update current as current=current->leftd. repeat while current is NULL and stack is not empty
1. pop the element from the stack and update
current equal to the popped element
2. print info of current
3.update current=current->rightC++代码实现有序遍历
#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 inorder traversal of a BST*/
void inorder(node *root)
{
stack<node*> stack;
node *curr=root;
while(!stack.empty() || curr!=NULL)
{
/*If current node is not NULL push the node in stack*/
if(curr!=NULL)
{
stack.push(curr);
curr=curr->left;
}
/*If current node is empty or NULL pop it from the stack */
else
{
curr=stack.top();
stack.pop();
cout<<curr->info<<" ";
curr=curr->right;
}
}
}
//主程序
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<<"Inorder traversal :";
/*Call/invoke statement for inorder method*/
inorder(root);
cout<<endl;
return 0;
}输出结果
Inorder traversal :30 40 45 50 55 60 65 67 70 75 80 90
热门推荐
10 祝女儿简短祝福语大全
11 大学新年祝福语简短创意
12 元旦适合的祝福语简短
13 朋友出远门祝福语简短
14 初六简短的祝福语
15 祝男孩生日祝福语简短
16 同事调离的祝福语简短
17 拜年红包的祝福语简短
18 妈妈生日祝福语简短励志