Question

生成二叉排序树(c++写代码, 数据结构)

题 目 三：生成二叉排序树
题目描述：已知二叉排序树的先序遍历序列存储在一维数组中，编写算法由此数组得到该二叉排序树的二叉链表结构，打印对此而叉树的中序和后序遍历序列。
基本要求：
(1) 设计一个二叉树类。打印二叉树的中序和后遍历序列是该二叉树类的成员函数。
(2) 生成二叉树的算法以普通函数的形式实现，该函数的返回值是一棵二叉树。
提高要求：
(1) 输入的字符可以是存放在某个文本文件中的n个字符
(2) 有简单的基于字符的DOS界面，方便用户进行操作。

Answer 1

#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>

using namespace std;
#define LEN 100
typedef char ElemType;

class BSTree;
BSTree *CreateBSTree(const ElemType *a);

// 二叉排序树节点
class BSTNode
{
friend class BSTree;
friend BSTree *CreateBSTree(const ElemType *a);
public:
BSTNode() : lchild(NULL), rchild(NULL) {}
BSTNode(ElemType d, BSTNode *l = NULL,BSTNode *r = NULL)
: data(d), lchild(l), rchild(r) {}

private:
BSTNode *lchild, *rchild;
ElemType data;
};

// 二叉排序树
class BSTree
{
friend BSTree *CreateBSTree(const ElemType *a);
public:
BSTree() : root(NULL) {}
~BSTree() { CleanUp(); }

void CleanUp(BSTNode *r);
void InOrder(BSTNode *r) const; // 中序遍历
void PostOrder(BSTNode *r) const; // 后序遍历
void CleanUp(); // 释放资源
void InOrder() const;
void PostOrder() const;

private:
BSTNode *root;
};

void BSTree::CleanUp(BSTNode *r)
{
if (r)
{
CleanUp(r->lchild);
CleanUp(r->rchild);
delete r;
}
}

void BSTree::CleanUp()
{
CleanUp(root);
}

void BSTree::InOrder(BSTNode *r) const
{
if (r)
{
InOrder(r->lchild);
cout << r->data << ' ';
InOrder(r->rchild);
}
}

void BSTree::InOrder() const
{
InOrder(root);
}

void BSTree::PostOrder(BSTNode *r) const
{
if (r)
{
PostOrder(r->lchild);
PostOrder(r->rchild);
cout << r->data << ' ';
}
}

void BSTree::PostOrder() const
{
PostOrder(root);
}

// 创建二叉排序树
BSTree *CreateBSTree(const ElemType *a)
{
BSTree *tree= new BSTree;
BSTNode *cursor;

tree->root= new BSTNode(a[0]);
const ElemType *p = a + 1;

while (*p != '\0')
{
cursor = tree->root;

while (1)
{
if (*p < cursor->data)
{
if (!cursor->lchild)
{
cursor->lchild = new BSTNode(*p);
break;
}

cursor = cursor->lchild;
}
else
{
if (!cursor->rchild)
{
cursor->rchild = new BSTNode(*p);
break;
}

cursor = cursor->rchild;
}
}

++p;
}

return tree;
}

int main()
{
char choice, data[LEN];
BSTree *tree = NULL;

cout << "请选择创建二叉排序树的方式:" << endl;
cout << "1) 文件获取数据\t2) 手动输入数据" << endl;

memset(data, '\0', LEN);
cin >> choice;
while (getchar() != '\n');

switch (choice)
{
case '1':
{
// 假定数据文件名为data.txt
ifstream infile("data.txt");

if (!infile)
{
cerr << "打开文件出错！" << endl;
exit(-1);
}

// 从文件读取一行数据，长度为LEN减1
infile.getline(data, LEN);
// 关闭文件
infile.close();
break;
}
case '2':
{
cout << endl;
cout << "请输入一个字符串: ";
// 从控制台读取一行数据，长度为LEN减1
cin.getline(data, LEN);
break;
}
}

tree = CreateBSTree(data);
cout << endl;
cout << "中序序列：" << endl;
tree->InOrder();
cout << endl;
cout << "后序序列：" << endl;
tree->PostOrder();
cout << endl;
delete tree;
system("PAUSE");
return 0;
}

Answer 2

#include
<memory.h>
#include
<cstdlib>
#include
<cstdio>
#include
<iostream>
#include
<fstream>
using
namespace
std;
#define
LEN
100
typedef
char
ElemType;
class
BSTree;
BSTree
*CreateBSTree(const
ElemType
*a);
//
二叉排序树节点
class
BSTNode
{
friend
class
BSTree;
friend
BSTree
*CreateBSTree(const
ElemType
*a);
public:
BSTNode()
:
lchild(NULL),
rchild(NULL)
{}
BSTNode(ElemType
d,
BSTNode
*l
=
NULL,BSTNode
*r
=
NULL)
:
data(d),
lchild(l),
rchild(r)
{}
private:
BSTNode
*lchild,
*rchild;
ElemType
data;
};
//
二叉排序树
class
BSTree
{
friend
BSTree
*CreateBSTree(const
ElemType
*a);
public:
BSTree()
:
root(NULL)
{}
~BSTree()
{
CleanUp();
}
void
CleanUp(BSTNode
*r);
void
InOrder(BSTNode
*r)
const;
//
中序遍历
void
PostOrder(BSTNode
*r)
const;
//
后序遍历
void
CleanUp();
//
释放资源
void
InOrder()
const;
void
PostOrder()
const;
private:
BSTNode
*root;
};
void
BSTree::CleanUp(BSTNode
*r)
{
if
(r)
{
CleanUp(r->lchild);
CleanUp(r->rchild);
delete
r;
}
}
void
BSTree::CleanUp()
{
CleanUp(root);
}
void
BSTree::InOrder(BSTNode
*r)
const
{
if
(r)
{
InOrder(r->lchild);
cout
<<
r->data
<<
'
';
InOrder(r->rchild);
}
}
void
BSTree::InOrder()
const
{
InOrder(root);
}
void
BSTree::PostOrder(BSTNode
*r)
const
{
if
(r)
{
PostOrder(r->lchild);
PostOrder(r->rchild);
cout
<<
r->data
<<
'
';
}
}
void
BSTree::PostOrder()
const
{
PostOrder(root);
}
//
创建二叉排序树
BSTree
*CreateBSTree(const
ElemType
*a)
{
BSTree
*tree=
new
BSTree;
BSTNode
*cursor;
tree->root=
new
BSTNode(a[0]);
const
ElemType
*p
=
a
+
1;
while
(*p
!=
'\0')
{
cursor
=
tree->root;
while
(1)
{
if
(*p
<
cursor->data)
{
if
(!cursor->lchild)
{
cursor->lchild
=
new
BSTNode(*p);
break;
}
cursor
=
cursor->lchild;
}
else
{
if
(!cursor->rchild)
{
cursor->rchild
=
new
BSTNode(*p);
break;
}
cursor
=
cursor->rchild;
}
}
++p;
}
return
tree;
}
int
main()
{
char
choice,
data[LEN];
BSTree
*tree
=
NULL;
cout
<<
"请选择创建二叉排序树的方式:"
<<
endl;
cout
<<
"1)
文件获取数据\t2)
手动输入数据"
<<
endl;
memset(data,
'\0',
LEN);
cin
>>
choice;
while
(getchar()
!=
'\n');
switch
(choice)
{
case
'1':
{
//
假定数据文件名为data.txt
ifstream
infile("data.txt");
if
(!infile)
{
cerr
<<
"打开文件出错！"
<<
endl;
exit(-1);
}
//
从文件读取一行数据，长度为LEN减1
infile.getline(data,
LEN);
//
关闭文件
infile.close();
break;
}
case
'2':
{
cout
<<
endl;
cout
<<
"请输入一个字符串:
";
//
从控制台读取一行数据，长度为LEN减1
cin.getline(data,
LEN);
break;
}
}
tree
=
CreateBSTree(data);
cout
<<
endl;
cout
<<
"中序序列："
<<
endl;
tree->InOrder();
cout
<<
endl;
cout
<<
"后序序列："
<<
endl;
tree->PostOrder();
cout
<<
endl;
delete
tree;
system("PAUSE");
return
0;
}

Answer 3

你才自找的，硬做做不出来你以为大学生日子好过啊。