#include <iostream>
#include <malloc.h>
using namespace std;
#include <queue>
class tre
{
private:
struct binarytree* tree;
void create(binarytree*& e); //树创建
void preOrder(binarytree* e); //先序遍历
void inOrder(binarytree* e); //中序遍历
void postOrder(binarytree* e); //后序遍历
void levelOrder(binarytree* e); //层次遍历
int hight(binarytree*& e); //确定二叉树高度
public:
tre();
tre(binarytree*& e);
void trcreate() ; //树创建
void trpreOrder(); //先序遍历
void trinOrder(); //中序遍历
void trpostOrder() ; //后序遍历
void trlevelOrder(); //层次遍历
void trhight(); //确定二叉树高度
void gethi();
};
typedef struct binarytree
{
char element;
struct binarytree* leftchild, * rightchild;
int hl; //左子树高
int hr; //右子树高
int hi; //树高
}*tree, treenode;
int main()
{
tre fe;
fe.trcreate();
fe.gethi();
}
void tre::trpreOrder()
{preOrder(tree);}
void tre::trpostOrder()
{postOrder(tree);}
void tre::trlevelOrder()
{levelOrder(tree);}
void tre::trinOrder()
{inOrder(tree);}
void tre::trhight()
{hight(tree);}
void tre::trcreate(){
create(tree);
}
void tre::gethi()
{
cout<< tree->hi<<endl;
cout<<tree->hl;
}
tre::tre()
{
tree=(binarytree*)malloc(sizeof(binarytree));
tree->hi=0;
tree->hl=0;
tree->hr=0;
}
tre::tre(binarytree* &e)
{
e = new treenode;
tree = e;
e->hi = 0; e->hl = 0; e->hr = 0; e->leftchild = NULL; e->rightchild = NULL;
}
void tre::create(binarytree*& e)
{
char s;
cin >> s;
if (s == '#')
{
e = NULL;
return;
}
e = new treenode;
e->element = s;
create(e->leftchild);
create(e->rightchild);
}
void tre::preOrder(binarytree* e)
{
if (e != NULL)
{
cout << e->element << " ";
preOrder(e->leftchild);
preOrder(e->rightchild);
}
}
void tre::inOrder(binarytree* e)
{
if (e != NULL)
{
preOrder(e->leftchild);
cout << e->element << " ";
preOrder(e->rightchild);
}
}
void tre::postOrder(binarytree* e)
{
if (e != NULL)
{
preOrder(e->leftchild);
preOrder(e->rightchild);
cout << e->element << " ";
}
}
void tre::levelOrder(binarytree* e)
{
queue <binarytree*> s;
while (e != NULL)
{
cout << e->element << " ";
if (e->leftchild != NULL)
s.push(e->leftchild);
if (e->rightchild != NULL)
s.push(e->rightchild);
if (s.empty()) return;
e = s.front();
s.pop();
}
}
int tre::hight(binarytree* &e)
{
if (e == NULL) return 0;
e->hl=hight(e->leftchild);
e->hr=hight(e->rightchild);
if (e->hl > e->hr)
return ++e->hl;
else
return ++e->hr;
}
左子树高度为什么应该是0？