首页 > 其他 > 详细

二叉树的前序,中序遍历

时间:2017-08-06 21:28:13      阅读:154      评论:0      收藏:0      [点我收藏+]

前序递归于循环

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left,*right;
};

void create(TreeNode *&p)
{
    int k;
    cin>>k; //1 2 0 0 3 0 0;
    if(k!=0)
    {
        p=new TreeNode;
        p->val=k;
        create(p->left);
        create(p->right);
    }
    else
        p=NULL;
}

void preorder1(TreeNode *p)
{
    if(p)
    {
        cout<<p->val;
        preorder1(p->left);
        preorder1(p->right);
    }
}

void preorder2(TreeNode *root)
{
    stack<TreeNode*> s;
    TreeNode *p=root;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            cout<<p->val;
            p=p->left;
        }
        else
        {
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}

中序递归与循环

void inorder1(TreeNode *p)
{
    if(p)
    {
        inorder1(p->left);
        cout<<p->val;
        inorder1(p->right);
    }
}

void inorder2(TreeNode *p)
{
    stack<TreeNode*> s;
    while(p||!s.empty())
    {
        if(p)
        {
            s.push(p);
            p=p->left;
        }
        else
        {
            p=s.top();
            cout<<p->val;
            s.pop();
            p=p->right;
        }
    }
}

int main()
{
    TreeNode *root=new TreeNode;
    create(root);
    //preorder1(root);
    preorder2(root);
    //inorder1(root);
    inorder2(root);
    return 0;
}

 

二叉树的前序,中序遍历

原文:http://www.cnblogs.com/home123/p/7295912.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!