数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究检查给定二叉树是否为 AVL 树的 C++ 程序
AVL 树是自平衡二叉查找树，其中对于所有节点，左右子树高度之差不能超过 1。
这是一个 C++ 程序，用于检查给定的二叉树是否为 AVL 树。
算法
Begin function 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() {
//take the nodes of the tree as input
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
更新于： 2019 年 7 月 30 日
已阅读 2K+ 次
广告