认识达内从这里开始

判断一棵树是平衡树

//树结构

typedef struct TreeNode

{

Node* _left;

Node* _right;

int _bf;

}Node;

int _Height(Node *root)

{

if(root == NULL)

return 0;

int left = _Height(root->_left);

int right = _Height(root->_right);

return lefe > right?left+1:right+1;

}

bool _isBlanceTree(Node *root)

{

if(root == NULL)

return true;

int left = _Height(root->_left);

int right = _Height(root->_right);

if(left - right != root->bf)

{

return false;

}

return abs(left-right) < 2 && _isBlance(root->_left) && _isBlance(root->_right);

}

-------------------------------------------------------------------------------------------

2.二叉搜索树转换为双向链表

void BuilderList(BinaryTreeNode* root, BinaryTreeNode **prev)

{

if (root == NULL)

{

return;

}

BinaryTreeNode* cur = root;

if (cur->_left != NULL)

{

BuilderList(cur->_left, prev);

}

cur->_left = *prev;

if (*prev!= NULL)

{

(*prev)->_right = cur;

}

(*prev) = cur;

if (cur->_right != NULL)

{

BuilderList(cur->_right, prev);

}

}

BinaryTreeNode* BSTtoList(BinaryTreeNode* root)

{

//用来连接节点的前驱节点

BinaryTreeNode* prev = NULL;

BuilderList(root,&prev);

BinaryTreeNode* newList = prev;

while (newList != NULL && newList->_left != NULL)

{

newList = newList->_left;

}

return newList;

}

-------------------------------------------------------------------------------------------

3.判断一棵树是不是红黑树

bool _IsBalance(Node* root, const int k, int count)

{

if (root == NULL)

return true;

if (root->_col == RED)

{

if (root->_parent->_col == RED)

{

cout << "颜色不正确" << root->_key << endl;

return false;

}

}

else

++count;

if (root->_left == NULL&&root->_right == NULL)

{

if (count == k)

return true;

else

{

cout << "黑色节点个数不对" << root->_key << endl;

return false;

}

}

return _IsBalance(root->_left, k, count) && _IsBalance(root->_right, k, count);

}