首页 数据结构（C++）
  1. 树
    1.1 树的抽象数据类型
  2. 二叉树
    2.1 一般树转化为二叉树
    2.2 二叉树还原为一般树
    2.3 森林转换为二叉树
    2.4 二叉树还原为森林
    2.5 二叉树的性质
    2.6 二叉树顺序存储结构
    2.7 二叉树链式存储结构
    2.8 二叉树的抽象数据类型
    2.9 二叉树结点类定义
    2.10 二叉树类定义
    2.11 前序遍历
    2.12 中序遍历
    2.13 后序遍历
    2.14 层次遍历
    2.15 销毁二叉树
    2.16 复制二叉树
    2.17 计算二叉树高度
    2.18 计算二叉树结点总数
    2.19 查找值为 x 的结点
    2.20 查找结点 t 的父结点
    2.21 从输入流创建二叉树
    2.22 左右子树交换
    2.23 计算二叉树叶子结点
    2.24 二叉树的生成
    2.25 顺序 --> 链式结构
    2.26 广义表 --> 二叉树
    2.27 二叉树 --> 广义表
    2.28 求二叉树深度
    2.29 根据前中序确定建立算法
  3. 线索二叉树
  4. 树和森林
    4.1 树的遍历
    4.2 森林的遍历
  5. 堆
    5.1 最小堆的类定义
    5.2 构造函数 (创建空堆)
    5.3 构造函数 (数组直接建堆)
    5.4 向下调整算法
    5.5 向上调整算法
    5.6 插入算法
    5.7 删除算法
    5.8 哈夫曼树

image-20251008124722393 image-20251008132404641 image-20251008132427388 image-20251008132438757 image-20251008132448546

# 一、树

# 1. 树的抽象数据类型

template<class T>
class Tree
{
    // 在类界面中的 position 是树中结点的地址
    // 在顺序存储方式下是下标型
    // 在链表存储方式下是指针型
public:
    Tree(); // 构造函数
    ~Tree();    // 析构函数
    BuildRoot(const T &value);  // 建立树的根结点
    position FirstChild(position p);    // 返回 p 的第一个子女结点
    position NextSibling(position p);   // 返回 p 下一兄弟地址；若无下一兄弟返回 0
    position Parent(position p);        // 返回 p 双亲结点地址；若 p 为根，返回 0
    T getData(position p);              // 返回结点 p 中存放的值
    bool InsertChild(position p,T &value);  // 在结点 p 下插入值为 value 的新子女，若插入失败，返回 false
    bool DeleteChild(position p,int i); // 删除结点 p 的第 i 个子女及其全部子孙结点，若删除失败，返回 false
    void DeleteSubTree(position t); // 删除以 t 为根结点的子树
    bool IsEmpty(); // 判树空否，若空则返回 true，否则返回 false
    void Traversal(void (*visit)(position p));  // 遍历以 p 为根的子树
};

# 二、二叉树


# 1. 一般树转化为二叉树

image-20251008132551362 image-20251008132615088 image-20251008132719821

# 2. 二叉树还原为一般树

image-20251008132734112 image-20251008133029427

# 3. 森林转换为二叉树

image-20251008133050349

# 4. 二叉树还原为森林

image-20251008133105014

# 5. 二叉树的性质

image-20251008133122288 image-20251008133134670 image-20251008133854883 image-20251008133905651

# 6. 二叉树顺序存储结构

image-20251008134011694 image-20251008134023209

# 7. 二叉树链式存储结构

image-20251008134048609 image-20251008134059751
// 结点结构
template<class T>
struct BinTreeNode
{
    T data;
    BinTreeNode *leftchild,*rightchild;
};

image-20251008140835819 image-20251008140823764

# 8. 二叉树的抽象数据类型

image-20251008140948517
template<class T>
class BinaryTree
{
public:
    BinaryTree(); // 构造函数
    BinaryTree(BinTreeNode<T> *lch,BinTreeNode<T> *rch,T item);// 构造函数，以 item 为根，lch 和 rch 为左、右子树，构造一棵二叉树
    int Height();   // 求树深度或高度
    int Size(); // 求树中结点个数
    bool IsEmpty(); // 判树空否，若空则返回 true，否则返回 false
    BinTreeNode<T> *Parent(BinTreeNode<T> *t);  // 求结点 t 的双亲
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *t);  // 求结点 t 的左子女
    BinTreeNode<T> *RightChild(BinTreeNode<T> *t);  // 求结点 t 的右子女
    bool Insert(T item);    // 在树中插入新元素
    bool Remove(T item);    // 在树中删除元素
    bool Find(T &item);     // 判断 item 是否在树中
    bool getData(T &item);  // 取结点数据
    BinTreeNode<T> *getRoot();  // 取根
    void Travel(void (*visit)(BinTreeNode<T> *t));  // 遍历，visit 是访问函数
};

# 9. 二叉树结点类定义

template<class T>
struct BinTreeNode  // 二叉树结点类定义
{
    T data; // 数据域
    BinTreeNode<T> *leftChild,*rightChild;  // 左子女、右子女链域
    BinTreeNode()   // 构造函数
    {
        leftChild=0;
        rightChild=0;
    }
    BinTreeNode(T x,BinTreeNode<T> *l=0,BinTreeNode<T> *r=0)    // 构造函数
    {
        data=x;
        leftChild=l;
        rightChild=r;
    }
};


# 10. 二叉树类定义

template<class T>
class BinaryTree    // 二叉树类定义
{
protected:
    BinTreeNode<T> *root;   // 二叉树的根指针
    T RefValue; // 数据输入停止标志
    void CreateBinTree(istream &in,BinTreeNode<T> *&subTree);  // 从文件读入建树
    bool Insert(BinTreeNode<T> *&subTree,T &x); // 插入
    void destroy(BinTreeNode<T> *subTree,T &x); // 销毁
    BinTreeNode<T> *Copy(BinTreeNode<T> *r);    // 复制
    int Height(BinTreeNode<T> *subTree);    // 返回树高度
    int Size(BinTreeNode<T> *subTree);  // 返回结点数
    BinTreeNode<T> *Parent(BinTreeNode<T> *subTree,BinTreeNode<T> *t);  // 返回父结点
    BinTreeNode<T> *Find(BinTreeNode<T> *subTree,T &x) const;   // 搜寻 x
    friend istream &operator>>(istream &in,BinaryTree<T> &Tree);    // 重载操作：输入
    friend ostream &operator<<(ostream &out,BinaryTree<T> &Tree);   // 重载操作：输出
public:
    BinaryTree() : root(0){} // 构造函数
    BinaryTree(T value) : RefValue(value),root(0){}// 构造函数
    BinaryTree(BinaryTree<T> &s);// 复制构造函数
    ~BinaryTree()  // 析构函数
    {
        destroy(root);
    }
    bool IsEmpty() // 判树空否
    {
        return (root==0);
    }
    int Height()   // 求树深度或高度
    {
        return Height(root);
    }
    int Size() // 求树中结点个数
    {
        return Size(root);
    }
    BinTreeNode<T> *Parent(BinTreeNode<T> *t)  // 求结点 t 的双亲
    {
        return (root==0 || root ==t) ? 0 : Parent(root,t);// 返回双亲结点
    }
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *t)  // 求结点 t 的左子女
    {
        return (t!=0) ? t->leftChild : 0;// 返回左子女
    }
    BinTreeNode<T> *RightChild(BinTreeNode<T> *t)  // 求结点 t 的右子女
    {
        return (t!=0) ? t->rightChild : 0;// 返回右子女
    }
    BinTreeNode<T> *getRoot()  // 取根
    {
        return root;
    }
};

# 11. 前序遍历
image-20251008144617044 image-20251008150110240
# 递归算法
template<class T>
void BinaryTree<T>::preOrder(BinTreeNode<T> *subTree,void (*visit)(BinTreeNode<T> *p))// 前序遍历
{
    if(subTree!=0)// 二叉树非空
    {
        visit(subTree); // 对根结点进行访问
        preOrder(subTree->leftChild,visit); // 对左子树进行遍历
        preOrder(subTree->rightchild,visit); // 对右子树进行遍历
    }
}

# 非递归算法
image-20251008150604879
void BinaryTree<T>::preOrder(void (*visit)(BinTreeNode<T> *p))// 前序遍历非递归
{
    stack<BinTreeNode<T> *> s;  // 定义栈对象，存储二叉树节点指针
    BinTreeNode<T> *t = root;   // 定义指针 t 并初始化为根节点
    // 栈非空或当前节点非空时循环
    while (!s.empty() || t != nullptr) 
    {
        // 遍历左子树，直到最左节点
        while (t != nullptr) 
        {
            visit(t);           // 访问当前节点
            s.push(t);          // 当前节点入栈
            t = t->leftChild;   // 移动到左子节点
        }
        // 处理右子树
        if (!s.empty()) 
        {
            t = s.top();        // 获取栈顶节点
            s.pop();            // 栈顶节点出栈
            t = t->rightChild;  // 移动到右子节点
        }
    }
}


# 12. 中序遍历
image-20251008151350032
# 递归算法
template<class T>
void BinaryTree<T>::inOrder(BinTreeNode<T> *subTree,void (*visit)(BinTreeNode<T> *p))// 中序遍历
{
    if(subTree!=0)// 二叉树非空
    {
        inOrder(subTree->leftchild,visit); // 对左子树进行遍历
        visit(subTree); // 对根结点进行访问
        inOrder(subTree->rightchild,visit); // 对右子树进行遍历
    }
}

# 非递归算法
image-20251008151403253
void BinaryTree<T>::inOrder(void (*visit)(BinTreeNode<T> *p))// 中序遍历非递归
{
    stack<BinTreeNode<T> *> s;  // 定义栈对象，存储二叉树节点指针
    BinTreeNode<T> *t = root;   // 定义指针 t 并初始化为根节点
    // 栈非空或当前节点非空时循环
    while (!s.empty() || t != nullptr) 
    {
        // 遍历左子树，将所有左节点入栈
        while (t != nullptr) 
        {
            s.push(t);          // 当前节点入栈
            t = t->leftChild;   // 移动到左子节点
        }
        // 处理栈顶节点和右子树
        if (!s.empty()) 
        {
            t = s.top();        // 获取栈顶节点
            s.pop();            // 栈顶节点出栈
            visit(t);           // 访问当前节点（中序遍历在此访问）
            t = t->rightChild;  // 移动到右子节点
        }
    }
}

# 13. 后序遍历
image-20251008151550792
# 递归算法
template<class T>
void BinaryTree<T>::PostOrder(BinTreeNode<T> *subTree,void (*visit)(BinTreeNode<T> *p))// 后序遍历
{
    if(subTree!=0)// 二叉树非空
    {
        PostOrder(subTree->leftChild,visit); // 对左子树进行遍历
        PostOrder(subTree->rightchild,visit); // 对右子树进行遍历
        visit(subTree); // 对根结点进行访问
    }
}

# 非递归算法
image-20251008151609001 image-20251008151725437
第一次进栈（ flag=0 ）：说明还没访问右子树；
第二次进栈（ flag=1 ）：说明左右子树都访问完了，该访问根。
void BinaryTree<T>::PostOrder(void (*visit)(BinTreeNode<T> *p))// 后序遍历非递归
{
    stack<BinTreeNode<T> *> s1;  // 存储节点的栈
    stack<int> s2;               // 存储节点进栈标志的栈（0 表示第一次进栈，1 表示第二次进栈）
    BinTreeNode<T> *t = root;    // 定义当前节点指针并初始化为根节点
    int flag;                    // 用于接收栈 s2 弹出的标志值
    // 栈非空或当前节点非空时循环
    while (!s1.empty() || t != nullptr) 
    {
        // 第一步：遍历左子树，所有节点第一次进栈（flag=0）
        while (t != nullptr) 
        {
            s1.push(t);          // 节点进栈
            s2.push(0);          // 标记为第一次进栈
            t = t->leftChild;    // 移动到左子节点
        }
        // 第二步：处理栈顶节点
        if (!s1.empty()) 
        {
            t = s1.top();        // 获取栈顶节点
            s1.pop();            // 节点出栈
            flag = s2.top();     // 获取对应标志
            s2.pop();            // 标志出栈
            if (flag == 1)       // 第二次出栈：左右子树已处理完，可访问当前节点
            {
                visit(t);        // 访问节点
                t = nullptr;     // 重置当前节点，准备处理下一个栈顶元素
            }
            else                 // 第一次出栈：需先处理右子树，节点第二次进栈（flag=1）
            {
                s1.push(t);      // 节点再次进栈
                s2.push(1);      // 标记为第二次进栈
                t = t->rightChild; // 移动到右子节点
            }
        }
    }
}

# 14. 层次遍历
// 层次遍历非递归
template<class T>
void BinaryTree<T>::levelOrder(void (*visit)(BinTreeNode<T> *p))
{
    if(root==nullptr)// 空树直接返回
    {
        return;
    }
    queue<BinTreeNode<T> *> q;// 用于存储结点的队列
    BinTreeNode<T> *current=nullptr;// 当前处理的结点
    
    q.push(root);// 根结点入队
    
    // 队列非空时循环
    while(!q.empty())
    {
        // 出队一个结点
        current=q.front();
        q.pop();// 移除队列第 1 个结点
        
        // 访问当前结点
        visit(current);
        
        // 如果左子结点存在，入队
        if(current->leftChild != nullptr)
        {
            q.push(current->leftChild);
        }
        
        // 如果右子结点存在，入队
        if(current->rightChild != nullptr)
        {
            q.push(current->rightChild);
        }
    }
}


# 15. 销毁二叉树
// 销毁二叉树（递归实现）
void destroy(BinTreeNode<T> *subTree)
{
    if (subTree != nullptr)  // 如果当前结点不为空
    {
        destroy(subTree->leftChild);   // 先销毁左子树
        destroy(subTree->rightChild);  // 再销毁右子树
        delete subTree;                // 最后删除当前结点
    }
}

# 16. 复制二叉树
// 复制二叉树（递归实现）
BinTreeNode<T> *Copy(BinTreeNode<T> *r)
{
    if (r == nullptr)  // 如果源树为空，返回空
        return nullptr;
    // 创建新结点，复制数据
    BinTreeNode<T> *p = new BinTreeNode<T>(r->data);
    p->leftChild = Copy(r->leftChild);   // 递归复制左子树
    p->rightChild = Copy(r->rightChild); // 递归复制右子树
    return p;  // 返回复制后的结点
}

# 17. 计算二叉树高度
// 计算二叉树高度（递归实现）
int Height(BinTreeNode<T> *subTree)
{
	if (subTree == nullptr)  // 空树高度为 0
		return 0;
	int hL = Height(subTree->leftChild);  // 计算左子树高度
	int hR = Height(subTree->rightChild); // 计算右子树高度
	// 树的高度 = 左右子树最大高度 + 1（当前结点）
	return (hL > hR ? hL : hR) + 1;
}

# 18. 计算二叉树结点总数
// 计算二叉树结点总数（递归实现）
int Size(BinTreeNode<T> *subTree)
{
    if (subTree == nullptr)  // 空树结点数为 0
        return 0;
    // 结点总数 = 1（当前结点） + 左子树结点数 + 右子树结点数
    return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
}

# 19. 查找值为 x 的结点
// 查找值为 x 的结点（递归实现）
BinTreeNode<T> *Find(BinTreeNode<T> *subTree, T &x) const
{
    if (subTree == nullptr)  // 空树中无此结点
        return nullptr;
    if (subTree->data == x)  // 当前结点就是要找的结点
        return subTree;
    // 先在左子树中查找
    BinTreeNode<T> *p = Find(subTree->leftChild, x);
    if (p != nullptr)  // 左子树中找到
        return p;
    // 左子树中未找到，在右子树中查找
    return Find(subTree->rightChild, x);
}

# 20. 查找结点 t 的父结点
// 查找结点 t 的父结点（递归实现）
BinTreeNode<T> *Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *t)
{
    // 如果当前子树为空，或为叶子结点，没有子结点，返回空
    if (subTree == nullptr || (subTree->leftChild == nullptr && subTree->rightChild == nullptr))
        return nullptr;
    // 如果当前结点的左孩子或右孩子是 t，则当前结点是 t 的父结点
    if (subTree->leftChild == t || subTree->rightChild == t)
        return subTree;
    // 先在左子树中查找
    BinTreeNode<T> *p = Parent(subTree->leftChild, t);
    if (p != nullptr)  // 左子树中找到
        return p;
    // 左子树中未找到，在右子树中查找
    return Parent(subTree->rightChild, t);
}

# 21. 从输入流创建二叉树
// 从输入流创建二叉树（递归实现）
// 参数：in - 输入流，subTree - 当前子树根节点的引用
void CreateBinTree(istream &in, BinTreeNode<T> *&subTree)
{
    T item;             // 存储读取到的数据
    if (!(in >> item))  // 读取数据失败（如到达文件末尾）
        return;
    if (item == RefValue)  // 如果读取到的是标记空结点的值
    {
        subTree = nullptr;  // 当前子树为空
    }
    else  // 否则创建新结点并递归构建左右子树
    {
        subTree = new BinTreeNode<T>(item);  // 创建新结点
        CreateBinTree(in, subTree->leftChild);  // 递归构建左子树
        CreateBinTree(in, subTree->rightChild); // 递归构建右子树
    }
}
// 重载输入运算符，用于从输入流创建二叉树
friend istream &operator>>(istream &in, BinaryTree<T> &Tree)
{
    Tree.destroy(Tree.root);  // 先销毁原有树结构
    Tree.CreateBinTree(in, Tree.root);  // 从输入流创建新树
    return in;
}
// 重载输出运算符，用于先序遍历输出二叉树
friend ostream &operator<<(ostream &out, BinaryTree<T> &Tree)
{
    Tree.PreOrderPrint(Tree.root, out);  // 先序遍历输出
    return out;
}

# 22. 左右子树交换
void Exchange(BinTreeNode<T> *t)
{
    if(t!=0)// 二叉树非空
    {
        BinTreeNode<T> *x=t->leftChild;
        t->leftChild=t->rightchild;
        t->rightchild=x;
        Exchange(t->leftChild);// 对左子树进行遍历
        Exchange(t->rightchild);// 对右子树进行遍历
    }
}

# 23. 计算二叉树叶子结点
# 使用全局变量
int counter=0;// 全局变量
void Leaves(BinTreeNode<T> *t)// 二叉树的叶子总数
{
    if(t!=0)// 二叉树非空
    {
        if(t->leftchild==0 && t->rightchild==0)
        {
            counter++;
        }
        Leaves(t->leftchild);// 对左子树进行统计
        Leaves(t->rightchild);// 对右子树进行统计
    }
}

# 用引用参数传递计数变量
// 把计数器 counter 作为引用参数传进函数。
// 每次递归时，所有层都共享同一个 counter。
// 不需要全局变量，避免副作用。
int n=0;
void Leaves(BinTreeNode<T> *t,int &counter)
{
    if(t!=0)// 二叉树非空
    {
        if(t->leftchild==0 && t->rightchild==0)
        {
            counter++;
            Leaves(t->leftchild,counter);// 对左子树进行统计
            Leaves(t->rightchild,counter);// 对右子树进行统计
        }
    }
}

# 返回值递归累加
int Leaves(BinTreeNode<T> *t)
{
    if(t!=0)// 二叉树非空
    {
        if(t->leftchild==0 && t->rightchild==0)
        {
            return 1;
        }
        else
        {
            return Leaves(t->leftchild)+Leaves(t->rightchild);
        }
    }
}

# 24. 二叉树的生成
image-20251021232326202
# 前序建立算法
template<class T>
BinTreeNode<T> *BinaryTree<T>::CreateBTree()// 前序建立算法
{
    char ch;
    BinTreeNode<T> *current;
    cin >>ch;
    if(ch=='.')// 输入的是否为 '.'
    {
        return 0;// 建立空树
    }
    else//else 可省略
    {
        current=new BinTreeNode<T>;// 分配结点空间
        current->data=ch;// 填入结点值
        current->leftchild=CraeteBTree();// 建立左子树
        current->rightchild=CreateBTree();// 建立右子树
        return current;
    }
}

# 中序建立算法
template<class T>
BinTreeNode<T> *BinaryTree<T>::CreateBTree()// 中序建立算法
{
    char ch;
    BinTreeNode<T> *q,*current;
    cin >>ch;
    if(ch=='.')// 输入的是否为符号 '.'
    {
        return 0;// 建立空树
    }
    else
    {
        q=CreateBTree();// 建立左子树
        current=new BinTreeNode<T>;// 分配结点空间
        current->data=ch;// 填入结点值
        current->leftchild=q;// 建立左子树
        current->rightchild=CreateBTree();// 建立右子树
        return current;
    }
}

# 后序建立算法
template<class T>
BinTreeNode<T> *BinaryTree<T>::CreateBTree()// 后序建立算法
{
    char ch;
    BinTreeNode<T> *tl,*tr,*current;
    cin >>ch;
    if(ch=='.')// 输入的是否为符号 '.'
    {
        return 0;// 建立空树
    }
    else
    {
        tl=CreateBTree();// 建立左子树
        tr=CreateBTree();// 建立右子树
        current=new BinTreeNode<T>;// 分配结点空间
        current->data=ch;// 填入结点值
        current->leftchild=tl;
        current->rightchild=tr;
        return current;
    }
}


# 25. 顺序 --> 链式结构
image-20251022000835716
//k 为当前要建立的结点在数组中的下标
BinTreeNode<T> *BinaryTree<T>::Change(int S[],int n,int k)// 顺序 --> 链式结构
{
    BinTreeNode<T> *current;
    if(k>n)// 结点不存在
    {
        return 0;// 建立空树
    }
    else
    {
        current=new BinTreeNode<T>;// 分配结点空间
        current->data=S[k];// 填入结点值
        current->leftchild=Change(S,n,2*k);// 建立左子树
        current->rightchild=Change(S,n,2*k+1);// 建立右子树
        return current;
    }
}


# 26. 广义表 --> 二叉树
image-20251022195312902
template<class T>
void BinaryTree<T>::Create2()
{
    stack<BinTreeNode<T> *> s;  // C++ STL stack
    int k=0;  // 记录当前要插入的是左孩子 (1) 还是右孩子 (2)
    char ch;
    BinTreeNode<T> *p = nullptr, *t = nullptr;  // 初始化指针，避免野指针
    root = nullptr;  // 替换 0 为 nullptr，指针语义更清晰
    cin >> ch;  // 读入第一个字符
    while (ch != '.')  // 以 '.' 作为输入结束标志
    {
        switch(ch)
        {
            case '(':
                s.push(p);
                k = 1;      // 左孩子准备来了
                break;
            case ',':
                k = 2;      // 右孩子准备来了
                break;
            
            case ')':
                t = s.top();
                s.pop();
                break;
            
            default:
                p = new BinTreeNode<T>;
                p->data = ch;  // 是结点值就生成节点
                p->leftchild = p->rightchild = nullptr;  // 初始化左右孩子为空
                if (root == nullptr)
                {
                    root = p;  // 如果是第一个结点，则为根
                }
                else
                {
                    if (k == 1)  // 作为左孩子
                    {
                        t = s.top();
                        t->leftchild = p;  // 作为左孩子插入
                    }
                    else  //k==2，作为右孩子
                    {
                        t = s.top();
                        t->rightchild = p;  // 作为右孩子插入
                    }
                }
        }
        cin >> ch;  // 继续读入下一个字符
    }
}


# 27. 二叉树 --> 广义表
template<class T>
void BinaryTree<T>::Print()// 二叉树转广义表
{
    if(t!=0)
    {
        cout <<t->data;// 先输入当前结点值
        if(t->leftchild!=0)// 有无孩子
        {
            cout <<'(';// 有孩子就先输出
            Print(t->leftchild);// 输出左子树
            if(t->rightchild!=0)// 有无右子树
            {
                cout <<',';// 有右子树才输出
                Print(t->rightchild);// 输出右子树
            }
            cout <<')';// 输出括号)
        }
    }
}
//AI 修正
template<class T>
void BinaryTree<T>::Print(BinTreeNode<T> *t) // 补充参数 t：当前要打印的子树根节点
{
    if (t != nullptr)  // 1. 替换 0 为 nullptr，指针判空更规范
    {
        cout << t->data;  // 先输出当前结点值（广义表的根节点）
        if (t->leftchild != nullptr)  // 有左 / 右孩子（只要有孩子就需要括号）
        {
            cout << '(';  // 左括号，包裹子节点
            Print(t->leftchild);  // 递归打印左子树
            if (t->rightchild != nullptr)  // 有右子树才输出逗号分隔
            {
                cout << ',';  // 逗号分隔左右子树
                Print(t->rightchild);  // 递归打印右子树
            }
            cout << ')';  // 右括号，闭合子节点
        }
    }
}
// 可选：提供无参重载版本，直接从根节点开始打印（更易用）
template<class T>
void BinaryTree<T>::Print()
{
    Print(root);  // 调用带参版本，传入整棵树的根节点 root
    cout << endl; // 打印结束后换行，格式更整洁
}


# 28. 求二叉树深度
image-20251022201032539
int BinaryTree<T>::Depth()//public 成员函数
{
    return Depth(root);
}
int BinaryTree<T>::Depth(BinTreeNode<T> *t)//private 成员函数
{
    int LeftDepth,RightDepth;
    if(t==0)
    {
        return 0;// 二叉树为空，深度为 0
    }
    else
    {
        LeftDepth=Depth(t->leftChild);// 求左子树的深度
        RightDepth=Depth(t->rightchild);// 求右子树深度
        if(LeftDepth>RightDepth)// 改变当前结点的深度
        {
            return LeftDepth+1;
        }
        else
        {
            return RightDepth+1;
        }
    }
}

# 29. 根据前中序确定建立算法
image-20251022201111886 image-20251022201124114
//stra 先序遍历序列   starta 起始下标
//strb 中序遍历序列   startb 起始下标
//lena 当前子树的结点数量
template<class T>
BinTreeNode<T> *CreateBTree(char *stra,int starta,char *strb,int startb,int lena)
{
    for(int i=0;i<lena;++i)
    {
        if(stra[starta]==strb[startb+i])// 寻找根结点
        {
            BinTreeNode<T> *p=new BinTreeNode<T>;
            p->data=stra[starta];
            p->leftChild=CreateBTree(stra,starta+1,strb,startb,i);
            p->rightchild=CreateBTree(stra,starta+i+1,startb+i+1,lena-i-1);
            return p;
        }
    }
    return 0;
}


# 三、线索二叉树
image-20251022205148082
image-20251022205156766
image-20251022205209261
image-20251022205225897
image-20251022205239670
image-20251022205511042
当某个结点的左指针本来是空时，把它指向这个结点的 中序前驱；
当某个结点的右指针本来是空时，把它指向这个结点的 中序后继。


# 四、树和森林
# 1. 树的遍历

image-20251022212819531 image-20251022213027085
# 2. 森林的遍历
image-20251022213047210 image-20251022213057519 image-20251022213139725
# 五、堆
image-20251022213434206
如果没有特别说明，默认是小根堆

# 1. 最小堆的类定义
image-20251022235806633 image-20251022235817540
#define DefaultSize 10
template<class T>
class MinHeap// 最小堆的类定义
{
    T *heap;// 指向存放堆元素的数组
    int CurrentSize;// 当前堆中元素个数
    int MaxHeapSize;// 堆的最大容量
public:
    MinHeap(int sz=DefaultSize);// 构造函数初始化堆
    MinHeap(T arr[],int n);
    ~MinHeap()// 析构函数
    {
        delete []heap;
    }
    const MinHeap<T> &operator=(const MinHeap &R);
    bool Insert(const T &x);
    bool IsEmpty() const
    {
        return CurrentSize==0;
    }
    bool IsFull() const
    {
        return CurrentSize==MaxHeapSize;
    }
    void MakeEmpty()
    {
        CurrentSize=0;
    }
private:
    void siftDown(int start,int m);// 向下调整
    void siftUp(int start);// 向上调整
};

# 2. 构造函数 (创建空堆)
初始化生成空堆
template<class T>
MinHeap<T>::MinHeap(int sz)// 初始化操作 生成空堆
{
    // 根据给定大小 maxSize 建立堆对象
    MaxHeapSize=(sz>DefaultSize) ? sz : DefaultSize;// 确定堆大小
    heap=new T[MaxHeapSize];// 创建堆空间
    CurrentSize=0;// 初始化
}

# 3. 构造函数 (数组直接建堆)
初始化一个非空最小堆
template<class T>
MinHeap<T>::MinHeap(T arr[],int n)// 初始化一个非空最小堆
{
    // 把最小堆初始化为数组
    MaxHeapSize=(DefaultSize<n) ? n : DefaultSize;
    heap=new T[MaxHeapSize];
    for(int i=0;i<n;++i)// 把原数组元素复制到堆数组里
    {
        heap[i]=arr[i];// 数组传送
    }
    CurrentSize=n;// 当前堆大小
    // 若父节点在 i，左右孩子分别在 2i+1 和 2i+2
    // 则叶子从 n/2 到 n-1
    int currentPos=(CurrentSize-2)/2;// 最后一个非叶子结点
    while(currentPos>=0)// 从最后一个非叶节点开始，对每个节点执行 siftDown，把它下沉到正确位置，一直调整到根节点
    {
        // 从下到上逐步扩大，形成堆
        siftDown(currentPos,CurrentSize-1);
        // 从 currentPos 开始，到 CurrentSize 为止，调整
        currentPos--;
    }
}


# 4. 向下调整算法
//start 要开始下滤的结点下标
//m     堆的最后一个元素下标
// 若一个节点有父节点，其父节点的索引 = (i-1) // 2（// 表示整数除法）
template<class T>
void MinHeap<T>::siftDown(int start,int m)// 向下调整
{
    int i=start;
    int j=2*i+1;//j 是 i 的左子女
    T temp=heap[i];
    while(j<=m)// 当左孩子下标 j 没有越界时，说明 i 还有子节点，继续下滤。
    {
        if(j<m && heap[j]>heap[j+1])//j<m 就表示有右孩子，且右孩子比左孩子小
        {
            j++;// 如果右孩子存在且比左孩子小，则 j 指向右孩子
        }
        if(temp<=heap[j])// 如果父节点比孩子还小，堆序正确，无需再下移
        {
            break;
        }
        else
        {
            heap[i]=heap[j];// 把较小的孩子上移，父结点一路下滑
            i=j;    // 向下继续检查下一层
            j=2*j+1;// 往下走
        }
    }
    heap[i]=temp;
}

# 5. 向上调整算法
template<class T>
void MinHeap<T>::siftUp(int start)// 向上调整算法
{
    // 从 start 开始，向上直到 0，调整堆
    int j=start;
    int i=(j-1)/2;//i 是 j 的双亲
    T temp=heap[j];// 暂存该结点值，用于最后放置正确位置
    while(j>0)// 只要没到根结点，就继续比较
    {
        if(heap[i]<=temp)// 父结点小于当前结点，满足堆序，不需上移
        {
            break;
        }
        else// 否则
        {
            heap[j]=heap[i];// 把父结点下移
            j=i;
            i=(i-1)/2;// 往上走
        }
    }
    heap[j]=temp;// 找到正确位置，填入结点值
}

# 6. 插入算法
template<class T>
bool MinHeap<T>::Insert(const T &x)// 插入算法
{
    if(CurrentSize==MaxHeapSize)// 堆满
    {
        cout <<"堆已满" <<endl;
        return 0;
    }
    heap[CurrentSize]=x;// 插在表尾
    siftUp(CurrentSize);// 向上调整为堆
    CurrentSize++;// 堆元素 + 1
    return 1;
}


# 7. 删除算法
template<class T>
int MinHeap<T>::RemoveMin(T &x)// 删除算法
{
    if(!CurrentSize)
    {
        cout <<"堆已空" <<endl;
        return 0;
    }
    x=heap[0];// 最小元素出队列
    heap[0]=heap[CurrentSize-1];
    CurrentSize--;
    siftDown(0,CurrentSize-1);// 从 0 号位置开始自顶向下调整为堆
    return 1;
}

# 8. 哈夫曼树
image-20251120093235085
#include<iostream>
using namespace std;
#define DefaultSize 10
template<class T>
class MinHeap// 最小堆的类定义
{
    T *heap;// 指向存放堆元素的数组
    int CurrentSize;// 当前堆中元素个数
    int MaxHeapSize;// 堆的最大容量
public:
    MinHeap(int sz=DefaultSize);// 构造函数初始化堆
    MinHeap(T arr[],int n);
    ~MinHeap()// 析构函数
    {
        delete []heap;
    }
    const MinHeap<T> &operator=(const MinHeap &R);
    bool Insert(const T &x);
    bool IsEmpty() const
    {
        return CurrentSize==0;
    }
    bool IsFull() const
    {
        return CurrentSize==MaxHeapSize;
    }
    void MakeEmpty()
    {
        CurrentSize=0;
    }
    int RemoveMin(T &x);
private:
    void siftDown(int start,int m);// 向下调整
    void siftUp(int start);// 向上调整
};
template<class T>
MinHeap<T>::MinHeap(int sz)// 初始化操作 生成空堆
{
    MaxHeapSize=(sz>DefaultSize) ? sz : DefaultSize;// 确定堆大小
    heap=new T[MaxHeapSize];// 创建堆空间
    CurrentSize=0;// 初始化
}
template<class T>
void MinHeap<T>::siftDown(int start,int m)// 向下调整
{
    int i=start;
    int j=2*i+1;
    T temp=heap[i];
    while(j<=m)
    {
        if(j<m && heap[j]->data > heap[j+1]->data)
        {
            j++;
        }
        if(temp->data <= heap[j]->data)
        {
            break;
        }
        else
        {
            heap[i]=heap[j];
            i=j;
            j=2*j+1;
        }
    }
    heap[i]=temp;
}
template<class T>
MinHeap<T>::MinHeap(T arr[],int n)// 初始化一个非空最小堆
{
    MaxHeapSize=(DefaultSize<n) ? n : DefaultSize;
    heap=new T[MaxHeapSize];
    for(int i=0;i<n;++i)
    {
        heap[i]=arr[i];
    }
    CurrentSize=n;
    int currentPos=(CurrentSize-2)/2;
    while(currentPos>=0)
    {
        siftDown(currentPos,CurrentSize-1);
        currentPos--;
    }
}
template<class T>
void MinHeap<T>::siftUp(int start)// 向上调整算法
{
    int j=start;
    int i=(j-1)/2;
    T temp=heap[j];
    while(j>0)
    {
        if(heap[i]->data <= temp->data)
        {
            break;
        }
        else
        {
            heap[j]=heap[i];
            j=i;
            i=(i-1)/2;
        }
    }
    heap[j]=temp;
}
template<class T>
bool MinHeap<T>::Insert(const T &x)// 插入算法
{
    if(CurrentSize==MaxHeapSize)
    {
        cout <<"堆已满" <<endl;
        return 0;
    }
    heap[CurrentSize]=x;
    siftUp(CurrentSize);
    CurrentSize++;
    return 1;
}
template<class T>
int MinHeap<T>::RemoveMin(T &x)// 删除算法
{
    if(!CurrentSize)
    {
        cout <<"堆已空" <<endl;
        return 0;
    }
    x=heap[0];
    heap[0]=heap[CurrentSize-1];
    CurrentSize--;
    siftDown(0,CurrentSize-1);
    return 1;
}
struct HuffmanNode
{
    float data;// 权值
    HuffmanNode *leftChild,*rightChild,*parent;
};
class HuffmanTree
{
    HuffmanNode *root;
    void mergeTree(HuffmanNode *ht1,HuffmanNode *ht2,HuffmanNode *&parent);
public:
    HuffmanTree(float w[],int n);
    ~HuffmanTree(){};
};
HuffmanTree::HuffmanTree(float w[],int n)
{
    MinHeap<HuffmanNode*> hp;// 把所有权值变成 “单节点树”，放入最小堆
    //first、second：每次取出的两棵最小树   parent：新合并的树  work：临时新节点
    HuffmanNode *parent,*first,*second,*work;
    for(int i=0;i<n;++i)// 把每个权值变成一个结点
    {
        work=new HuffmanNode;
        work->data=w[i];
        work->leftChild=work->rightChild=work->parent=0;
        hp.Insert(work);
    }
    for(int i=0;i<n-1;++i)
    {
        hp.RemoveMin(first);// 取最小权值树
        hp.RemoveMin(second);// 取次小权值树
        mergeTree(first,second,parent);// 合并成新树
        hp.Insert(parent);// 新树放回堆
    }
    root=parent;
}
void HuffmanTree::mergeTree(HuffmanNode *ht1,HuffmanNode *ht2,HuffmanNode *&parent)
{
    parent=new HuffmanNode;
    parent->data=ht1->data+ht2->data;
    parent->leftChild=ht1;
    parent->rightChild=ht2;
    ht1->parent=ht2->parent=parent;
}
   
 更新于