j3jun1
2015-01-03 09:51
采纳率: 100%
浏览 2.0k
已采纳

不用递归遍历一颗二叉树

用递归遍历二叉树很简单,但是现在的问题是,能不能不用递归去遍历呢?用C#或者Java给出代码更好。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • blownewbee 2015-01-04 02:54
    已采纳

    简单来说有两个思路

    (1)使用后序遍历的方法。也就是说对于一个节点,先找它的左子节点,再找右子节点,最后找它本身。(深度优先)
    (2)使用线形表来存储二叉树。二叉树是可以直接用线形表表达的。(广度优先)

    点赞 打赏 评论
  • KangRoger 2015-01-03 10:55

    给出C++代码吧!把递归改为非递归,一般都是通过栈来实现。函数递归的原理也是利用了栈。
    首先来看前序遍历:前序遍历是先访问当前结点,再访问子结点。
    方法如下:
    1、访问当前结点p,并入栈。
    2、判断p左孩子是否为空,若为空则取出栈顶结点,将其右孩子设为当前结点p,转到1。若不为空,将p的左孩子设为当前结点p。
    3、直到p为空,并且栈的为空,则结束。
    代码:
    void preOrder2(BinTree root) //非递归前序遍历
    {
    stack<BinTree
    > s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
    while(p!=NULL)//一直向左找
    {
    cout<data<<"";
    s.push(p);
    p=p->lchild;
    }
    if(!s.empty())
    {
    p=s.top();
    s.pop();
    p=p->rchild;
    }
    }
    }

    再来看中序遍历,中序遍历是先访问左孩子,再访问当前结点。可以左孩子可能又是一个子树的根,这样的话,又要访问左孩子的左孩子,直到遇到左孩子为空。按照相同方法处理右子树。
    对于当前结点p
    1、如果其左孩子不为空,则将p入栈,将p左孩子设为p,在转到1.
    2、如果为空,取出栈顶元素来访问。之后将p设备栈顶元素的右孩子。
    3、直到p为空,且栈为空。
    void inOrder(BinTree root)

    {
    stack<BinTree
    > s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
    while(p!=NULL)//一直找左孩子
    {
    s.push(p);
    p=p->lchild;
    }
    if(!s.empty())
    {
    p=s.top();
    cout<data<<"";
    s.pop();
    p=p->rchild;
    }
    }

    }

    后续遍历,这个比较复杂。因为如果按照前面的方法。在结点第一次出栈时,只能确定它左孩子被访问了,但是还有右孩子。有一种方法是在结点中添加变量,来表面此结点有没有被访问过,这样就要修改结点结构。不应该这样做。
    要确保访问了左孩子、右孩子后,才访问当前结点。把当前结点入栈,再把其左右孩子入栈,这样其左右孩子肯定比它先出栈。但是确保左右孩子已经被访问过了才能访问当前结点。这样需要记录上一此访问的结点。
    void postOrder3(BinTree root) //非递归后序遍历
    {
    stack<BinTree
    > s;
    BinTree *cur; //当前结点
    BinTree *pre=NULL; //前一次访问的结点
    s.push(root);
    while(!s.empty())
    {
    cur=s.top();
    if((cur->lchild==NULL&&cur->rchild==NULL)||当前结点无孩子
    (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild))) //当前结点的孩子已经访问过了
    {
    cout<data<<"";

    s.pop();
    pre=cur;
    }
    else
    {
    if(cur->rchild!=NULL)
    s.push(cur->rchild);
    if(cur->lchild!=NULL)

    s.push(cur->lchild);
    }
    }

    }

    点赞 打赏 评论
  • KangRoger 2015-01-03 10:56

    排版有点乱,还没搞懂怎么加代码!!

    点赞 打赏 评论
  • dannyhao 2015-01-03 13:14

    object e = null; //声明一个变量存放地址
    SqStack S = new SqStack(); //声明一个栈,用来存放遍历过程中非末级节点

            TreeNode p = t;    //声明一个节点变量p 接收函数传来的参数 t
    
            while (p != null || !S.SqStackEmpty())  //从跟节点开始遍历,只要 p!=null (当前该节点还有子节点) 或者 栈 S 没用清空,循环执行下去。
            {
                if (p != null)    
                {
                    S.SqStackPush(p);   该节点有子节点,先把该节点保存入栈,(栈是后进先出,正好先遍历完子节点才遍历父节点的控制作用,栈的最底部存的是根节点,最后才弹出遍历,遍历完后,!S.SqStackEmpty() 就不成立了,while循环结束)   
                    p = p.left;    // 上一步p变量的节点压入栈保存后,转而获取左边子节点,继续循环,如果这是p=null,也就是刚压入栈的节点没有子节点,开始执行 else 里的语句
                }
                else
                {
                    S.SqStackPop(ref e);  //弹出刚压入栈的节点,存放到 e   ref e 是指存放该节点的地址
                    p = (TreeNode)e;    类型强制转化成 节点类型,因为 e 声明的是
    

    object类型。付值给p,
    Console.Write(p.data + " "); //输出p的数据。

                    p = p.right;     //转而读取该节点右边的树,开始新的循环。
                }
    
    点赞 打赏 评论
  • oyljerry 2015-01-03 13:47

    递归转成迭代方式,都是类似的,就是把节点放入一个队列,然后依次入队,出队

    点赞 打赏 评论

相关推荐 更多相似问题