二叉树

1、定义

binary tree的递归定义：根结点的子树仍然是一棵二叉树，到达空子树的时候递归结束。

2、性质

（1）第i层至多有2^(i-1)个结点

（2）深度为k的二叉树最少有k个结点，最多有2^k-1个结点

（3）对于任一棵非空二叉树，若其叶子结点的个数为N0，度为2的非叶子结点的个数为N2，则有N0=N2+1

（4）具有n个结点的完全二叉树的深度为int_up(log(2,n+1))

（5）

3、特殊二叉树

（1）满二叉树

所有的分支结点都存在左右子树，所有的叶子结点都在同一层。

（2）完全二叉树

对于一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全相同，则这颗树就是完全二叉树；满二叉树一定是一棵完全二叉树，反之不一定。

4、二叉树c++实现

（1）存储方式

使用顺序存储的空间利用率太低，一般采用的是链式存储的方式，称之为二叉链表；二叉树的结点类如下：

template <typename T>
struct BinTreeNode
{
    T data;
    BinTreeNode<T> *left,*right;
    BinTreeNode():left(NULL),right(NULL){}
    BinTreeNode(T x,BinTreeNode<T>* l = NULL ,BinTreeNode<T>* r = NULL):data(x),left(l),right(r){}
}

（2）二叉树的遍历

【1】前序遍历：根左右

//递归实现
void PreOrder(BinTreeNode<T>*& root)
{
    if(root)
    {
        cout << root->data << endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}
//非递归实现
//使用栈先进后出的存储特性来记录遍历时候的回退路径
//具体而言，为了保证是根左右的顺序，即先左子树后右子树，在进栈的时候先进右子树的结点，后进左子树的，这样出栈的时候刚好是左右的顺序
void PreOrder1(BinTreeNode<T>*& root)
{
    stack<BinTreeNode<T>*> s;
    BinTreeNode* temp = NULL;
    s.push(root);
    while(!s.empty())
    {
        temp = s.top();
        s.pop();
        cout << temp->data << endl;
        if(temp->right)
            s.push(temp->right);
        if(temp->left)
            s.push(temp->left);
    }
}

//非递归实现的第二种方式
void PreOrder2(BinTreeNode<T>*& root)
{
    BinTreeNode<T>* temp = root;
    stack<BinTreeNode<T>*> s;
    s.push(NULL);//初始push一个空指针进栈，这样到最后一个没有左右子树的叶子结点的时候，栈里只有一个NULL了，令指针root指向这个NULL就可以结束循环
    while(temp)
    {
        cout << temp->data << endl;
        if(temp->right)
            s.push(temp->right);//预留右子树指针在栈中
        if(temp->left)
            temp = temp->left;//进入左子树
        else//左子树为空
        {
            temp = s.top();
            s.pop();
        }
    }
}

【2】中序遍历：左根右

//递归实现
void InOrder(BinTreeNode<T>*& root)
{
    if(root)
    {
        InOrder(root->left);
        cout << root->data << endl;
        InOrder(root->right);
    }
}

//非递归实现
//同样使用栈来记录遍历过程中回退的路径
//如果某结点的右子树为空，就说明以这个节点为根的二叉树遍历完了，此时从栈中退出到更上层的结点并访问它
void InOrder1(BinTreeNode<T>*& root)
{
    if(!root)
        return;
    stack<BinTreeNode<T>*> s;
    s.push(root);
    while(!s.empty())
    {
        while(s.top()->left)//左子树依次入栈
        {
            s.push(s.top()->left);
        }
        while(!s.empty())
        {
            BinTreeNode<T>* cur = s.top();
            cout << cur->data << endl;
            s.pop();
            if(cur->right)
            {
                s.push(cur->right);
                break;
            }
        }
    }
}

【3】后序遍历：左右根

//后序遍历的递归实现
void PostOrder(BinTreeNode<T>*& root)
{
    if(root)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        cout << root->data << endl;
    }    
}
//非递归实现
void PostOrder1(BinTreeNode<T>*& root)
{
    if(!root) return;
    stack<BinTreeNode<T>*> s;
    s.push(root);
    BinTreeNode<T>* last = NULL;
    while(!s.empty())
    {
        while(s.top()->left)//左结点依次入栈，循环遍历到二叉树的最左结点处
            s.push(s.top()->left);
        while(!s.empty())
        {
            if(last == s.top()->right || s.top()->right == NULL)//上一次出栈的结点是当前栈顶结点的右节点，或者当前栈顶结点不存在右节点
            {
                cout << s.top()->data << endl;
                last = s.top();
                s.pop();
            }
            else if(s.top()->right)//当前栈顶结点存在右节点，那么右节点压栈
            {
                s.push(s.top()->right)
                break;
            }
        }
    }
}

【4】层序遍历

void levelOrder(BinTreeNode<T>*& root)
{
    queue<BinTreeNode<T>*> q;
    if(root)
        q.push(root);
    BinTreeNode<T>* node;
    while(!q.empty())
    {
        node = q.front();
        cout << node->data << endl;
        q.pop();
        if(node->left)
            q.push(node->left);
        if(node->right)
            q.push(node->right);
    }
}

（3）二叉树创建

【1】广义表

例如，使用广义表：A(B(D,E(G,)),C(,F))#建立的二叉树：

BinTreeNode<T>* CreatBinTree(string s)
{
    stack<BinTreeNode<T>*> s;
    BinTreeNode<T>* root = NULL , *p = NULL , *t = NULL;
    int k;
    for(int i = 0;i < s.length();++i)
    {
        switch(s[i])
        {
            case '(':
                s.push(p);
                k=1;
                break;
            case ')':
                s.pop();
                break;
            case ',':
                k = 2;
                break;
            default:
                p = new BinTreeNode<T>*(ch);
                if(root == NULL)
                    root = p;
                else if(k == 1)
                    t =  s.top();t->left = p;
                else
                    t = s.top();t->right = p;
        }
    }
    
}

5、线索二叉树

（1）定义

将结点结构进行扩容，如下：ltag和rtag用来指示lchild和rchild存放的是指向孩子结点的指针还是指向前驱结点和后继结点的线索。

（2）结点类

//结点结构
template<typename T>
struct threadNode
{
    int ltag,rtag;
    treadNode<T>* left,*right;
    T data;
    threadNode(T x):data(x),left(NULL),right(NULL),ltag(0),rtag(0){}
}

（3）二叉树线索化

//利用函数重载来实现中序遍历对创建好的普通二叉树进行线索化
void creatInThread()
{
    threadNode<T>* pre = NULL;
    if(root != NULL)
    {
        creatInThread(root,pre);
        pre->right = NULL;
        pre->rtag = 1;
    }
}

void creatInThread(threadNode<T>*& cur,threadNode<T>*& pre)
{
    if(!cur == NULL) return;
    creatInThread(cur->left , pre);//递归左子树的线索化
    if(!cur->left)
    {
        cur->left = pre;
        cur->ltag = 1;
    }
    if(pre != NULL && pre->right == NULL)
    {
        pre->right = cur;
        pre->rtag = 1;
    }
    pre = cur;
    creatInThread(cur->right , pre);//递归右子树的线索化
}

6、二叉搜索树（二叉查找树、二叉排序树，Binary Search Tree（BST））

（1）定义

（2）性质

【1】二叉搜索树是set和map的底层结构

【2】二叉搜索树用中序遍历输出的序列式升序排列的，如上图的二叉搜素树，用中序遍历输出的话：1,6,10,9，10,12,16,17,18,25

（3）查找操作

Node* Find(const K& val)
{
    Node* cur = _root;
    while(cur)
    {
        if(val == cur->_data)
            return cur;
        else if(val > cur->_data)
            cur = cur->right;
        else
            cur = cur->left;
    }
    return nullptr;
}