树

基本概念

结点的度：结点拥有的子树数
树的度：树中各结点度的最大值（下图中为3）

tree

tree_ceil

无序树：树中结点的各子树之间的顺序无关，可以交换位置
有序树：树中结点的各棵子树从左到右顺序相关，交换任意两棵子树的位置都将改变原来树的结构

森林：树的集合，0棵或多棵不相交的树组成森林

二叉树

二叉树的五种基本形态
注：在二叉树中结点的子树要区分左右子树，并非无序；二叉树的每个结点最多只能有2棵子树

binary_tree

性质：

二叉树的第 i（i>=1）层上至多有 2^i-1 个结点
高度为 h 的二叉树上至多有 2^h-1 个结点
包含 n 个结点的二叉树的高度最矮为 log₂(n+1) 向上取整，最高为 n
当每一层都只有一个结点的时候，二叉树高度最高，为 n
任一二叉树中，若叶结点数量为 n₀，度为 2 的结点数量为 n₂，则有 n₀=n₂+1

满二叉树

高度为 h，且有 2^h-1 个结点的二叉树（每一层结点数量都饱和）
满二叉树一定是完全二叉树，也是扩充二叉树

完全二叉树

只有最下面两层结点的度可以小于 2，其它层中的结点的度均等于 2
最下一层的叶结点均依次集中在靠左的若干位置上
具有 n 个结点的完全二叉树的高度为 log₂(n+1) 向上取整

Complete_Binary_Tree

tree_order

扩充二叉树（2-树）

除叶子结点以外，其余结点都必须有 2 个孩子（仅存在度为 2 和 0 的结点，不存在度为 1 的结点）

求二叉树的结点总数量

$$
二叉树的结点总数量 = 左子树结点总数量 + 右子树结点总数量 + 根节点
$$

简单代码实现：

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    // 创建一个示例二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    int totalNodes = countNodes(root);
    std::cout << "二叉树的节点总数: " << totalNodes << std::endl;

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

清空二叉树

关键代码实现：

void TreeClear(BinaryTree *bt)  // 清空二叉树 bt
{
	Clear(bt->root);
}

// 后序遍历思想
void Clear(BTNode *t)  // 清空以 t 为根的二叉树
{
	if(!t)
		return;
	Clear(t->leftChild);
	Clear(t->rightChild)l
	free(t);  // 释放结点 t 的空间
}

二叉树的遍历

先序遍历（深度优先）—— O(n)

先访问根结点，再依次遍历左右子树

VLR

关键代码：

void PreOrderTree(BinaryTree *bt)
{
	PreOrder(bt->root);    //调用先序遍历递归函数
}

void PreOrder(BTNode *t)   //先序遍历递归函数
{
	if(!t)
		return;
	printf("%c",t->element);  //访问根节点
	PreOrder(t->lChild);    //先序遍历左子树
	PreOrder(t->rChild);    //先序遍历右子树
}

中序遍历（深度优先）—— O(n)

先遍历左子树，再访问根节点，最后遍历右子树

特性：根节点左子树中所有结点先于根结点访问输出，而右子树所有结点在根结点之后访问输出

LVR

关键代码：

void InOrderTree(BinaryTree *bt)
{
	InOrder(bt->root);    //调用中序遍历递归函数
}

void InOrder(BTNode *t)   //中序遍历递归函数
{
	if(!t)
		return;
	InOrder(t->lChild);    //中序遍历左子树
	printf("%c",t->element);  //访问根节点
	InOrder(t->rChild);    //中序遍历右子树
}

后序遍历（深度优先）—— O(n)

先依次遍历左右子树，最后访问根结点

特性：最后访问输出的是该二叉树的根结点

VRL

关键代码：

void PostOrderTree(BinaryTree *bt)
{
	PostOrder(bt->root);    //调用后序遍历递归函数
}

void PostOrder(BTNode *t)   //后序遍历递归函数
{
	if(!t)
		return;
	PostOrder(t->lChild);    //后序遍历左子树
	PostOrder(t->rChild);    //后序遍历右子树
	printf("%c",t->element);  //访问根节点
}

层次遍历（宽度优先）

从上到下、从左到右逐层访问二叉树每一个结点，每个结点访问且仅访问一次（非递归）

Level-order-traversal

关键代码——时间复杂度 O(n)：

#define QueueSize 100   // 队列容量
void LevelOrderTree(BinaryTree *tree) {
    Queue Q;    // Q 是用于存储 BTNode 结点类型指针的队列
    BTNode *p;
    if(!tree->root)
        return; // 二叉树为空，则直接返回
    Create(&Q, QueueSize); // 初始化队列
    Enqueue(&Q, tree->root); // 将根结点入队
    while(!isEmpty(&Q)){
        Front(&Q, &p); // 队首元素出队
        DeQueue(&Q); // 队首元素出队
        printf("%c ", p->element); // 访问队首元素
        if(p->leftChild) // 若左子树非空，则入队
            Enqueue(&Q, p->leftChild);
        if(p->rightChild) // 若右子树非空，则入队
            Enqueue(&Q, p->rightChild);
    }
    Destroy(&Q); // 销毁队列，释放内存
}