关于二叉树的一些心得

#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 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 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 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;

}