判断二叉树是不是平衡二叉树

ゞ浴缸里的玫瑰 2022-08-02 04:49 232阅读 0赞

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树：

![Center][]

// IsbalenceTree.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct BiNOde
    {
    	char ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	root->ele = 0;
    	node1->ele = 1;
    	node2->ele = 2;
    	node3->ele = 3;
    	node4->ele = 4;
    	node5->ele = 5;
    	node6->ele = 6;
    	node7->ele = 7;
    	node8->ele = 8;
    	node9->ele = 9;
    	node10->ele = 10;
    	node11->ele = 11;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = node11;
    	node4->lnode = node10;
    	node4->rnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = NULL;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;
    	//node12->ele = 12;
    	//node12->lnode = NULL;
    	//node12->rnode = NULL;
    	//node6->lnode = node11;
    	return root;
    }
    
    int depth(BiNOde*node)
    {
    
    	if (node == NULL || node->lnode == NULL&&node->rnode == NULL)
    		return 0;
    	if (node->lnode != NULL)
    		if (node->rnode != NULL)
    		{
    		if ((node->lnode->lnode == NULL&&node->lnode->rnode == NULL
    			&&node->rnode->lnode == NULL&&node->rnode->rnode == NULL))
    			return 1;
    		}
    		else
    		{
    			if ((node->lnode->lnode == NULL&&node->lnode->rnode == NULL))
    				return 1;
    		}
    	else
    		if (node->rnode != NULL)
    		{
    		if (node->rnode->lnode == NULL&&node->rnode->rnode == NULL)
    			return 1;
    		}
    	return 1 + max(depth(node->lnode), depth(node->rnode));
    
    }
    
    
    bool IsbalenceTree(BiNOde* node)
    {
    	if (node->lnode == NULL&&node->rnode == NULL)
    		return true;
    	if (node->lnode == NULL)
    	{
    		if (node->rnode->lnode != NULL || node->rnode->rnode != NULL)
    			return false;
    		return true;
    	}
    	if (node->rnode == NULL)
    	{
    		if (node->lnode->lnode != NULL || node->lnode->rnode != NULL)
    			return false;
    		return true;
    	}
    	if (abs(depth(node->lnode) - depth(node->rnode)) > 1)
    		return false;
    	return IsbalenceTree(node->lnode) && IsbalenceTree(node->rnode);
    
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	//char b = 0;
    	//cout << b << endl;
    	BiNOde*root = new BiNOde;
    	root = create_tree();
    
    	cout << depth(root) << endl;
    	if (IsbalenceTree(root))
    		cout << "是平衡二叉树" << endl;
    	else
    		cout << "不是平衡二叉树" << endl;
    	system("pause");
    	return 0;
    }

[Center]: /images/20220731/e0886ac35f2c40a4acef2b095af2b336.png