二叉树程序//不懂之处,该怎么处理

二叉树程序//不懂之处

C/C++ code

#include <iostream>#include <iomanip>using namespace std;struct Node{    int data;    Node* left;    Node* right;    Node(const int& d):data(d),left(),right(){}};class Bst{private:    void insert(Node*p,Node* &t)    {        if(p==NULL) return;        if(t==NULL) t=p;        else if(p->data>t->data) insert(p,t->right);        else insert(p,t->left);    }    void travel(Node* &t)    {        if(t==NULL) return;        travel(t->left);        cout << t->data <<' ';        travel(t->right);    }    void clear(Node* &t)    {        if(t==NULL) return;        clear(t->left);        clear(t->right);        delete t;    }    Node* & find(const int&d,Node* &t)    {        if(t==NULL) return t;        if(t->data==d) return t;        if(d>t->data) return find(d,t->right);        return find(d,t->left);    }    int high(Node* & t)//这个函数是什么作用????????    {        if(t==NULL) return 0;        int lh = high(t->left);        int rh = high(t->right);        return (lh>rh?lh:rh)+1;    }    void print(Node* &t,int s,char c)    {        if(t==NULL) return;        print(t->right,s+3,'/');        cout << setw(s) << c << t->data <<endl;        print(t->left,s+3,'\\');    }public:    Bst():root(){}    ~Bst() {clear();}    void insert(const int& d)    {        Node* pn = new Node(d);        insert(pn,root);    }    void travel()    {        travel(root);        cout<<endl;    }    void clear()    {        clear(root);        root=NULL;    }    Node*& find(const int& d)    {        return find(d,root);    }    bool remove(const int& d)    {        Node* & t = find(d);        if(t==NULL) return false;        insert(t->left,t->right);//这一步是什么作用?????        Node* p =t;        t = t->right;        delete p;        return true;    }    void removeAll(const int& d)    {        while(remove(d));    }    void modify(const int& old,const int& newVal)    {        while(remove(old)) insert(newVal);    }    int high()    {        return high(root);    }    void print()    {        print(root,0,'*');    }private:    Node* root;};int main(){    Bst t;    t.insert(5);    t.insert(3);    t.insert(2);    t.insert(4);    t.insert(8);    t.insert(6);    t.insert(9);    cout << t.high() <<endl;    t.print();}

[解决办法]

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

struct Node{
int data;
Node* left;
Node* right;
Node(const int& d):data(d),left(),right(){}//构造函数使用初始化列表
};///////////////////////////////////////////////////定义节点的结构体

class Bst{
private:
void insert(Node*p,Node* &t)
{
if(p==NULL) return;
if(t==NULL) t=p;
else if(p->data>t->data) insert(p,t->right);
else insert(p,t->left);
}
void travel(Node* &t)
{
if(t==NULL) return;
travel(t->left);
cout << t->data <<' ';
travel(t->right);
}
void clear(Node* &t)
{
if(t==NULL) return;
clear(t->left);
clear(t->right);
delete t;
}
Node* & find(const int&d,Node* &t)
{
if(t==NULL) return t;
if(t->data==d) return t;
if(d>t->data) return find(d,t->right);
return find(d,t->left);
}
int high(Node* & t)//这个函数是什么作用????????///////////////明显看出求二叉树的高度
{
if(t==NULL) return 0;

int lh = high(t->left);
int rh = high(t->right);
return (lh>rh?lh:rh)+1;
}
void print(Node* &t,int s,char c)
{
if(t==NULL) return;
print(t->right,s+3,'/');
cout << setw(s) << c << t->data <<endl;
print(t->left,s+3,'\\');
}
public:
Bst():root(){}
~Bst() {clear();}
void insert(const int& d)
{
Node* pn = new Node(d);
insert(pn,root);
}
void travel()
{
travel(root);
cout<<endl;
}
void clear()
{
clear(root);
root=NULL;
}
Node*& find(const int& d)
{
return find(d,root);
}
bool remove(const int& d)
{
Node* & t = find(d);///////////////////////////////调用找节点函数
if(t==NULL) 
return false;
insert(t->left,t->right);//这一步是什么作用??？？//调用了插入函数，看似要构造一种树，不是简单的删除操作
Node* p =t;
t = t->right;
delete p;
return true;
}
void removeAll(const int& d)
{
while(remove(d));
}
void modify(const int& old,const int& newVal)
{
while(remove(old)) insert(newVal);
}
int high()
{
return high(root);
}
void print()
{
print(root,0,'*');
}
private:
Node* root;//定义根节点
};

int main()
{
Bst t;
t.insert(5);
t.insert(3);
t.insert(2);
t.insert(4);
t.insert(8);
t.insert(6);
t.insert(9);
cout << t.high() <<endl;
t.print();
}

查看更多 下一篇