//Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
//
// 译文：
//
// 给定一个有序数组(递增)，写程序构建一棵具有最小高度的二叉树。
#include <iostream>
#include <string>
#include <queue>
using namespace std;
class tree
{
public:
tree()
{
//root = create();
root = NULL;
index = 0;
}
/***输入扩展层次遍历序列，#表示该节点为空***/
tree(char *s)
{
root = NULL;
index = 0;
if (s == NULL)
{
return;
}
int size = strlen(s);
create(&root,s,0,size);
}
~tree()
{
/***清空二叉树***/
}
/***二叉排序树：插入。***/
void insert(char *s)
{
if (s == NULL)
{
return;
}
int size = strlen(s);
for (int i = 0; i<size; i++)
{
insert(&root, s[i]);
}
}
void createBanlance(char *s)
{
int size = strlen(s);
createB(&root, s, 0, size-1);
cout<<"End"<<endl;
}
void levelOrder()
{
queue<treenode *> q;
if (root != NULL)
{
q.push(root);
}
while(!q.empty())
{
treenode *t = q.front();
cout<<t->data<<endl;
q.pop();
if (t->left != NULL)
{
q.push(t->left);
}
if (t->right != NULL)
{
q.push(t->right);
}
}
}
bool isBanlance(int size)
{
int *s = new int[size];
depth(root,s,size,0);
s[index+1] = '\0';
int i = 0;
int max = s[0];
int min = s[0];
while(s[i]!='\0')
{
if (s[i]>max)
{
max = s[i];
}
if (s[i]<min)
{
min = s[i];
}
i++;
}
return ((max - min)>1? 0:1);
}
void preOrder(){ pOrder(root);}
void inOreder(){ zOrder(root);}
void postOreder(){ hOrder(root);}
private:
struct treenode
{
char data;
treenode * left;
treenode * right;
};
treenode *root;
int index;
void insert(treenode **p, char s)
{
if (((*p) == NULL) && s != '\0')
{
*p = new treenode;
(*p)->data = s;
(*p)->left = NULL;
(*p)->right = NULL;
}
else
{
if ((*p)->data > s)
{
insert(&((*p)->left) , s);
}
else
{
insert(&((*p)->right) , s);
}
}
}
/**取begin,end中间值做根节点，两值相等相等为叶节点，大于为空**/
void createB(treenode **p, char *s, int begin, int end)
{
if (begin>end)
{
*p = NULL;
return;
}
else if (begin == end)
{
*p = new treenode;
(*p)->data = s[end];
(*p)->left = (*p)->right = NULL;
}
else
{
*p = new treenode;
int mid = (begin + end)/2;
(*p)->data = s[mid];
cout<<s[mid]<<endl;
createB(&((*p)->left), s, begin, mid -1);
createB(&((*p)->right), s, mid +1, end);
}
}
void depth(treenode *s, int *str,int size,int k)
{
if (s==NULL)
{
return;
}
if (s->left == NULL && s->right == NULL)
{
str[index]= k;
index++;
}
else
{
depth(s->left,str, size, k+1);
depth(s->right,str, size, k+1);
}
}
treenode* create()
{
treenode *p;
char t;
cout<<"请输入："<<endl;
t = getchar();
if (t=='#')
{
p = NULL;
}
else
{
p = new treenode;
p->data = t;
cout<<"create tree node: "<<t<<endl;
p->left = create();
p->right = create();
}
return p;
}
void create(treenode **p, char *str, int i, int size)
{
if (i>size-1 || str[i] == '\0')
{
*p = NULL;
return;
}
if (str[i] == '#')
{
*p=NULL;
}
else
{
*p = new treenode;
(*p)->data = str[i];
create(&((*p)->left),str,2*i+1,size);
create(&((*p)->right),str,2*i+2,size);
}
}
void pOrder(treenode *p)
{
if (p==NULL)
{
return;
}
cout<<p->data<<" "<<endl;
pOrder(p->left);
pOrder(p->right);
}
void zOrder(treenode *p)
{
if (p==NULL)
{
return;
}
zOrder(p->left);
cout<<p->data<<" "<<endl;
zOrder(p->right);
}
void hOrder(treenode *p)
{
if (p==NULL)
{
return;
}
hOrder(p->left);
cout<<p->data<<" "<<endl;
hOrder(p->right);
}
};
int main()
{
/***扩展层次序列简立树***/
//char t[9] = "ABCDE#FG";
//tree s(t);
//s.preOrder();
/***建立二叉排序树***/
//tree s;
//char t[8] = "3289654";
//s.insert(t);
// s.postOreder();
/**4.1*************************/
//cout<<"is Banlance? "<<s.isBanlance(8)<<endl;
/**4.3*************************/
tree s;
char t[9] = "12345678";
s.createBanlance(t);
s.preOrder();
cout<<"Over"<<endl;
/**非递归层次遍历*************************/
/*tree s;
char t[8] = "3289654";
s.insert(t);
s.levelOrder();*/
return 0;
}