递归建立二叉树问题 - 数据结构与算法

楼主

已结贴√ 问题点数：10 回复次数：6

递归建立二叉树问题

我的代码如下：

程序代码：

template <class Elem>
void CreateBinTree(BinNode<Elem> *subroot)
{
    BinNode<Elem>* T= subroot;
    Elem nodeval;
    cin>>nodeval;
    if(nodeval=='#')
    {
        subroot=NULL;
        return ;
    }
    else
    {
        subroot=new BinNodePtr<Elem>();
        if(subroot!=NULL)
        {
        subroot->setVal(nodeval);
        CreateBinTree<Elem>(subroot->left());   

        CreateBinTree<Elem>(subroot->right()); 

        }
    }
}

运行的结果是退不出递归，即使输“#”进去了，还是在不断递归，请问有什么问题？

搜索更多相关主题的帖子: 二叉树　

第 2 楼

得分:0

以下是我改进后的，但当我输入'#'后，会异常停止：

程序代码：

template <class Elem>
void  CreateBinTree(BinNode<Elem> *subroot)
{
    BinNode<Elem>* T= subroot;
    Elem nodeval;
    cin>>nodeval;
    if(nodeval!='#')
    {

        subroot=new BinNodePtr<Elem>();
        if(subroot!=NULL)
        {   

        subroot->setVal(nodeval);
        CreateBinTree<Elem>(subroot->left());   

        CreateBinTree<Elem>(subroot->right()); 

        }
        else
            exit(0);
    }
    else
        subroot=NULL;

}

求高手解答，谢谢了！

第 3 楼

得分:10

空间没有释放

成功贵在坚持

第 4 楼

得分:0

回复 3楼 mayuebo

请问那里是需要释放空间的？我是要建立一颗二叉树，不用释放空间吧？

第 5 楼

得分:0

貌似看上去好像没有错。。
我以前也写过类似的代码我这里还有呢。原因找出来了但是我不记得了。

第 6 楼

得分:0

回复楼主回到原點

BinNode<Elem>把它的详细信息贴出来观摩下

第 7 楼

得分:0

回复 6楼寒风中的细雨

程序代码：

#ifndef _BINNODE_H
#define _BINNODE_H
//Binary tree node abstract class
template <class Elem> class BinNode{
public:
    //return the node's element
    virtual Elem& val() = 0;
    //set the node's element
    virtual void setVal(const Elem &) = 0;
    //return the node's left child
    virtual BinNode* left() const = 0;
    //set the node's left child
    virtual void setLeft(BinNode*) = 0;
    //return the node's right child
    virtual BinNode* right() const = 0;
    //set the node's right child
    virtual void setRight(BinNode*) = 0;
    //return true if the node is a leaf
    virtual bool isLeaf() = 0;
};
#endif
#ifndef _BINNODEPTR_H
#define _BINNODEPTR_H
#include "BinNode.h"
// Binary tree node class
class KEComp{
public:

 static bool lt(int x,int y){return x<y;}

 static bool eq(int x,int y){return x==y;}

 static bool gt(int x,int y){return x>y;}
};
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
    Elem it;         // The node's value
    BinNodePtr* lc;  // Pointer to left child
    BinNodePtr* rc;  // Pointer to right child

public:
    BinNodePtr() { lc = rc = NULL; }
    BinNodePtr(Elem e, BinNodePtr* l =NULL,
        BinNodePtr* r =NULL)
    { it = e; lc = l; rc = r; }
    Elem& val() { return it; }
    void setVal(const Elem& e) { it = e; }
    inline BinNode<Elem>* left() const
    { return lc; }
    void setLeft(BinNode<Elem>* b)
    { lc = (BinNodePtr*)b; }
    inline BinNode<Elem>* right() const
    { return rc; }
    void setRight(BinNode<Elem>* b)
    { rc = (BinNodePtr*)b; }
    bool isLeaf()
    { return (lc == NULL) && (rc == NULL); }
   

};

代码如上，请问那里出了问题？