树结构

树：层次关系
Tree ：n个节点构成的有限集合；
n=0时；称为空树；
对于非空树，具备特质有：

• 树中有一个根的特殊节点，用r解释；
• 子树；
  树与非树？
• 子树是不想交的；
• 除了根节点外，每个结点点有且仅有一个父节点；
• 一棵N个结点的树有N-1条边；

基本术语

1、 结点的度 结点的子树个数
2、树的度：树的所有结点最大的度数
3、叶结点：度为1的结点；
4、父节点：有子树的结点是其子树的根节点的父节点
5、子节点；
6、兄弟结点：同一父节点的各结点是彼此的兄弟结点；
7、路径和路径长度；
8、祖先结点；
9、子孙节点；
11、结点的层次；
12、树的深度；

实现方法

image.png

二叉树：度为2；
特殊二叉树

• 斜二叉树
• 完美二叉树/满二叉树
• 完全二叉树（不完整）

重要性质

二叉树第i层最大结点 2^（n-1）
深度为k的二叉树最大结点总数为2^n-1
非空二叉树 n0为叶节点的个数 n2为度为2的非叶节点个数 满足n0=n2+1；

常用的遍历方法：
先序--根，左子树，右子树
中序--左子树，根，右子树
后续--左子树，右子树，根
层次遍历--从上到下，从左到右

二叉树的存储结构

顺序存储结构

-完全二叉树
：从上到下、从左到右顺序存储n个节点的完全二叉树的节点父子关系。

• 父根节点 父节点[i/2]
• 左孩子节点 2i
• 右孩子节点2i+1
  一般二叉树也可以采取这种结构，但会造成空间浪费。

链表存储

template <typename DataType>
struct TreeNode
{
    DataType data; //存储的数据
    TreeNode *left; //指向左子树根节点
    TreeNode *right; //指向右子树根节点
    //TreeNode * parent; //指向父节点，如果需要的话
    TreeNode(DataType inData): data(inData), right(nullptr), left(nullptr) {}
};

image.png

遍历

//遍历
//先序遍历
template <typename DataType>
void Traverse(TreeNode<DataType> * inNode){
    if (inNode == nullptr){
    return;
    }
    //cout<<inNode->data<<endl;//如果在这里访问即为先序访问
    Traverse(inNode->left);
    //cout<<inNode->data<<endl;//如果在这里访问即为中序访问
    Traverse(inNode->right);
    //cout<<inNode->data<<endl;//如果在这里访问即为后序访问
    return；
}

二叉树的非递归算法

先序遍历的非递归：使用堆栈

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){
            //遇到节点先输出
            cout<<cycleNode->data<<endl;
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if（！inNode.empty()）{
            cycleNode = nodeStack.top();
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

中序遍历：先访问左子节点，在访问根节点，再访问右子节点。

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
    stack<TreeNode<DataType>*> nodeStack;
    TreeNode<DataType> *cycleNode = inNode;
    while(inNode != nullptr||!nodeStack.empty()){
        //不断访问某一节点的左子节点并压栈知道最左子节点
        while(cycleNode != nullptr){   
            nodeStack.push(cycleNode);
            cycleNode = cycleNode->left;
        }
        //此时所有的左子树都压入栈中
        //弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
        if（！inNode.empty()）{
            cycleNode = nodeStack.top();
            //在此处访问即为中序遍历，时机为压入右子节点之前
        //cout << cycleNode->data << endl; 
            cycleNode = cycleNode->right;
            nodeStack.pop();
        }
    }
}

由于辅助压栈，我们并没有将null压入栈中，如果发现左子节点为null则在保存右子节点地址后直接弹出该节点，并使用右子节点作为下一论访问起始节点，如果右子节点为null则表示该节点左右子树均遍历完毕，则继续弹出直至出现第一个右子树不为空的节点，重复递归。

压栈图中，在前序遍历时，只要遇到节点（压栈过程）就直接输出就可以保证根节点首先被输出，而中序遍历由于需要在左子树输出完毕后才能输出，因此只要保证在压栈返回时（出栈时）且准备遍历右子树时输出即可。

后序遍历 非递归实现

template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> *inNode){
        stack<TreeNode<DataType> *>nodeStack;
        TreeNode<DataType> *cycleNode = inNode;
        TreeNode<DataType> *hasNode = nullptr;
        while(inNode != nullptr || !nodeStack.empty()){
            //不断访问某一节点的左子节点并压栈直到最左子节点
            while(cycleNode != nullptr){
                nodeStack.push(cycleNode);
                cycleNode = cycleNode->left;
            }
            //此时所有的子节点都已经压入栈中。
            //弹出最后一个节点，访问该节点的右子节点并作为下一轮遍历根节点
            if(!nodeStack.empty()){
                cycleNode = nodeStack.top();
                //此时判别是否已经加载右子树
                //如果为空则和中序遍历一样
                if(cycleNode->right == nullptr){
                    hascycle = cycleNode;
                    cout<< cycleNode->data<<endl;
                    nodeStack.pop();
                }
                else if(hascycle == cycleNOde->right){
                    hascycle = cycleNode;
                    cout<<cycleNode->data<<endl;
                    nodeStack.pop();
                }
                cycleNode = nullptr;
                if(!nodeStack.empty() && ndoeStack.top->right!=nullptr)) {
                    cycleNode = nodeStack.top()->right;
                }
            }
        }
}

层序遍历

二叉树遍历的核心问题：二维结构的线性化

• 从节点访问其左、右儿子
• 需要一个存储结构保存暂时不访问的结点
• 存储结构：堆栈、队列

队列实现：遍历从根节点开始，首先将根节点入队，然后开始执行循环：结点出队，访问该结点，将左右儿子入队

void LevelOrderTraversal ( BinTree BT){
    Queue Q;BinTree T;
    //如果是空树直接返回
    if(!BT)
        return ;
    //创建并初始化队列Q
    Q = CreatQueue(Maxsize);
    AddQ(Q,BT);
    while( !IsEmptyQ(Q)){
        T = DeleteQ(Q);
        cout  <<T->data<<endl;
        if(T->left)   
            AddQ(Q,T->left);
        if(T->right)
            AddQ(Q,T->right)
    }
}

如果有两个遍历序列确定二叉树

必须要有中序遍历
如果已知先序和中序；

1. 根据先序遍历序列第一个节点确定根节点；
2. 根绝根节点在中序遍历序列中分割出左右两个子序列
3. 对左子树和右子树分别递归分为左子树和右子树

二叉查找树的定义与实现

静态查找：二分查找
动态查找：二叉搜索树；
也称为二叉排序树，或者二叉查找树；

• 分空左子树的所有键值小于其根节点的键值。
• 分空右子树的所有键值大于其根节点的键值。
• 左右子树都是二叉搜索树。

对于二叉树ADT，一般需要提供以下操作：

• 清空二叉查找树：MakeEmpty
• 查找某个节点：Find
• 删除某个节点：DeleteElement
• 查找最大值：FindMax
• 查找最小值：FindMin
• 插入一个节点：InsertElement
  二叉查找树的平均深度为O(log(N))，不过如果插入元素序列递增或者递减，二叉查找树将退化成单链表。

二叉查找树的实现

二叉树的基本结构定义：

template <typename DataType>
struct Node
{
    DataType data;
    Node *left;
    Node *right;
    Node(DataType inData): data(inData), left(nullptr), right(nullptr) {}
};

template <typename DataType>
class BinarySearchTree
{
public:
    BinarySearchTree(): root(nullptr) {}
    ~BinarySearchTree();
    void MakeEmpty(); //清空二叉查找树
    void MakeEmptyNon(); //非递归清空二叉树
    Node<DataType> * Find(DataType inElement); //查找某个元素
    Node<DataType> * FindNon(DataType inElement); //非递归查找
    void DeleteElement(DataType inElement); //删除一个节点
    Node<DataType> * FindMax(); //查找最大元素
    Node<DataType> * FindMaxNon(); //非递归查找最大元素
    Node<DataType> * FindMin(); //查找最小元素
    Node<DataType> * FindMinNon(); //非递归查找最小元素
    Node<DataType> * InsertElementNon(DataType inElement); //非递归插入一个元素
private:
    void MakeEmptyCore(Node<DataType> *inNode);
    Node<DataType> *FindCore(Node<DataType> *inNode, DataType inElement);
    //删除一个节点
    Node<DataType> * DeleteElementCore(Node<DataType> *inNode, DataType inElement);
    Node<DataType> *FindMaxCore(Node<DataType> *inNode);
    Node<DataType> *FindMinCore(Node<DataType> *inNode);
    Node<DataType> *root;
};

二叉查找树的基本数据成员为
递归清空核心函数：

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空核心函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return;
    }
    MakeEmptyCore(inNode->left);
    MakeEmptyCore(inNode->right);
    delete inNode;
}

递归清空入口函数，调用清空核心函数

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmpty()
{
    MakeEmptyCore(root); root = nullptr;
}

非递归清空函数，采用某种非递归遍历函数思想即可

template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyNon()
{
    stack<Node<DataType> *> nodeStack;
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr || !nodeStack.empty()) {
        while (cycleIter != nullptr) {
            nodeStack.push(cycleIter);
            cycleIter = cycleIter->left;
        }
        
        if (!nodeStack.empty()) {
            Node<DataType> * tmp = nodeStack.top();
            cycleIter = tmp->right;
            delete tmp; nodeStack.pop();
        }
    }
    root = nullptr;
}

递归查找某个元素

template <typename DataType>
Node<DataType> *BinarySearchTree<DataType>::FindCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    if (inNode->data == inElement) {
        return inNode;
    }
    else if (inNode->data > inElement){
        return FindCore(inNode->left, inElement);
    }
    else {
        return FindCore(inNode->right, inElement);
    }
    return nullptr;
}

非递归查找

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindNon(DataType inElement)
{
    Node<DataType> *cycleIter = root;
    while (cycleIter != nullptr) {
        if (cycleIter->data == inElement) {
            return cycleIter;
        }
        else if (cycleIter->data > inElement){
            cycleIter = cycleIter->left;
        }
        else {
            cycleIter = cycleIter->right;
        }
    }
    return nullptr;
}

递归删除节点函数核心函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}

递归查找最大元素核心函数

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxCore(Node<DataType> *inNode)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->right == nullptr) {
        return inNode;
    }
    else {
        return FindMaxCore(inNode->right);
    }
}

递归查找最大元素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMax()
{
    if (root == nullptr) {
        return nullptr;
    }
    return FindMaxCore(root);
}

非递归查找最大元素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxNon()
{
    if (root == nullptr) {
        return nullptr;
    }
    Node<DataType> *pre = root;
    Node<DataType> *cycleIter = pre->right;
    while (cycleIter != nullptr) {
        pre = cycleIter;
        cycleIter = pre->right;
    }
    return pre;
}

递归删除节点函数核心元素

template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
    if (inNode == nullptr) {
        return nullptr;
    }
    else if (inNode->data > inElement) {
        inNode->left = DeleteElementCore(inNode->left, inElement);
    }
    else if (inNode->data < inElement) {
        inNode->right = DeleteElementCore(inNode->right, inElement);
    }
    else {
        if (inNode->left != nullptr && inNode->right != nullptr) {
            Node<DataType> *tmp = FindMinCore(inNode->right);
            inNode->data = tmp->data;
            inNode->right = DeleteElementCore(inNode->right, inNode->data);
        }
        else {
            Node<DataType> *tmp = inNode;
            if (inNode->left == nullptr) {
                inNode = inNode->right;
            }
            else {
                inNode = inNode->left;
            }
            delete  tmp;
        }
    }
    return inNode;
}