数据结构 - 平衡二叉树

迈不过友情╰ 2022-04-22 07:28 231阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

# 平衡二叉树的定义 #

**平衡二叉树**（Balanced Binary Tree）是具有以下性质的二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

# 判断一棵二叉树是否平衡（C++） #

#include <iostream>#define NULL 0using namespace std;template<class T>struct BTNode{
          T data; BTNode<T> *lChild, *rChild; BTNode(); BTNode(const T &val, BTNode<T> *childL = NULL, BTNode<T> *childR = NULL) {  data = val;  lChild = childL;  rChild = childR; } BTNode<T>* CopyTree() {  BTNode<T> *nl, *nr, *nn;  if(&data == NULL)  {   return NULL;  }  nl = lChild->CopyTree();  nr = rChild->CopyTree();  nn = new BTNode<T>(data, nl, nr);  return nn; }};template<class T>BTNode<T>::BTNode(){ lChild = rChild = NULL;}template<class T>class BinaryTree{
         public: BTNode<T> *root; BinaryTree(); ~BinaryTree(); void DestroyTree(); BTNode<T>* MakeTree(const T &element, BTNode<T> *l, BTNode<T> *r) {  root = new BTNode<T> (element, l, r);  if(root == NULL)  {   cout << "Failure for applying storage address, system will close the process." << endl;   exit(1);  }  return root; }private: void Destroy(BTNode<T> *&r);};template<class T>BinaryTree<T>::BinaryTree(){ root = NULL;}template<class T>BinaryTree<T>::~BinaryTree(){ DestroyTree();}template<class T>void BinaryTree<T>::DestroyTree(){ Destroy(root);}template<class T>void BinaryTree<T>::Destroy(BTNode<T> *&r){ if(r != NULL) {  Destroy(r->lChild);  Destroy(r->rChild);  delete r;  r = NULL; }}template<class T>int isBalanced(BTNode<T> *r){
          if(!r) {  return 0; } int left = isBalanced(r->lChild); int right = isBalanced(r->rChild); if((left >= 0) && (right >= 0) && ((left - right) <= 1) && ((left - right) >= -1)) {  return (left < right) ? (right + 1) : (left + 1); } else {  return -1; }}void main(){ BTNode<char> *b, *c, *d, *e, *f, *g; BinaryTree<char> a; b = a.MakeTree('F', NULL, NULL); c = a.MakeTree('E', NULL, NULL); d = a.MakeTree('D', b, NULL); e = a.MakeTree('C', NULL, NULL); f = a.MakeTree('B', d, c); g = a.MakeTree('A', f, e); if(isBalanced(a.root) >= 0) {  cout << "This IS a balanced binary tree." << endl; } else {  cout << "This is NOT a balanced binary tree." << endl; }}// Output:/*This is NOT a balanced binary tree.*/

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220422/cece7439a18f41fca9efb014a7f8c79a.png