数据结构 - 二叉树（C++）_c++二叉树定义

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击人工智能教程

二叉树的定义

      二叉树（BinaryTree）是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。

二叉树的性质

性质1　二叉树第i层上的结点数目最多为2^(i-1)(i≥1)。
证明：

　　用数学归纳法证明。
　　归纳基础：i=1时，有2^(i-1)=2^(0)=1。因为第1层上只有一个根结点，所以命题成立。
　　归纳假设：假设对所有的j（1≤j<i）命题成立，即第j层上至多有2^(j-1)个结点，证明j=i时命题亦成立。
　　归纳步骤：根据归纳假设，第i-1层上至多有2^(i-1-1)=2^(i-2)个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2^(i-2)=2^(i-1)个结点，故命题成立。

性质2　深度为k的二叉树至多有2^k-1个结点(k≥1)。
证明：

　　在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
　　　　2^0+2^1+…+2^(k-1)=2^k-1
　　故命题正确。

性质3　在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
证明：

　　因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数n0、1度结点数n1和2度结点数n2之和，即

　　　　n=n0+n1+n2　（式子1）

　　另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是n1+2n2，而树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为

　　　　n=n1+2n2+1　（式子2）

　　由式子1和式子2得到：

　　　　n0=n2+1

二叉树的实现（C++）

/*
 * Created by Chimomo
 */
 
#include <iostream>
 
#define NULL 0
 
using namespace std;
 
template<class T>
struct BTNode {
    T data;
    BTNode<T> *lChild, *rChild;
 
    BTNode();
 
    BTNode(const T &val, BTNode<T> *lChild = NULL, BTNode<T> *rChild = NULL) {
        data = val;
        this->lChild = lChild;
        this->rChild = rChild;
    }
 
    BTNode<T> *CopyTree() {
        BTNode<T> *l, *r, *n;
        if (&data == NULL) {
            return NULL;
        }
        l = lChild->CopyTree();
        r = rChild->CopyTree();
        n = new BTNode<T>(data, l, r);
        return n;
    }
};
 
template<class T>
BTNode<T>::BTNode() {
    lChild = rChild = NULL;
}
 
template<class T>
class BinaryTree {
public:
    BTNode<T> *root;
 
    BinaryTree();
 
    ~BinaryTree();
 
    void Pre_Order();
 
    void In_Order();
 
    void Post_Order();
 
    int TreeHeight() const;
 
    int TreeNodeCount() const;
 
    void DestroyTree();
 
    BTNode<T> *MakeTree(const T &element, BTNode<T> *l, BTNode<T> *r) {
        root = new BTNode<T>(element, l, r);
        if (root == NULL) {
            cout << "Failure for applying storage address, system will close the process." << endl;
            exit(1);
        }
        return root;
    }
 
private:
    void PreOrder(BTNode<T> *r);
 
    void InOrder(BTNode<T> *r);
 
    void PostOrder(BTNode<T> *r);
 
    int Height(const BTNode<T> *r) const;
 
    int NodeCount(const BTNode<T> *r) const;
 
    void Destroy(BTNode<T> *&r);
};
 
template<class T>
BinaryTree<T>::BinaryTree() {
    root = NULL;
}
 
template<class T>
BinaryTree<T>::~BinaryTree() {
    DestroyTree();
}
 
template<class T>
void BinaryTree<T>::Pre_Order() {
    PreOrder(root);
}
 
template<class T>
void BinaryTree<T>::In_Order() {
    InOrder(root);
}
 
template<class T>
void BinaryTree<T>::Post_Order() {
    PostOrder(root);
}
 
template<class T>
int BinaryTree<T>::TreeHeight() const {
    return Height(root);
}
 
template<class T>
int BinaryTree<T>::TreeNodeCount() const {
    return NodeCount(root);
}
 
template<class T>
void BinaryTree<T>::DestroyTree() {
    Destroy(root);
}
 
template<class T>
void BinaryTree<T>::PreOrder(BTNode<T> *r) {
    if (r != NULL) {
        cout << r->data << ' ';
        PreOrder(r->lChild);
        PreOrder(r->rChild);
    }
}
 
template<class T>
void BinaryTree<T>::InOrder(BTNode<T> *r) {
    if (r != NULL) {
        InOrder(r->lChild);
        cout << r->data << ' ';
        InOrder(r->rChild);
    }
}
 
template<class T>
void BinaryTree<T>::PostOrder(BTNode<T> *r) {
    if (r != NULL) {
        PostOrder(r->lChild);
        PostOrder(r->rChild);
        cout << r->data << ' ';
    }
}
 
template<class T>
int BinaryTree<T>::NodeCount(const BTNode<T> *r) const {
    if (r == NULL) {
        return 0;
    } else {
        return 1 + NodeCount(r->lChild) + NodeCount(r->rChild);
    }
}
 
template<class T>
int BinaryTree<T>::Height(const BTNode<T> *r) const {
    if (r == NULL) {
        return 0;
    } else {
        int lh, rh;
        lh = Height(r->lChild);
        rh = Height(r->rChild);
        return 1 + (lh > rh ? lh : rh);
    }
}
 
/**
 * Swap left, right subtree of all nodes.
 * @tparam T The type parameter.
 * @param r The root pointer.
 */
template<class T>
void Swap(BTNode<T> *r) {
    BTNode<T> *p;
    if (r) {
        p = r->lChild;
        r->lChild = r->rChild;
        r->rChild = p; // Swap left, right child.
        Swap(r->lChild); // Swap left, right subtree of all the nodes in left subtree.
        Swap(r->rChild); // Swap left, right subtree of all the nodes in right subtree.
    }
}
 
template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r) {
    if (r != NULL) {
        Destroy(r->lChild);
        Destroy(r->rChild);
        delete r;
        r = NULL;
    }
}
 
int main() {
    BTNode<char> *b, *c, *d, *e, *f, *g;
    BinaryTree<char> a;
    b = a.MakeTree('F', NULL, NULL);
    c = a.MakeTree('E', NULL, NULL);
    d = a.MakeTree('D', NULL, NULL);
    e = a.MakeTree('C', b, NULL);
    f = a.MakeTree('B', d, c);
    g = a.MakeTree('A', f, e);
 
    cout << "Pre Order: ";
    a.Pre_Order();
    cout << endl;
 
    cout << "In Order: ";
    a.In_Order();
    cout << endl;
 
    cout << "Post Order: ";
    a.Post_Order();
    cout << endl;
 
    cout << "Tree Height: ";
    cout << a.TreeHeight();
    cout << endl;
 
    cout << "The Count of Tree Nodes: ";
    cout << a.TreeNodeCount();
    cout << endl;
 
    cout << endl << "------ Swap left, right subtree of all nodes ------" << endl << endl;
    Swap(a.root);
 
    cout << "Pre Order: ";
    a.Pre_Order();
    cout << endl;
 
    cout << "In Order: ";
    a.In_Order();
    cout << endl;
 
    cout << "Post Order: ";
    a.Post_Order();
    cout << endl;
 
    cout << "Tree Height: ";
    cout << a.TreeHeight();
    cout << endl;
 
    cout << "The Count of Tree Nodes: ";
    cout << a.TreeNodeCount();
    cout << endl;
 
    return 0;
}
 
// Output:
/*
Pre Order: A B D E C F
In Order: D B E A F C
Post Order: D E B F C A
Tree Height: 3
The Count of Tree Nodes: 6
------ Swap left, right subtree of all nodes ------
Pre Order: A C F B E D
In Order: C F A E B D
Post Order: F C E D B A
Tree Height: 3
The Count of Tree Nodes: 6
*/