树¶

概念¶

定义¶

总的来说树是递归地定义的

树是n(n>=0)个节点的有限集合，n=0时称为空树
在任意一棵非空树中，有且仅有一个特定的称为根(root)的节点
当n>1时，其余节点可分为m(m>0)个互不相交的有限集合T1、T2、...、Tm，其中每一个集合本身又是一棵树，并称为根的子树(subtree)（换言之，除了根节点外，每个节点都有且仅有一个父节点）
树由一个根节点和0个或多个非空的子树组成，这些子树与根通过一条有向的边(edge)连接，一棵N个节点的树有N-1条边

术语¶

节点的度(degree)：节点拥有的子树的个数 （与图中的度不同）
树的度：树所有节点中最大的度数
叶节点（Leaf）：度为零的节点
分支节点（Branch）：度不为零的节点
父节点（Parent）：有子树的节点是其子树的根节点的父节点
子节点（Child）：若A节点是B节点的父节点，则称B节点是A节点的子节点
兄弟节点（Sibling）：具有相同父节点的节点互称为兄弟节点
祖先节点（Ancestor）：从根到某节点所经分支上的所有节点
子孙节点（Descendant）：以某节点为根的子树中任一节点
路径（Path）：从节点n1到nk的路径是一个节点序列n1, n2, ..., nk，使得ni是ni+1的父节点
路径长度：路径上的边数
节点的层次（Level）：规定根节点在第一层，其子节点在第二层，以此类推
树的高度/深度（Depth）：树中节点的最大层次
节点的高度：从节点到叶节点的最长路径的边数
节点的深度：从根到该节点的路径长度

实现¶

数组实现较难实现树的一些复杂结构
链表实现可行但是空间浪费较大

这里使用FirstChild_NextSibling Representation实现树

typedef struct TreeNode *PtrToNode;
struct Tree Node {
    // 节点元素
    ElementType Element;
    // 指向第一个子节点
    PtrToNode FirstChild;
    // 指向下一个兄弟节点
    PtrToNode NextSibling;
};

将这种方法表示的树顺时针旋转45°，得到类似二叉树的结构

二叉树¶

定义¶

二叉树是n(n>=0)个节点的有限集合，它或者是空集（n=0），或者由一个根节点及两棵互不相交的。分别称为这个根的左子树和右子树的二叉树组成
二叉树是每个节点最多有两个子树的树结构
二叉树的子树有左右之分，次序不能颠倒

术语¶

满二叉树（Full Binary Tree）：每个节点的度都是0或2
斜二叉树（Skewed Binary Tree）：所有节点只有左子树或右子树的二叉树
完全二叉树（Complete Binary Tree）：最后一层有空缺，其余层都是满的。

性质¶

在二叉树的第i层上至多有$2^{i-1}$个节点$(i>=1)$
深度为k的二叉树至多有$2^k-1$个节点$(k>=1)$
对任何一棵二叉树T，如果其叶节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$
具有n个节点的完全二叉树的深度为$\log_2[n]+1$，其中$[x]$表示不大于x的最大整数

遍历¶

代码实现¶

根本问题：二维结构线性化

先序遍历(preorder traversal)：根-左-右

// it is recursive
void PreOrderTraversal( BinTree BT ) {
    if( BT ) {
        // visit root
        printf("%d\n", BT->Data);
        // traverse left subtree
        PreOrderTraversal( BT->Left );
        // traverse right subtree
        PreOrderTraversal( BT->Right );
    }
}

中序遍历(inorder traversal)：左-根-右

递归实现迭代实现（堆栈）

    void InOrderTraversal( BinTree BT ) {
    if( BT ) {
        // traverse left subtree
        InOrderTraversal( BT->Left );
        // visit root
        printf("%d\n", BT->Data);
        // traverse right subtree
        InOrderTraversal( BT->Right );
    }
}

    void InOrderTraversal( BinTree BT){
        BinTree T = BT;
        // create and initialize a stack
        Stack S = CreateStack( MaxSize );
        // traverse the tree
        while ( T || !IsEmpty(S) ){
            // traverse left subtree
            while ( T ) {
                // push the node into the stack
                Push( S, T );
                T = T->Left;
            }
            if( !IsEmpty(S) ) {
                // pop the node from the stack
                T = Pop( S );
                printf("%d\n", T->Data);
                // traverse right subtree
                T = T->Right;
            }
        }
    }

后序遍历(postorder traversal)：左-右-根

// it is recursive
void PostOrderTraversal( BinTree BT ) {
    if( BT ) {
        // traverse left subtree
        PostOrderTraversal( BT->Left );
        // traverse right subtree
        PostOrderTraversal( BT->Right );
        // visit root
        printf("%d\n", BT->Data);
    }
}

层序遍历(level order traversal)：按层次从上到下，从左到右

队列实现：根节点入队，然后开始循环：出队一个节点，访问该节点，将其左右孩子入队

void LevelOrderTraversal( BinTree BT ) {
    Queue Q;
    BinTree T;
    // if the tree is empty, return
    if( !BT ) return;
    // create a queue and initialize it
    Q = CreateQueue();
    AddQ( Q, BT );
    while( !IsEmpty(Q) ) {
        // when the queue is not empty, dequeue a node
        T = DeleteQ( Q );
        // visit the node
        printf("%d\n", T->Data);
        // if the node has left or right child, enqueue them
        if( T->Left ) AddQ( Q, T->Left );
        if( T->Right ) AddQ( Q, T->Right );
    }
}

应用¶

输出叶节点：先序，print前加if判断
求二叉树高度：后序，返回左右子树高度的最大值+1
二元运算表达式树的计算：先序、中序、后序遍历得到前缀、中缀、后缀表达式。注意：中缀表达式需要在每个左子树输出完成后加括号以保证运算优先级一致
由中序和另外任一遍历序列，可以唯一确定一棵二叉树

储存结构¶

顺序存储：将二叉树按照完全二叉树的方式存储在数组中。若节点的序号为i，则：
- 其左孩子的序号为2i，（若$2i \le n$,则无左孩子）
- 右孩子的序号为2i+1，（同上）
- 父节点的序号为$\lfloor i/2 \rfloor$ 对一般二叉树也可用这种方式存储，但会浪费空间（无节点处为空）

链表储存

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

线索二叉树（Thread binary tree）¶

为了方便遍历，可以在二叉树的空指针域中存放指向该节点在某种遍历次序下的前驱和后继节点的指针，这种指针称为线索
如果一个节点的左子树为空，则其左孩子指针指向该节点的前驱；如果右子树为空，则其右孩子指针指向该节点的后继

二叉查找树（Binary Search Tree）¶

性质¶

各节点键值是各不相同的整数
非空左子树的所有键值小于其根节点的键值
非空右子树的所有键值大于其根节点的键值
左右子树都是二叉查找树

操作¶

查找：

任意元素

递归实现

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 IterFind( ElementType X, BinTree BST ) {
    while( BST ) {
        if( X > BST->Data ) 
            BST = BST->Right;
        else if( X < BST->Data ) 
            BST = BST->Left;
        else 
            return BST;
    }
    return NULL;
}

注意到查找效率和树的高度有关，最坏情况下为O(n)，平均情况下为O(logn)，因此需要保证树的平衡

最小元素：最左下节点

递归实现

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 ) {
        // if the tree is empty, create a new node
        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 );
            // recursively insert the node into the left subtree
        else if( X > BST->Data ) 
            BST->Right = Insert( X, BST->Right );
            // recursively insert the node into the right subtree
        }
    return BST;
    }

删除：分三种情况
1. 被删除节点为叶节点：直接删除，父节点指向NULL
2. 被删除节点有一个子节点：删除后用子节点替代
3. 被删除节点有两个子节点：用该节点右子树的最小值替代被删除节点，然后删除右子树的最小值节点；或者用左子树的最大值替代，然后删除左子树的最大值节点

递归实现

BinTree Delete( ElementType X, BinTree BST ) {
    Position Tmp;
    if( !BST ) 
        printf("Element not found\n");
    else if( X < BST->Data ) 
        BST->Left = Delete( X, BST->Left );
        // recursively delete the node from the left subtree
    else if( X > BST->Data ) 
        BST->Right = Delete( X, BST->Right );
        // recursively delete the node from the right subtree
    else {
        if( BST->Left && BST->Right ) {
            // if the node has two children
            Tmp = FindMin( BST->Right );
            BST->Data = Tmp->Data;
            BST->Right = Delete( BST->Data, BST->Right );
        } else {
            // if the node has one or zero child
            Tmp = BST;
            if( !BST->Left ) 
            // if the node has no left child
                BST = BST->Right;
            else if( !BST->Right ) 
            // if the node has no right child
                BST = BST->Left;
            free( Tmp );
        }
    }
    return BST;
}

lazy tag

当删除操作不多时，可以使用懒惰方法

具体来说，对要删除的节点做标记，访问时忽略，删除时不用free，重新插入时也不用malloc

平衡二叉树¶

二叉查找树的查找、插入、删除操作的时间复杂度与树的高度有关，因此需要保证树的平衡，即树的高度尽可能小。

平衡因子（Balance Factor）: 左子树的高度减去右子树的高度 BF(T) = $h_L - h_R$
平衡二叉树（AVL树）：空树或者任一节点左右子树高度差的绝对值不超过1的二叉查找树
- 任一节点的左右子树的高度差的绝对值不超过1
- 任一节点的左右子树都是平衡二叉树

Property

平衡二叉树高度为$h$,则节点数最少为$n_h = n_{h-1} + n_{h-2} + 1 $

实际上就是斐波那契数列减去1.可以证明，$\lim_{h \to \infty}n_h \approx \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{h+2} - 1$, 这说明 $h = O (\log_{2}{n})$

最后更新: 2024年10月2日 14:45:20
创建日期: 2024年3月20日 00:17:47