1.判断二叉树是否平衡
//求树的高度 int TreeDepth(Node* t) { int hl,hr,h; if(t != NULL) { hl = TreeDepth(t->left); hr = TreeDepth(t->right); h = hl>hr? hl:hr; return h+1; } return 0; } //判断二叉树是否平衡 int isBalanced(Node* t) { if(t==NULL) return 1; int leftDepth = TreeDepth(t->left); int rightDepth = TreeDepth(t->right); if(abs(leftDepth-rightDepth) > 1) return 0; else return isBalanced(t->left) && isBalanced(t->right); }
2.判断二叉树是否相同
//判断两棵二叉树是否相同 int CompTree(Node* tree1, Node* tree2) { if(tree1 == NULL && tree2 == NULL) return 1; else if(tree1 == NULL || tree2 == NULL) return 0; if(tree1->data != tree2->data) return 0; if(CompTree(tree1->left,tree2->left)==1 && CompTree(tree1->right,tree2->right)==1) return 1; //反转二叉树也可能相同 if(CompTree(tree1->left,tree2->right)==1 && CompTree(tree1->right,tree2->left)==1) return 1; return 0; }
//拷贝二叉树 void CopyTree(Node* s,Node* & d) { if(s==NULL) d = NULL; Node* temp = new Node; temp->data = s->data; if(d==NULL) d = temp; if(s->left) CopyTree(s->left,d->left); if(s->right) CopyTree(s->right,d->right); }
3.判断二叉树是否完全二叉树
判断二叉树是否是完全二叉树：层次遍历二叉树，遍历的左右节点入队列。若出队列的结点为空，则以后出队列的结点都为空，则为完全二叉树，否则不是
int ComplateTree(Node* bt) { Node* p=bt; queue<Node*> q; int tag=0; if(p==NULL) return 1; q.push(p); while(!q.empty()) { p=q.front(); q.pop(); if(p->left && !tag) q.push(p->left); else if(p->left) return 0; else tag=1; if(p->right && !tag) q.push(p->right); else if(p->right) return 0; else tag=1; } return 1; }
4.判断二叉树是否二叉排序树
判断二叉树是否是二叉排序树（BST）：根据中序遍历序列是否升序来判断
bool IsBinarySortTree(Node* bt) { stack<Node*> s; Node* p = bt; Node* pre = NULL; // pre保持为p的中序前驱 while(p || !s.empty()) { if(p) { s.push(p); p = p->left; } else { p = s.top(); s.pop(); if( pre && (p->data <= pre->data) ) return false; // 不是二叉排序树 pre = p; // 记下前驱结点 p = p->right; } } return true; // 二叉排序树 }
判断二叉树是否是二叉排序树（BST）：层次遍历二叉树，若出队列的结点小于左结点的值，或者是大于右结点的值，则不是BST，否则是BST
bool IsBST(Node* T) { queue<Node*> q; Node* p; if(T == NULL) return true; q.push(T); while(!q.empty()) { p = q.front(); q.pop(); if(p->left) if(p->data < p->left->data) return false; else q.push(p->left); if(p->right) if(p->data > p->right->data) return false; else q.push(p->right); } return true; }
