【王道数据结构】【chapter7查找】【P308t7】

本文主要是介绍【王道数据结构】【chapter7查找】【P308t7】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法

#include <iostream>
#include <queue>
typedef struct node{int data;struct node* left;struct node* right;
}node,*pnode;pnode buynode(int x)
{pnode tmp=(pnode) malloc(sizeof (node));tmp->data=x;tmp->left= nullptr,tmp->right= nullptr;return tmp;
}void build_tree(pnode &root,int data)
{if(root== nullptr) {root= buynode(data);return;}if(data<root->data)build_tree(root->left,data);if(data==root->data) return;if(data>root->data) build_tree(root->right,data);
}void print(pnode root)
{if(root== nullptr) return;std::queue<pnode> record;record.push(root);int size=record.size();while(!record.empty()){pnode head=record.front();printf("%3d",head->data);record.pop();if(head->left) record.push(head->left);if(head->right) record.push(head->right);if(--size==0) puts(""),size=record.size();}
}
void _judge_banlance_avl(pnode root,int &balance ,int &hight)
{int bl=0,br=0,hl=0,hr=0;if(root== nullptr) balance=1,hight=0;else if(!root->left&&!root->right) balance=1,hight=1;else{_judge_banlance_avl(root->left,bl,hl);_judge_banlance_avl(root->right,br,hr);hight=(hl>hr?hl:hr)+1;if(abs(hl-hr)>1) balance=0;else balance=bl&&br;}
}bool judge_balance_avl(pnode root)
{int balance =0,hight=0;_judge_banlance_avl(root,balance,hight);return balance;
}int main() {pnode r1= nullptr;//p295图7.8(a),这是一棵平衡二叉排序树int a[]={45,24,12,37,28,40,55,53,60,70};for(int i=0;i<10;i++){build_tree(r1,a[i]);}print(r1);if(judge_balance_avl(r1)) printf("this is a balance treee\n");else printf("this is not a balance tree\n");pnode r2= nullptr;//p295图7.8(b)，这是一棵非平衡二叉树int b[]={12,24,28,37,40,45,53,55,60,70};for(int i=0;i<10;i++){build_tree(r2,b[i]);}print(r2);if(judge_balance_avl(r2)) printf("this is a balance treee\n");else printf("this is not a balance tree\n");return 0;
}