c++数据结构题1:建立一棵二叉链表树,分别输出此先根,中根和后根遍历序列
发布网友
发布时间：2022-06-04 04:51
共4个回答
热心网友
时间：2023-10-26 18:40
using namespace std;
class bst
{
struct Node
{
int data;
Node *L;
Node *R;
Node(const int &d):data(d),L(NULL),R(NULL)
{
}
};
Node *root;
int len;
void clear(Node *&tree)
{
if (tree == NULL)
{
return ;
}
clear(tree->L);
clear(tree->R);
delete tree;
tree = NULL;
--len;
}
void travel(Node *tree)
{
if (tree == NULL)
{
return ;
}
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
int height(Node *tree)
{
if (tree == NULL)
{
return 0;
}
int lh = height(tree->L);
int rh = height(tree->R);
return lh > rh ? lh+1 : rh+1;
}
void insert(Node *&tree, Node *p)
{
if (tree == NULL)
{
tree = p;
}
else if (p->data < tree->data)
{
insert(tree->L, p);
}
else
{
insert(tree->R, p);
}
}
Node* &find(Node* &tree, const int &d)
{
if (tree == NULL)
{
return tree;
}
if (tree->data == d)
{
return tree;
}
if (d < tree->data)
{
find(tree->L, d);
}
return find(tree->R, d);
}
void combine(Node *lc, Node *&rc)
{
if (lc == NULL)
{
return ;
}
if (rc == NULL)
{
rc = lc;
}
else
{
combine(lc, rc->L);
}
}
public:
bst():len(0),root(NULL)
{
}
~bst()
{
clear(root);
}
void clear()
{
clear(root);
}
void travel()
{
travel(root);
cout << endl;
}
bool empty()
{
return root==NULL;
}
int height()
{
return height(root);
}
void insert(const int &d)
{
insert(root, new Node(d));
++len;
}
bool find(const int &d)
{
return find(root, d) != NULL;
}
bool erase(const int &d)
{
Node *&pt = find(root, d);
if (pt == NULL)
{
return false;
}
combine(pt->L, pt->R);
Node *p = pt;
pt = pt->R;
delete p;
--len;
return true;
}
};
int main(int argc, char *argv[])
{
bst t;
t.insert(9);
t.insert(6);
t.insert(3);
t.insert(5);
t.insert(8);
t.insert(15);
t.insert(24);
t.travel();
cout << t.find(16) << endl;
return 0;
}
热心网友
时间：2023-10-26 18:41
热心网友
时间：2023-10-26 18:41
热心网友
时间：2023-10-26 18:42
