#include
#include
#include
using namespace std;
template
struct binode
{
elemtype data;
binode* lchild, * rchild;
};
template
class bitree
{public:
bitree() {
root = creat(root);
}
void preorder() {
preorder(root);
};
void inorder()
{
inorder(root);
};
void postorder()
{
postorder(root);
};
void Depth()
{
cout<* root;
binode* creat(binode* bt);
void preorder(binode* bt);
void inorder(binode* bt);
void postorder(binode* bt);
int depth(binode* bt);
int width(binode* root);
};
template
binode* bitree::creat(binode* bt)
{
char ch;
cout << "请创建一颗二叉树的结点数据：" << endl;
cin >> ch;
if (ch =='#')
{
return NULL;
}
else
{
bt = new binode < elemtype>;
bt ->data= ch;
bt->lchild = creat(bt->lchild);
bt->rchild = creat(bt->rchild);
}
return bt;
}
template
void bitree::preorder(binode* bt)
{
if (bt == NULL)
{
return;
}
else
{
cout << bt->data << " ";
preorder(bt->lchild);
preorder(bt->rchild);
}
}
template
void bitree::inorder(binode* bt)
{
if (bt == NULL)
{
return;
}
else
{
preorder(bt->lchild);
cout << bt->data << " ";
preorder(bt->rchild);
}
}
template
void bitree::postorder(binode* bt)
{
if (bt == NULL)
{
return;
}
else
{
preorder(bt->lchild);
preorder(bt->rchild);
cout << bt->data << " ";
}
}
template
int bitree::depth(binode* bt)
{
if (bt == NULL)
{
return 0;
}
else
{
int dep1 = depth(bt->lchild);
int dep2 = depth(bt->rchild);
return max(dep1, dep2)+1;
}
}
template
int bitree::width(binode* root)
{
if (root == NULL)
{
return 0;
}
int wid = 0;
int maxwid = 0;
queue* > q;
q.push(root);
while (!q.empty())
{
wid = q.size();
maxwid = max(maxwid, wid);
for ( int i = 0; i < wid; i++)
{
binode* p = q.front();
q.pop();
if (p->lchild)
{
q.push(p->lchild);
}
if (p->rchild)
{
q.push(p->rchild);
}
}
}
return maxwid;
}
int main()
{
cout << "开始创建树" << endl;
bitree tree;
cout << "中序遍历：" << endl;
tree.inorder();
cout <<"后序遍历："<< endl;
tree.postorder();
cout <<"前序遍历："<< endl;
tree.preorder();
cout << "树的深度：" << endl;
tree.Depth();
cout << "树的宽度" << endl;
tree.Width();
}
