C语言数据结构之平衡二叉树（语言数据结构之平衡二叉树（AVL树）实现方法示例树）实现方法示例
主要介绍了C语言数据结构之平衡二叉树（AVL树）实现方法,结合实例形式分析了C语言平衡二叉树的相关定义
与使用技巧,需要的朋友可以参考下
本文实例讲述了C语言数据结构之平衡二叉树（AVL树）实现方法。分享给大家供大家参考，具体如下：
AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树。
要维持这个树，必须在插入和删除的时候都检测是否出现破坏树结构的情况。然后立刻进行调整。
看了好久，网上各种各种的AVL树，千奇百怪。
关键是要理解插入的时候旋转的概念。
//
// AvlTree.h
// HelloWorld
// Created by feiyin001 on 17/1/9.
// Copyright (c) 2017年 FableGame. All rights reserved.
//
#ifndef __HelloWorld__AvlTree__
#define __HelloWorld__AvlTree__
#include <iostream>
namespace Fable
{
int max(int a, int b)
{
return a > b? a:b;
}
//二叉查找树，对于Comparable,必须实现了><=的比较
template<typename Comparable>
class AvlTree
{
public:
//构造函数
AvlTree(){}
//复制构造函数
AvlTree(const AvlTree& rhs)
{
root = clone(rhs.root);
}
//析构函数
~AvlTree()
{
makeEmpty(root);
}
//复制赋值运算符
const AvlTree& operator=(const AvlTree& rhs)
{
if (this != &rhs)
{
makeEmpty(root);//先清除
root = clone(rhs.root);//再复制
}
return *this;
}
//查找最小的对象
const Comparable& findMin()const
{
findMin(root);
}
//查找最大的对象
const Comparable& findMax()const
{
findMax(root);
}
//是否包含了某个对象
bool contains(const Comparable& x)const
{
return contains(x, root);
}
//树为空
bool isEmpty()const
{
return root == nullptr;
}
//打印整棵树
评论0