#include
#include
#include
#include
using namespace std;
typedef struct bitnode
{
int val;
struct bitnode* lchild, * rchild;
}bitnode,*bitree;
struct ReturnTypeOne
{
bool isBST;
int _min;
int _max;
};
struct ReturnTypeTwo
{
bool isAVL;
int height;
ReturnTypeTwo(bool _isAVL, int _height)
{
isAVL = _isAVL;
height = _height;
}
};
int StringToInt(string s)
{
int num = 0;
for (int i = 0; i < s.size(); i++)
{
num = num * 10 + s[i] - '0';
}
return num;
}
int preValue = INT_MIN;
//构建一颗二叉树
bitree createBitree(int level)
{
string s;
cout << "this is the " << level << "th's bitnode:" << endl;
cin >> s;
if (s == "n") {
return nullptr;
}
else {
int x = StringToInt(s);
bitree node = new bitnode;
node->val = x;
node->lchild = createBitree(level + 1);
node->rchild = createBitree(level + 1);
return node;
}
}
//递归的先序遍历
void preOrder(bitree node)
{
if (!node) return;
cout << node->val << ' ';
preOrder(node->lchild);
preOrder(node->rchild);
}
//非递归的先序遍历
void PreOrder(bitree node)
{
if (!node) return;
bitree stk[30];
int top = -1;
bitree pi = node;
while (pi || top != -1)
{
if (pi) {
stk[++top] = pi;
cout << pi->val << ' ';
pi = pi->lchild;
}
else pi = stk[top--]->rchild;
}
}
//递归的中序遍历
void inOrder(bitree node)
{
if (!node) return;
inOrder(node->lchild);
cout << node->val << ' ';
inOrder(node->rchild);
}
//非递归的中序遍历
void InOrder(bitree node)
{
if (!node) return;
bitree stk[30];
int top = -1;
bitree pi = node;
while (pi || top != -1)
{
if (pi) {
stk[++top] = pi;
pi = pi->lchild;
}
else{
pi = stk[top];
cout << pi->val << ' ';
top--;
pi = pi->rchild;
}
}
}
//递归的后序遍历
void postOrder(bitree node)
{
if (!node) return;
postOrder(node->lchild);
postOrder(node->rchild);
cout << node->val << ' ';
}
//非递归的后序遍历
void PostOrder(bitree node)
{
if (!node) return;
bitree stk[30];
int top = -1;
bitree pi = node, r = nullptr;
while (pi || top != -1)
{
if (pi) {
stk[++top] = pi;
pi = pi->lchild;
}
else {
pi = stk[top];
if (!pi->rchild || pi->rchild == r) {
cout << pi->val << ' ';
top--;
r = pi;
pi = nullptr;
}
else {
pi = pi->rchild;
}
}
}
}
//bfs
void bfs(bitree node)
{
if (!node) return;
queue<bitree> que;
que.push(node);
while (!que.empty())
{
auto pi = que.front();
if (pi->lchild) que.push(pi->lchild);
if (pi->rchild) que.push(pi->rchild);
cout << pi->val << ' ';
que.pop();
}
}
//判断是否完全二叉树
bool isCBT(bitree node)
{
if (!node) return true;
bool time = false;
queue<bitree> que;
que.push(node);
while (!que.empty())
{
bitree pi = que.front();
if ((!pi->lchild && pi->rchild) || (time && (pi->lchild || pi->rchild)))
return false;
if (pi->lchild) {
que.push(pi->lchild);
}
if (pi->rchild) {
que.push(pi->rchild);
}
if (!pi->rchild) time = true;
que.pop();
}
return true;
}
//判断是否满二叉树
bool isFBT(bitree node)
{
if (!node) return true;
queue<bitree> que;
int level = 0, cnt = 0;
que.push(node);
while (!que.empty())
{
int size = que.size();
cnt += size;
while (size--)
{
bitree pi = que.front();
if (pi->lchild) que.push(pi->lchild);
if (pi->rchild) que.push(pi->rchild);
que.pop();
}
level++;
}
return cnt == (1 << level) - 1;
}
//判断是否二叉排序树,方法一
bool isBST_AccessOne(bitree node)
{
if (!node) return true;
bool left = isBST_AccessOne(node->lchild);
if (!left) return false;
if (node->val <= preValue) return false;
else preValue = node->val;
return isBST_AccessOne(node->rchild);
}
//判断是否二叉排序树，方法二
ReturnTypeOne* isBST_AccessTwo(bitree node)
{
if (!node) return nullptr;
auto left = isBST_AccessTwo(node->lchild);
auto right = isBST_AccessTwo(node->rchild);
ReturnTypeOne* tmp = new ReturnTypeOne;
tmp->_min = node->val, tmp->_max = node->val;
if (left) {
tmp->_min = min(tmp->_min, left->_min);
tmp->_max= max(tmp->_max, left->_max);
}
if (right) {
tmp->_min = min(tmp->_min, right->_min);
tmp->_max = max(tmp->_max, right->_max);
}
tmp->isBST = true;
if ((left && left->_max >= node->val) || (right && right->_min <= node->val))
tmp->isBST = false;
return tmp;
}
//判断是否平衡二叉树
ReturnTypeTwo* isAVLTree(bitree node)
{
if (!node) return new ReturnTypeTwo(true,0);
auto left = isAVLTree(node->lchild);
auto right = isAVLTree(node->rchild);
int h = 1;
h += max(left->height, right->height);
bool isAVL = left->isAVL && right->isAVL && (abs(left->height - right->height) < 2);
return new ReturnTypeTwo(isAVL, h);
}
int main()
{
bitree root = createBitree(1);
cout << "PreTraverse: " << endl;
preOrder(root);
cout << endl;
PreOrder(root);
cout << endl;
cout << "intraverse: " << endl;
inOrder(root);
cout << endl;
InOrder(root);
cout << endl;
cout << "posttraverse: " << endl;
postOrder(root);
cout << endl;
PostOrder(root);
cout << endl;
cout << "bfstraverse: " << endl;
bfs(root);
cout << endl;
if (isCBT(root)) {
cout << "this is a complete binary tree!" << endl;
}
else {
cout << "this isn't a complete binary tree!" << endl;
}
if (isFBT(root)) {
cout << "this is a full binary tree!" << endl;
}
else {
cout << "this isn't a full binary tree!" << endl;
}
if (isBST_AccessOne(root)) {
cout << "this is a bst !" << endl;
}
else {
cout << "this isn't a bst !" << endl;
}
if (isBST_AccessTwo(root)->isBST) {
cout << "this is a bst !" << endl;
}
else {
cout << "this isn't a bst !" << endl;
}
if (isAVLTree(root)->isAVL) {
cout << "this is an AVL !" << endl;
}
else {
cout << "this isn't an AVL !" << endl;
}
return 0;
}