推断二叉树是不平衡树 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 输入一颗二叉树的根结点, 推断该树是不是平衡二叉树.

二叉平衡树: 随意结点的左右子树的深度相差不超过1.

使用后序遍历的方式, 而且保存左右子树的深度, 进行比較.

代码:

/*

 * main.cpp

 *

 *  Created on: 2014.6.12

 *      Author: Spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct BinaryTreeNode {

	int m_nValue;

	BinaryTreeNode* m_pLeft;

	BinaryTreeNode* m_pRight;

};

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth) {

	if (pRoot == NULL) {

		*pDepth = 0;

		return true;

	}

	int left, right;

	if (IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right)) {

		int diff = left - right;

		if (diff>=-1 && diff<=1) {

			*pDepth = 1 + (left>right?left:right);

			return true;

		}

	}

	return false;

}

bool IsBalanced(BinaryTreeNode* pRoot) {

	int depth = 0;

	return IsBalanced(pRoot, &depth);

}

BinaryTreeNode* init(void) {

	BinaryTreeNode* pRoot = new BinaryTreeNode(); pRoot->m_nValue = 1;

	BinaryTreeNode* pNode2 = new BinaryTreeNode(); pNode2->m_nValue = 2;

	BinaryTreeNode* pNode3 = new BinaryTreeNode(); pNode3->m_nValue = 3;

	BinaryTreeNode* pNode4 = new BinaryTreeNode(); pNode4->m_nValue = 4;

	BinaryTreeNode* pNode5 = new BinaryTreeNode(); pNode5->m_nValue = 5;

	BinaryTreeNode* pNode6 = new BinaryTreeNode(); pNode6->m_nValue = 6;

	BinaryTreeNode* pNode7 = new BinaryTreeNode(); pNode7->m_nValue = 7;

	pRoot->m_pLeft = pNode2; pRoot->m_pRight = pNode3;

	pNode2->m_pLeft = pNode4; pNode2->m_pRight = pNode5;

	pNode4->m_pLeft = NULL; pNode4->m_pRight = NULL;

	pNode5->m_pLeft = pNode7; pNode5->m_pRight = NULL;

	pNode7->m_pLeft = NULL; pNode7->m_pRight = NULL;

	pNode3->m_pLeft = NULL; pNode3->m_pRight = pNode6;

	pNode6->m_pLeft = NULL; pNode6->m_pRight = NULL;

	return pRoot;

}

int main(void)

{

	BinaryTreeNode* pRoot = init();

	bool result = IsBalanced(pRoot);

	printf("result = %s\n", result==false?"false":"true");

    return 0;

}

输出:

result = true