用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->right

C ++代码实现有序遍历

#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