用于检查给定的二叉树是否为AVL树的C ++程序

• Z时代
• 2024-01-10
• 分类：综合

AVL树是一种自平衡二叉搜索树，其中左子树和右子树的高度之差对于所有节点都不能超过一个。

这是一个C ++程序，用于检查给定的二叉树是否为AVL树。

算法

Beginfunction AVL() returns true if the given tree is AVL otherwise false.
   if(root == NULL)
      return 1
   leftheight = height(root->left)
   rightheight = height(root->right)
   if(abs(leftheight-rightheight) <= 1 && AVL(root->left) && AVL(root->right))
      return 1
   return 0
End

示例

#include <bits/stdc++.h>
using namespace std;
class nod { //node declaration
   public:
   int data;
   nod* l;
   nod* r;
};
nod* newNod(int d) { //creation of new node
   nod* Nod = new nod();
   Nod->data = d;
   Nod->l = NULL;
   Nod->r = NULL;
   return(Nod);
}
int max(int x, int y) { //return maximum between two values
   return (x >= y)? x: y;
}
int height(nod* node) { //get the height means the number of nodes along the longest path from the root
node down to the farthest leaf node of the tree. 
   if(node == NULL)
      return 0;
   return 1 + max(height(node->l), height(node->r));
}
bool AVL(nod *root) {
   int lh;
   int rh;
   if(root == NULL)
      return 1;
   lh = height(root->l); // left height
   rh = height(root->r); // right height
   if(abs(lh-rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1;
   return 0;
}
int main() {
   //将树的节点作为输入
   nod *root = newNod(7);
   root->l = newNod(6);
   root->r = newNod(12);
   root->l->l = newNod(4);
   root->l->r = newNod(5);
   root->r->r = newNod(13);
   if(AVL(root))
      cout << "The Tree is AVL Tree"<<endl;
   else
      cout << "The Tree is not AVL Tree "<<endl;
   nod *root1 = newNod(7);
   root1->l = newNod(6);
   root1->r = newNod(12);
   root1->l->l = newNod(4);
   root1->l->r = newNod(5);
   root1->r->r = newNod(13);
   root1->r->r->r = newNod(26);
   if(AVL(root1))
      cout << "The Tree is AVL Tree"<<endl;
   else
      cout << "The Tree is not AVL Tree "<<endl;
   return 0;
}

输出结果

The Tree is AVL Tree
The Tree is not AVL Tree

以上是 用于检查给定的二叉树是否为AVL树的C ++程序 的全部内容， 来源链接： utcz.com/z/358670.html