数据结构——平衡二叉树的判断【递归算法】（C语言）

平衡二叉树的判断（左右子树的高度差只能为-1，0，1） #include<stdio.h> #include<stdlib.h> #include<queue> #include <iostream> #define MAXSIZE 10010 #define ElemType int using namespace std; typedef struct BTNode{ ElemType data; BTNode *lchild,*rchild; }*BTree; //先序建树 BTree CreateTree(){ ElemType ch; printf("输入结点元素值："); scanf("%d",&ch); if(ch == 0) return NULL; else{ BTree tree=(BTree)malloc(sizeof(BTree)); tree->data=ch; printf("%d 结点左子树\n",ch); tree->lchild=CreateTree(); printf("%d 结点右子树\n",ch); tree->rchild=CreateTree(); return tree; } } //层次遍历 void LayeredOrderTravel(BTree tree){ queue<BTree> queue1; BTree p; if(tree){//树非空 //入队与队列指针（下标）初始化 queue1.push(tree); while(!queue1.empty()){//队列非空 p=queue1.front();//队头元素出队并访问 queue1.pop(); printf("%d ",p->data);//访问 if(p->lchild)//左孩子不为空则入队 queue1.push(p->lchild); if(p->rchild)//右孩子不为空则入队 queue1.push(p->rchild); } } } int getDepth(BTree tree){ if(!tree) return 0; else{ int leftDepth=getDepth(tree->lchild); int rightDepth=getDepth(tree->rchild); return leftDepth > rightDepth ? (leftDepth+1):(rightDepth+1); } } bool IsBalanceTree(BTree tree){ if(!tree) return true; int leftDepth=getDepth(tree->lchild); int rightDepth=getDepth(tree->rchild); if(abs(leftDepth-rightDepth)>1)//判断左右子树高度绝对值之差是否大于1，若是则为非平衡二叉树 return false; else{//递归判断该结点的左右子树 return IsBalanceTree(tree->lchild)&&IsBalanceTree(tree->rchild); } } int main(){ printf("二叉树的建立\n"); BTree tree; tree=CreateTree(); printf("二叉树的层序遍历\n"); LayeredOrderTravel(tree); printf("\n判断是否为平衡二叉树\n"); bool flag=IsBalanceTree(tree); if(flag) printf("该树为平衡二叉树\n"); else printf("该树为非平衡二叉树\n"); return 0; }