树

树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树：

树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

二分查找：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

提到树，就得先从二分查找这个有着$O(nlog(n))$复杂度的算法说起，因为二分查找本身就会生成一个二叉搜索树。

代码实现：

int BinarySearch(List Tbl, ElementType K)
{
    int l, r ,mid, NoFound = -1;

    l = 1;
    r = Tbl->Length;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (K < Tbl->Element[mid])
            r = mid - 1;
        else if (K > Tbl->Element[mid])
            l = mid + 1;
        else
            return mid;
    }
    return NoFound;
}

树的储存：

struct TreeNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

树的遍历：

• 先序

/*************************************************************************
先序遍历的非递归算法
按照根左右的顺序沿一定路径经过路径上所有的结点。
在二叉树中，先根后左再右。巧记：根左右。
    A
  /   \
  B    C
 / \  /
D   E F
结果：ABDECF
************************************************************************/
void PreOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    stack<BinTree> S;
    while (T || !S.empty())
    {
        while(T)
        {
            S.push(T);
            printf("%5d", T->Data);//
            T = T->Left;
        }
        if (!S.empty())
        {
        	T = S.top();
            S.pop();
            //区别在这里
            T = T->Right;
        }
    }
}

• 中序

/*************************************************************************
中序遍历(Inorder Traversal (LDR))
非递归实现：
在二叉树中，中序遍历首先遍历左子树，
然后访问根结点，最后遍历右子树。
        A
      /   \
      B    C
     / \  /
    D   E F
结果：DBEAFC
*************************************************************************/
void InOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    stack<BinTree> S;
    while (T || !S.empty())
    {
        while(T)
        {
            S.push(T);
            T = T->Left;
        }
        if (!S.empty())
        {
            T = S.top();
            S.pop();
            printf("%5d", T->Data);
            T = T->Right;
        }
    }
}

• 后序

/*************************************************************************
后序遍历的非递归算法
后序遍历（LRD）是二叉树遍历的一种，
也叫做后根遍历、后序周游，可记做左右根。
后序遍历有递归算法和非递归算法两种。
在二叉树中，先左后右再根，即首先遍历左子树，
然后遍历右子树，最后访问根结点。
        A
      /   \
      B    C
     / \  /
    D   E F
结果：DEBFCA
已知前序遍历和中序遍历，就能确定后序遍历。
 ************************************************************************/
void PostOrderTraversal(BinTree BT)
{
    if (BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%5d", BT->Data);
    }
}

• 层序(这个可以类比bfs)

/*************************************************************************
层序遍历(bfs?)的非递归算法
队列实现
************************************************************************/

void LevelOrderTraversal(BinTree BT)
{
    queue<BinTree> Q;
    BinTree T;
    Q.push(BT);
    while (!Q.empty())
    {
    	T = Q.front();
        Q.pop();
        printf("%d\n", T->Data);
        if (T->Left)
            Q.push(T->Left);
        if (T->Right)
            Q.push(T->Right);
    }
}

二叉搜索树：

概念：

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

代码实现：

/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;
int a[maxn];

typedef struct TreeNode *BinTree;
typedef BinTree Position;
typedef int ElementType;
struct TreeNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

class __BST
{
public:

    BinTree BST = NULL;
    /*************************************************************************
    查找递归
    ************************************************************************/
    Position Find(ElementType X, BinTree BST)
    {
        if (!BST)
            return NULL;
        if (X > BST->Data)
            return Find(X, BST->Right);
        else if (X < BST->Data)
            return Find(X, BST->Left);
        else
            return BST;
    }
    //迭代
    Position Find1(ElementType X, BinTree BST)
    {
        if (!BST)
            return NULL;
        if (X > BST->Data)
            return Find1(X, BST->Right);
        else if (X < BST->Data)
            return Find1(X, BST->Left);
        else
            return BST;
    }
    /*************************************************************************
    查找最小元素
     ************************************************************************/
    Position FindMin(BinTree BST)
    {
        if (!BST)
            return NULL;
        else if (!BST->Left)
            return BST;
        else
            return FindMin(BST->Left);
    }
    /*************************************************************************
    查找最大元素迭代
     ************************************************************************/
    Position FindMax(BinTree BST)
    {
        if (BST)
            while (BST->Right)
                BST = BST->Right;
        return BST;
    }

    /*************************************************************************
    插入和查找相似
    ************************************************************************/

    BinTree Insert(ElementType X, BinTree BST)
    {
        if (!BST)//空树生成
        {
            BST = (BinTree)malloc(sizeof(struct TreeNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;

        }
        else
        {
            if (X < BST->Data)
                BST->Left = Insert(X, BST->Left);
            else if (X > BST->Data)
                BST->Right = Insert(X, BST->Right);
        }
        return BST;
    }
    /*************************************************************************
    删除
    ************************************************************************/
    BinTree Delete(ElementType X, BinTree BST)
    {
        Position Tmp;

        if (!BST)
            puts("未找到");
        else if (X < BST->Data)
            BST->Left = Delete(X, BST->Left);
        else if (X > BST->Data)
            BST->Right = Delete(X, BST->Right);
        else if (BST->Left && BST->Right)
        {
            Tmp = FindMin(BST->Right);
            BST->Data = Tmp->Data;
            BST->Right = Delete(BST->Data, BST->Right);
        }
        else
        {
            Tmp = BST;
            if (!BST->Left)
                BST = BST->Right;
            else if (!BST->Right)
                BST = BST->Left;
            free(Tmp);
        }
        return BST;
    }
    /*************************************************************************
    中序遍历(Inorder Traversal (LDR))
    非递归实现：
    在二叉树中，中序遍历首先遍历左子树，
    然后访问根结点，最后遍历右子树。
            A
          /   \
          B    C
         / \  /
        D   E F
    结果：DBEAFC
    *************************************************************************/
    void InOrderTraversal(BinTree BT)
    {
        BinTree T = BT;
        stack<BinTree> S;
        while (T || !S.empty())
        {
            while(T)
            {
                S.push(T);
                T = T->Left;
            }
            if (!S.empty())
            {
                T = S.top();
                S.pop();
                printf("%5d", T->Data);
                T = T->Right;
            }
        }
    }
    /*************************************************************************
    先序遍历的非递归算法
    按照根左右的顺序沿一定路径经过路径上所有的结点。
    在二叉树中，先根后左再右。巧记：根左右。
        A
      /   \
      B    C
     / \  /
    D   E F
    结果：ABDECF
    ************************************************************************/
    void PreOrderTraversal(BinTree BT)
    {
        BinTree T = BT;
        stack<BinTree> S;
        while (T || !S.empty())
        {
            while(T)
            {
                S.push(T);
                printf("%5d", T->Data);//
                T = T->Left;
            }
            if (!S.empty())
            {
                T = S.top();
                S.pop();
                //区别在这里
                T = T->Right;
            }
        }
    }

    /*************************************************************************
    后序遍历的非递归算法
    后序遍历（LRD）是二叉树遍历的一种，
    也叫做后根遍历、后序周游，可记做左右根。
    后序遍历有递归算法和非递归算法两种。
    在二叉树中，先左后右再根，即首先遍历左子树，
    然后遍历右子树，最后访问根结点。
            A
          /   \
          B    C
         / \  /
        D   E F
    结果：DEBFCA
    已知前序遍历和中序遍历，就能确定后序遍历。
     ************************************************************************/
    void PostOrderTraversal(BinTree BT)
    {
        if (BT)
        {
            PostOrderTraversal(BT->Left);
            PostOrderTraversal(BT->Right);
            printf("%5d", BT->Data);
        }
    }
    /*************************************************************************
    层序遍历(bfs?)的非递归算法
    队列实现
    ************************************************************************/

    void LevelOrderTraversal(BinTree BT)
    {
        queue<BinTree> Q;
        BinTree T;
        Q.push(BT);
        while (!Q.empty())
        {
            T = Q.front();
            Q.pop();
            printf("%d\n", T->Data);
            if (T->Left)
                Q.push(T->Left);
            if (T->Right)
                Q.push(T->Right);
        }
    }
};

__BST B;

/*************************************************************************
主函数
 ************************************************************************/
int main()
{
    B.BST = B.Insert(5, B.BST);
    B.BST = B.Insert(10, B.BST);
    B.BST = B.Insert(2, B.BST);
    B.BST = B.Insert(1, B.BST);
    B.BST = B.Insert(3, B.BST);
    B.BST = B.Insert(6, B.BST);
    puts("\n中序遍历");
    B.InOrderTraversal(B.BST);
    puts("\n层序遍历");
    B.LevelOrderTraversal(B.BST);//
    puts("\n先序遍历");
    B.PreOrderTraversal(B.BST);
    puts("\n后序遍历");
    B.PostOrderTraversal(B.BST);
    return 0;
}
//中序遍历
//    1    2    3    5    6   10
//层序遍历
//5
//2
//10
//1
//3
//6
//
//先序遍历
//    5    2    1    3   10    6
//后序遍历
//    1    3    2    6   10    5

代码来源浙大慕课+自我优化

更多代码见github