用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 毕业祝福语给同学 简短