2021 年秋天我再次作为一个刚踏进带学校园的人出现。然而还是要面临一样的东西，我也没什么基础可言，仰望各位大佬，自己一无所得。除了会给 VSCode 配一个 C++ 环境以外纯纯的黔驴技穷。想着去学校天天抄报告之前学点东西吧，于是下面的一系列笔记就这样诞生了。很简单，没啥东西，能满足 114514 本带学的考试及格，就是满足一下自己作为「正经人」写日记的感受而已，凑合看吧。

「re: 从零开始的带学数据结构①」几种基础的树的理解

二叉树的非递归遍历

深度优先搜索

先从递归遍历的方向去理解。

实际上递归操作本质上是栈的实现。函数调用的过程具有栈的形式，也就是先进后出。

中序遍历：每次在 pop 前后对元素进行操作。中序遍历会在第二次见到元素的时候进行操作。

//伪代码实现
Trav(节点)
{
	while(节点、栈非空)
	while(节点非空)
        //先序遍历：第一次见到就操作。
		节点压栈；
		左移；
	//这个时候已经走完了一条路径，于是
	栈顶元素赋值给这个节点，折返；
	//中序遍历：在 pop 之前对这个元素进行操作。
	栈 弹出栈顶元素；
	节点右移，探索右部路径；
}

vector<int>Trav(TreeNode *Node)
{
    vector<int> Result;
    stack<TreeNode*> S;
    while(!s.empty() || Node == NULL)
    {
        while(Node)
        {
            S.push(Node);
            Node = Node->left;
        }
        //在这里 Node 一定会移动到 nullptr。所以走到了尽头，要按照中序遍历的路线图一样先折返再右移。
        Node = S.top();
        S.pop();
        Result.push_back(Node->value);
        //即使接下来 Node 到达 nullptr 也无所谓。那就从栈顶再折返。
        Node = Node->right;
	}
    return Result;
}

对二叉搜索树相关操作的理解

对于二叉搜索树，满足性质：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉搜索树；

于是，可以二分地去进行查找，只要待定值大，就去右边；小就去左边。可以递归的实现为：

TreeNode *Find(T X, TreeNode* BSTNode)
    {
        //failed
        if(!BSTNode)
            return NULL;
        
        if(X > BSTNode->Data)
            return Find(X, BSTNode->Right);
        else if(X < BSTNode->Data)
            return Find(X, BSTNode->Left);
        else
            return BSTNode; //succ
    }

由上性质易知，最小的节点是最左侧的节点；反之亦然。

所以查找最大和最小的算法，可以藉由递归，不断地向左和向右来实现。

TreeNode *FindMin(TreeNode *BSTNode)
    {
        if(BSTNode)
            while(BSTNode->Left)
                BSTNode = BSTNode->Left;

        return BSTNode;
    }

    TreeNode *FindMax(TreeNode *BSTNode)
    {
        if(!BSTNode)
            return NULL;
        else if(!BSTNode->Right)
            return BSTNode;
        else
            return FindMax(BSTNode->Right);
    }

在整棵树上寻找位置插入，便可以利用上面的规律：

考察待插入节点值的大小，削减规模到在左 / 右子树上寻找位置插入。
在削减规模的过程中，通过递归的返回值，把插入节点以后的变化了的左子树再赋回原来的左子树上。
如果寻找的位置已经越出了树的内存地址（NULL），那么就新建一个节点。把它连接到上次的左右子树上面。这个时候，代表已经走到了树的叶节点的下一个位置，就可以在它后面插入了。代码实现如下：
新插入节点总是叶子节点。

TreeNode *BSTInsert(TreeNode *BSTHead, T Value)
{
    //过程 3. 一旦进入了 NULL，就可以通过 2 的返回机制来把新的 BST 插入。
	if(!BSTHead){	
        BSTHead = new TreeNode;
        BSTHead->Data = Value;
        BSTHead->Left = BSTHead->Right = NULL;
    }
    
    //过程 1.
    else{
        if(Value < BSTHead->Data)
            //过程 2. 树的更新。
        	BSTHead->Left = BSTInsert(BSTHead->Left, Value);
        else if(Value > BSTHead->Data)
        	BSTHead->Right = BSTInsert(BSTHead->Right, Value);
	}
    
    //过程 2. 返回值。返回的是一个节点类型。
    return BSTHead;
}

树的删除也是类似的道理。由二叉搜索树的性质易知，被删除节点的右子树的最小值没有左子树，可以直接删除。

先查找待删除结点的位置。削减规模。
找到待删除结点的右子树的最小值，把它赋给待删除结点的位置，节点删除完毕。
这个时候去清理冗余的、位于右子树最小值位置的节点。递归的进行这一步骤，它的节点数一定小于两个。
对于只有一个子树或者没有的树，可以直接把下面接上来。不需要进行 2、3 两个步骤。

TreeNode *BSTDelete(TreeNode *BST, T X)
    {
        TreeNode *TempNode = new TreeNode;

        if(!BST)//步骤 1
            return NULL;
        
        else if(X < BST->Data)
            BST->Left = BSTDelete(BST->Left, X);

        else if(X > BST->Data)
            BST->Right = BSTDelete(BST->Right, X);
        
        else    //找节点去删除
        {             
            if(BST->Left && BST->Right)
            {
                //被删除节点有左右两子树。步骤 2。
                TempNode = FindMin(BST->Right);
                //更改节点内容
                BST->Data = TempNode->Data;
                //右子树的最小值没有左子树。问题规模简单化为被删除节点没有两个子树的情况。
                //去右子树这里删除节点。把删除 data 之后的右子树赋回来。(步骤 3)
                BST->Right = BSTDelete(BST->Right, BST->Data);
            }

            else        //被删除节点只有一个或者无子树。步骤 4.
            { 
                TempNode = BST;

                if(!BST->Left)
                    BST = BST->Right;
                else if(!BST->Right)
                    BST = BST->Left;

                delete TempNode;
            }
        }

        return BST;
    }

堆的实现及其操作理解

这里的堆满足以下性质：

完全二叉树。每一个根节点都比两个子节点要大 / 小。
使用静态数组来构成堆。从 a[1] 开始逐个导入元素，完全二叉树一定满足： \[ ChildPos / 2 = ParentPos \]
从父节点逐渐向下的序列一定满足单调性。

于是，便可以这样实现插入节点：

Heap->Size++;
int i = Heap->Size;	//插在最后一位上。默认是最小位置。
while(Heap->Data[i/2] < Value)	//因为存在单调性，所以只要从这条路径不断向根节点层层比对，一旦某一结点满足顺序便可以退出循环。这个时候便把待插入的 Value 放在了正确位置上。
{
    Heap->Data[i] = Heap->Data[i/2];	//参考性质 2。
    i = i / 2;
}
Heap->Data[i] = Value;

对于删除节点，默认只会删除优先级 / 值最高的节点，也就是根节点。可以

把最末位的元素列出来，假设它可以放在头上。这一层暂定为 Parent。
比对根节点左右子树大小，选出更大的子树来。
如果最末位的元素已经比它大，就意味着不需要调整了。否则把子树的值赋给根节点本身。
将 Child 位置赋给 Parent。向下一层继续比对。
各层调整过后，最末尾元素归位。

可以理解成：最末位元素锚定的 Parent 位置元素。和更大的 Child 元素之间相互比较，更大的元素进入 Parent 位置，而更小的则通过步骤 4 保留在 Child 位置上。当这最末尾元素比左右子树都大或者不再有元素，便结束循环。

T Remove(HeapContainer *H)
    {
        typedef uint32_t Position;
        Position Parent, Child;

        if (H->Size == 0)
            return;
        
        T MaxItem = H->Data[1];
        T TempElement;

        TempElement = H->Data[H->Size]; //将树中最小节点列出来。
        H->Size--;

        for(Parent = 1; Parent * 2 <= H->Size; Parent = Child){
            //不断比较左右子树的大小。把 Child 变量指向最大的子树。
            //先默认左子树更大。
            Child = Parent * 2;
            //左 < 右，Child!= H->Size  意味着左子树就是最大元素。
            if( (Child!= H->Size) && (H->Data[Child] < H->Data[Child+1]) )
                Child++;
            //判别。如果比左右子树都大，那么已经不需要调整了。
            //（下面便会让临时节点，本应位于最小位置的节点赋值到 parent 节点上。）
            if(TempElement >= H->Data[Child])
                break;
            else
                H->Data[Parent] = H->Data[Child];
            //每轮循环结束后，赋值 Child 位置给 Parent。（第一次会赋值到根节点。）
        }
        H->Data[Parent] = TempElement;
        return MaxItem;
    }