数据结构笔记--常见二叉树分类及判断实现
目录
1--搜索二叉树
2--完全二叉树
3--平衡二叉树
4--满二叉树
1--搜索二叉树
搜索二叉树的性质：左子树的节点值都比根节点小，右子树的节点值都比根节点大；
如何判断一颗二叉树是搜索二叉树？
主要思路：
递归自底向上判断是否是一颗搜索二叉树，返回判断结果的同时，要返回对应的最小值和最大值；
#include <iostream>
#include <climits>struct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isBST = true;int max = 0;int min = 0;ReturnType(bool ib, int ma, int mi) : isBST(ib), max(ma), min(mi){}
};class Solution {
public:bool isBST(TreeNode *root){ReturnType res = dfs(root);return res.isBST;}ReturnType dfs(TreeNode *root){// 初始化最大值为整型最小值，最小值为整型最大值if(root == NULL) return ReturnType(true, INT_MIN, INT_MAX); ReturnType left = dfs(root->left);ReturnType right = dfs(root->right);bool isBST = true;if(!left.isBST || !right.isBST || left.max >= root->val || right.min <= root->val){isBST = false;}int min = std::min(std::min(root->val, left.min), std::min(root->val, right.min)); int max = std::max(std::max(root->val, left.max), std::max(root->val, right.max));return ReturnType(isBST, max, min);}
};int main(int argc, char *argv[]){TreeNode *Node1 = new TreeNode(4);TreeNode *Node2 = new TreeNode(2);TreeNode *Node3 = new TreeNode(6);TreeNode *Node4 = new TreeNode(1);TreeNode *Node5 = new TreeNode(3);TreeNode *Node6 = new TreeNode(5);TreeNode *Node7 = new TreeNode(7);Node1->left = Node2;Node1->right = Node3;Node2->left = Node4;Node2->right = Node5;Node3->left = Node6;Node3->right = Node7;Solution S1;bool res = S1.isBST(Node1);if (res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}2--完全二叉树
如何判断一颗二叉树是完全二叉树？
主要思路：
层次遍历二叉树的节点，当遇到第一个节点（其左右儿子不双全）进行标记，往后遇到的所有节点应均为叶子节点，当遇到一个不是叶子节点时，返回 false 表明二叉树不是完全二叉树；
#include <iostream>
#include <queue>struct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};class Solution {
public:bool isCBT(TreeNode *root){if(root == NULL) return true;std::queue<TreeNode*> q;q.push(root);bool flag = false; while(!q.empty()){ // 层次遍历TreeNode *cur = q.front();q.pop();if(cur->left != NULL) q.push(cur->left);if(cur->right != NULL) q.push(cur->right);if( // 标记节点后，还遇到了不是叶子节点的节点，返回false(flag == true && (cur->left != NULL || cur->right != NULL)) || // 左儿子为空，右儿子不为空，返回false(cur->left == NULL && cur->right != NULL)) return false;// 遇到第一个左右儿子不双全的节点进行标记if(cur->left == NULL || cur->right == NULL) flag = true;}return true;}
};int main(int argc, char *argv[]){TreeNode *Node1 = new TreeNode(1);TreeNode *Node2 = new TreeNode(2);TreeNode *Node3 = new TreeNode(3);TreeNode *Node4 = new TreeNode(4);TreeNode *Node5 = new TreeNode(5);TreeNode *Node6 = new TreeNode(6);TreeNode *Node7 = new TreeNode(7);TreeNode *Node8 = new TreeNode(8);TreeNode *Node9 = new TreeNode(9);TreeNode *Node10 = new TreeNode(10);TreeNode *Node11 = new TreeNode(11);TreeNode *Node12 = new TreeNode(12);Node1->left = Node2;Node1->right = Node3;Node2->left = Node4;Node2->right = Node5;Node3->left = Node6;Node3->right = Node7;Node4->left = Node8;Node4->right = Node9;Node5->left = Node10;Node5->right = Node11;Node6->left = Node12;Solution S1;bool res = S1.isCBT(Node1);if (res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}3--平衡二叉树
平衡二叉树要求：左子树和右子树的高度差 <= 1；
如何判断一颗二叉树是平衡二叉树？
主要思路：
递归自底向上判断是否是一颗平衡二叉树，返回判断结果的同时，要返回对应的深度；
#include <iostream>
#include <queue>struct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isbalanced = true;int height = 0;ReturnType(bool ib, int h) : isbalanced(ib), height(h) {}
};class Solution {
public:bool isBalanced(TreeNode *root){ReturnType res = dfs(root);return res.isbalanced;}ReturnType dfs(TreeNode *root){if(root == NULL) return ReturnType(true, 0);ReturnType left = dfs(root->left);ReturnType right = dfs(root->right);int cur_height = std::max(left.height, right.height) + 1; bool cur_balanced = left.isbalanced && right.isbalanced && std::abs(left.height - right.height) <= 1;return ReturnType(cur_balanced, cur_height);}private:int height = 0;
};int main(int argc, char *argv[]){TreeNode *Node1 = new TreeNode(1);TreeNode *Node2 = new TreeNode(2);TreeNode *Node3 = new TreeNode(3);TreeNode *Node4 = new TreeNode(4);TreeNode *Node5 = new TreeNode(5);TreeNode *Node6 = new TreeNode(6);TreeNode *Node7 = new TreeNode(7);TreeNode *Node8 = new TreeNode(8);TreeNode *Node9 = new TreeNode(9);TreeNode *Node10 = new TreeNode(10);TreeNode *Node11 = new TreeNode(11);TreeNode *Node12 = new TreeNode(12);Node1->left = Node2;Node1->right = Node3;Node2->left = Node4;Node2->right = Node5;Node3->left = Node6;Node3->right = Node7;Node4->left = Node8;Node4->right = Node9;Node5->left = Node10;Node5->right = Node11;Node6->left = Node12;Solution S1;bool res = S1.isBalanced(Node1);if (res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}4--满二叉树
满二叉树的判断：节点数 = 2^深度 - 1；
如何判断一颗二叉树是平衡二叉树？
主要思路：
递归自底向上判断是否是一颗满二叉树，返回判断结果的同时，要返回对应的深度和节点数；
#include <iostream>
#include <queue>struct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isFCT = true;int height = 0;int nodes = 0;ReturnType(bool ib, int h, int n) : isFCT(ib), height(h), nodes(n){}
};class Solution {
public:bool isFCT(TreeNode *root){ReturnType res = dfs(root);return res.isFCT;}ReturnType dfs(TreeNode *root){if(root == NULL) return ReturnType(true, 0, 0);ReturnType left = dfs(root->left);ReturnType right = dfs(root->right);bool isFCT = true;int cur_nodes = left.nodes + right.nodes + 1;int cur_height = std::max(left.height, right.height) + 1;if(!left.isFCT || !right.isFCT || (1<<cur_height) - 1 != cur_nodes){isFCT = false;}return ReturnType(isFCT, cur_height, cur_nodes);}
};int main(int argc, char *argv[]){TreeNode *Node1 = new TreeNode(1);TreeNode *Node2 = new TreeNode(2);TreeNode *Node3 = new TreeNode(3);TreeNode *Node4 = new TreeNode(4);TreeNode *Node5 = new TreeNode(5);TreeNode *Node6 = new TreeNode(6);TreeNode *Node7 = new TreeNode(7);TreeNode *Node8 = new TreeNode(8);TreeNode *Node9 = new TreeNode(9);TreeNode *Node10 = new TreeNode(10);TreeNode *Node11 = new TreeNode(11);TreeNode *Node12 = new TreeNode(12);Node1->left = Node2;Node1->right = Node3;Node2->left = Node4;Node2->right = Node5;Node3->left = Node6;Node3->right = Node7;Node4->left = Node8;Node4->right = Node9;Node5->left = Node10;Node5->right = Node11;Node6->left = Node12;Solution S1;bool res = S1.isFCT(Node1);if (res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}