定义一个二叉树
#include <stack>#include <queue>#include <unordered_map>#include <unordered_set>#include <iostream>using namespace std;class Node{public:int value;Node* left;Node* right;Node(int value):value(value){left = nullptr;right = nullptr;}};
生成一个平衡二叉树，满二叉树， 完全二叉树
//生成一个完全二叉树Node* fullTreeInit(){Node *head = new Node(1);head->left = new Node(2);head->right = new Node(3);head->left->left = new Node(4);head->left->right = new Node(5);head->right->left = new Node(6);head->right->right = new Node(7);return head;}//生成一个满二叉树Node* treeInit(){Node *head = new Node(1);head->left = new Node(2);head->right = new Node(3);head->left->left = new Node(4);head->left->right = new Node(5);head->right->left = new Node(6);head->right->right = new Node(7);return head;}
算法
//是否是完全二叉树bool isFBT(Node *head){if(head == nullptr){return true;}queue<Node*> q;q.push(head);Node *l, *r;bool leaf = false;while(!q.empty()){head = q.front();l = head->left;r = head->right;q.pop();//前面已经有叶节点了，但还是有左右节点if((leaf && (l != nullptr || r != nullptr))||(l == nullptr && r != nullptr) //有右无左){return false;}if(l != nullptr){q.push(l);}if(r != nullptr){q.push(r);}//虽然是或运算，其实只有无左无右才能到这里if(l == nullptr || r == nullptr){leaf = true;}}return true;}//判断是否是平衡二叉树class ReturnType{public:bool isBanlance;int height;ReturnType(bool isB, int h):isBanlance(isB), height(h){}};ReturnType isBanlanceTree(Node *head){if(head == nullptr){return ReturnType(true, 0);}ReturnType rt1 = isBanlanceTree(head->left);ReturnType rt2 = isBanlanceTree(head->right);int height = max(rt1.height, rt2.height) + 1;return ReturnType((rt1.isBanlance && rt2.isBanlance)&&(abs(rt1.height-rt2.height)<2),height);}//判断是否为满二叉树class Info{public:int height;int nodes;Info(int h, int n):height(h), nodes(n){}};Info isFullTree(Node* head){if(head == nullptr){return Info(0, 0);}Info if1 = isFullTree(head->left);Info if2 = isFullTree(head->right);int height = max(if1.height, if2.height)+1;int nodes = if1.nodes + if2.nodes + 1;return Info(height, nodes);}bool isFull(Node *head){Info info = isFullTree(head);return info.nodes == (1<<info.height)-1? true:false;}
