ツリーの基本概念

1本の二叉樹の結点の有限集合:この集合は空であるか、1本の結点に左子樹と右子樹と呼ばれる2本の交差しない二叉樹からなる.
関連性:
1.二叉木の第i(i>=1)層に最大2のi−1次方結点がある.
2.深さk(k>=0)の二叉木には最低k個の接点があり、最大2個のk次方-1個の接点がある.
3.リーフノード数等度2の非リーフノード数に1:N 0=N 2+1を加算
4.満二叉木:深さkの満二叉木は2のk次-1個の接点がある
5.完全二叉木:各接点は高さkの満二叉木における番号1~nの接点1つに対応
6.n個のノードを有する完全な二叉木の深さはlog 2(n+1)上向きに整列する
抽象データ型:

#ifndef BINARYTREE_H
#define BINARYTREE_H

template<typename T>
class BinaryTree{
public:
    BinaryTree();
    //item  ,lch,rch     
    BinaryTree(BinTreeNode<T>* lch,BinTreeNode<T>* rch,T item);
    int Height();
    int Size();//    
    bool IsEmpty();
    BinTreeNode<T> *Parent(BinTreeNode<T>* current);
    BinTreeNode<T> *LeftChild(BinTreeNode<T>* current);
    BinTreeNode<T> *RightChild(BinTreeNode<T>* current);
    bool Insert(T item);
    bool Remove(T item);
    bool Find(const T& item)const;
    bool getData(const T& item)const;
    BinTreeNode<T>* getRoot()const;
    void preOrder(void(*visit)(BinTreeNode<T>*p));//  
    void inOrder(void(*visit)(BinTreeNode<T>*p));//  
    void postOrder(void(*visit)(BinTreeNode<T>*p));//  
    void levelOrder(void(*visit)(BinTreeNode<T>*p));//  
};

#endif // BINARYTREE_H