树

SyEic_L MVP++
  2025-10-29 22:01:16 2025-10-29 22:01:16 Created   2025-10-29 22:01:16 2025-10-29 22:01:16 Updated    2.7k Words  12 Mins  

树和森林概念

  • 自由树
    • 定义为二元组Tf={V,E}T_f = \{ V, E\}
    • V为顶点集合
    • E为边集合
  • 有根树
    • 有n个结点
    • r是根节点
    • 根以外的是子树
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Type> class Tree {
    public:
        Tree ( );
        ~Tree ( );
        position Root ( );
        BuildRoot ( const Type& value );
        position FirstChild ( position p );
        position NextSibling ( position p );
        position Parent ( position p );
        Type GetData ( position p );
        int InsertChild ( const position p, const Type &value );
        int DeleteChild ( position p, int i );
};
  • E=V−1E = V - 1（边数=结点数−1边数 = 结点数 - 1）

二叉树

分类

  • 满二叉树（FBT）

    全部填满

  • 完全二叉树（CBT）

    • 除了最后一层都是满二叉树且最后一层是从左到右依次填满
    • 对于一个h层的树，叶结点仅在h和h-1层
    • 对任一结点，若其右子树高度为k，则其左子树高度为k或k+1

性质

  1. 若层次从1开始计算，则第i层最多有2i−12^{i-1}个结点

  2. 深度为k的二叉树最多有2k−12^{k}-1个结点

  3. 对任何一棵二叉树，如果其叶结点有n0n_0个，度为2的非叶结点有n2n_2个，则有n0=n2+1n_0 = n_2 + 1

  4. 具有n个结点的完全二叉树高度为⌈log⁡2(n+1)⌉\lceil\log_2(n+1)\rceil

  5. n个结点的完全二叉树，同一层从左到右连续编号，则

    1
    2
    3
    4
    5
    6
    7
             1
          /     \
         2       3
       /   \    / \
      4     5  6   7
     / \   / 
    8   9 10

    • 若i==1i==1， 则ii为根若 i > 1，则父节点为，则父节点为\lfloor i/2\rfloor - 若n≥2∗in \geq 2*i，则节点ii左子节点为2∗i2 * i

    • 若n≥2∗i+1n \geq 2*i + 1，则节点ii左子节点为2∗i+12 * i + 1

    • 若ii为奇数，则为左子节点

      若ii为偶数，则为右子节点

    • 节点ii的层数为⌊log⁡2i⌋+1\lfloor \log_2i \rfloor + 1

二叉树存储表示

  • 顺序表示（数组）

  • 链表表示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //二叉链表
    struct TreeNode {
        public:
            string value;
            TreeNode* left;
            TreeNode* right;
            //TreeNode* parent;		//三叉链表
            TreeNode(string val) : value(val), left(nullptr), right(nullptr) {}
    };

    class BinaryTree {
        private:
            TreeNode* root;
        public:
            BinaryTree(TreeNode* r = nullptr) : root(r) {}
            int countNodes() const;
        	...
    };

  • 二叉链表的静态结构

二叉树遍历

1
2
3
4
5
6
7
8
9
       -
    /     \
   +       /
 /   \    / \
a     *  e   f
     / \ 
    b   -
    	 / \
    	c   d
  • 前序：−+a∗b−cd/ef-+a*b-cd/ef
  • 中序：a+b∗c−d−e/fa+b*c-d-e/f
  • 后序：abcd−∗+ef/−abcd-*+ef/-

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//中序遍历
void BinaryTree::inOrderRecursive ( TreeNode <Type> *subTree ) {
    if ( subTree != NULL ) {
        InOrder ( subTree->leftChild );
        cout << subTree->data;
        InOrder ( subTree->rightChild );
    }
}
//前序遍历
void BinaryTree::preOrderRecursive ( TreeNode <Type> * subTree ) {
    if ( subTree != NULL ) {
        cout << subTree->data;
        PreOrder ( subTree->leftChild );
        PreOrder ( subTree->rightChild );
    }
}
//后序遍历
void BinaryTree::postOrderRecursive ( TreeNode <Type> * subTree ) {
    if ( subTree != NULL ) {
        PostOrder ( subTree->leftChild );
        PostOrder ( subTree->rightChild );
        cout << subTree->data;
    }
}
递归计算二叉树节点个数
1
2
3
4
5
6
7
8
int BinaryTree::count(TreeNode<Type> *t) const{
    if (t == NULL){
        return 0;
    }
    else{
        return 1 + count(t->left) + count(t->right);
    }
}

非递归实现

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//单栈法
void BinaryTree::postOrder( TreeNode* root ) {
    if (!root) return;

    stack<TreeNode*> st;
    TreeNode* curr = root;
    TreeNode* lastVisited = nullptr;

    while (curr || !st.empty()) {
        if (curr) {
            st.push(curr);
            curr = curr->left;  // 一直往左走
        } 
        else {
            TreeNode* top = st.top();
            // 若右子树存在且未访问过，则转向右子树
            if (top->right && lastVisited != top->right) {
                curr = top->right;
            } 
            else {
                cout << top->val << " ";  // 打印当前节点 或 加入结果vector中
                lastVisited = top;        // 记录已访问节点
                st.pop();
            }
        }
    }
}
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(k)O(k) k为层数

双栈法

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BinaryTree::inOrder( TreeNode* root ) { 
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr || !st.empty()) {
        // 1️⃣ 一直往左走，把所有左孩子压栈
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }

        // 2️⃣ 弹出栈顶节点并访问
        curr = st.top();
        st.pop();
        cout << curr->val << " ";

        // 3️⃣ 转向右子树
        curr = curr->right;
    }
}
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(k)O(k)

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BinaryTree::preOrder( TreeNode* root ) { 
    if (!root) return;

    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";  // 先访问“根”

        if (node->right) st.push(node->right);
        if (node->left)  st.push(node->left);
    }
}
  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(k)O(k)

广度优先遍历（BFS）

1
2
3
4
5
6
7
8
9
10
11
void BFS(TreeNode* root){
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()){
        TreeNode* node = q.dequeue();
        cout << node->val << " ";
        if (!node->left) q.enqueue(node->left);
        if (!node->right) q.enqueue(node->right);
    }
}

二叉树建立

  • 已知前序和中序，可以唯一确定一棵二叉树
  • 已知中序和后序，可以唯一确定一棵二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Treenode* CreateBT(string pres,ins){
    int Inpos;
    string Prestemp,Instemp;
    if (pres.length( ) == 0) {
        temp = NULL;
    }
    else {
        temp = new Treenode();
        temp->data = pres.ch[0];
        Inspos = 0;
        while (Ins.ch[Inpos] != temp->data){
            Inpos++;
        } 
        prestemp = pres(1, Inpos);
        Instemp = ins(0, Inpos-1);
        temp->leftchild = CreateBT(prestemp, Instemp);
        prestemp = pres(Inpos + 1, pres.length( ) - Inpos - 1);
        Instemp = Ins(Inpos + 1, pres.length( ) - Inpos - 1);
        temp->rightchild = CreateBT(prestemp, Instemp);
        return temp;
    }
}

二叉树计数

设f(n)f(n)表示有 n 个结点的二叉树的数量。

  • 如果选某个结点作为根，那么：
    • 左子树有ii个结点；
    • 右子树有n−1−in−1−i个结点。

所以满足：

​ f(n)=∑i=0n−1f(i)×f(n−1−i)f(n) = \sum_{i=0}^{n-1} f(i) \times f(n-1-i)

​ f(n)=1n+1C2nnf(n) = \frac{1}{n+1}C^n_{2n}

线索二叉树

  • 在某种特定序列下的线索二叉树

  • 方法一：增加两个链域

    1
    2
    3
    4
    5
    6
    7
    struct TreeNode {
    	int val;
        TreeNode *left;
        TreeNode *right;
    	TreeNode* pred;		//前驱
        TreeNode* succ;		//后继
    }

  • 方法二：利用空链域

    • 如果结点有左孩子，则其left指示其左孩子；否则指示其前驱
    • 如果结点有右孩子，则其rightchild指示其右孩子；否则指示其后继
    • 设置两个标志：LeftThread、RightThread

树和森林

  • 父指针表示法

    0 1 2 3 4 5 6
    data A B C D E F G
    parent -1 0 0 0 1 1 3

  • 子女指针表示法

    data child1 child2 child3 …… child 4

    适用于等数量的链域

  • 子女链表表示

    子女链表表示

  • 左子女-右兄弟表示（二叉链表）

    左子女-右兄弟表示

树与二叉树转换

  1. 加线：兄弟加线
  2. 抹线：除第一左子节点外，删去该节点与其他子树的连线
  3. 调整：按层次排列
  • 根节点只有左子树
  • 左子树是原树左子树，右子树是原树的下一个兄弟

森林转二叉树

森林转二叉树

可以唯一确定由几棵树组成

树的遍历

  • 深度优先
    • 先根次序遍历
    • 后根次序遍历
  • 广度优先
1
2
3
4
5
6
7
8
9
 A								   A
    /  |  \							  /
   B   C   D							 B
 /   \     |						   /  \		
E     F    G			  ->   		  E    C
									   \	\
									   	F	 D
									   		/
									   	   G
先根：ABEFCDG

可以转成二叉树再前序遍历

后根：EFBCGDA

可以转成二叉树再中序遍历

广度优先：ABCDEFG

森林遍历

先根遍历

  • 一棵树一棵树先根遍历

  • 可以转换成二叉树前序遍历

后根遍历
  • 可以转换成二叉树中序遍历
广度优先

  • 森林并排排序

  • 按层次遍历

    1
    2
    3
    4
    5
    A			F		   H			
       /  |  \		|	 	 /   \
      B   C   D		G	 	I	   J		
              |			 	|			
              E           	K

    AFHBCDGIJEK

堆

优先级队列

  • 最小堆（根节点是当前树种最小的）
    • Ki≤k2i+1   &&   Ki≤K2i+2K_i \leq k_{2i+1} \space\space\space\&\& \space\space\space K_i \leq K_{2i+2}
  • 最大堆（根节点是当前树种最大的）
    • Ki≥k2i+1   &&   Ki≥K2i+2K_i \geq k_{2i+1} \space\space\space \&\& \space\space\space K_i \geq K_{2i+2}

堆的建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <class Type> MinHeap <Type> :: MinHeap ( int maxSize ) {
	//根据给定大小maxSize,建立堆对象
	MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; //确定堆的大小
	heap = new Type [MaxHeapSize];
	if ( heap == NULL ) {
		cerr << “存储分配错!” << endl; 
        exit(1);
	}
	CurrentSize = 0;
}

template <class Type> MinHeap <Type> :: MinHeap ( int maxSize ) {
    //根据给定大小maxSize,建立堆对象
    MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; //确定堆的大小
    heap = new Type [MaxHeapSize];
    if ( heap == NULL ) {
        cerr << “存储分配错!” << endl; 
        exit(1);
    }
    for ( int i = 0; i < n; i++ ) {//数组传送
        heap[i] = arr[i];
    }
    CurrentSize = n; //当前堆大小
    int currentPos = (CurrentSize - 2) / 2;
    //找最初调整位置:最后的分支结点号
    while ( currentPos >= 0 ) {
        //从下到上逐步扩大,形成堆
        FilterDown ( currentPos, CurrentSize-1 );
        //从currentPos开始,到CurrentSize止,
        //调整
        currentPos--;
    }
}

调整堆

向下调整

filterDown (heapify)

  • 与左右子女比较，将最小的放在根节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class Type> void MinHeap<Type> :: FilterDown ( int start, int EndOfHeap ) {
    int i = start, j = 2*i+1; // j 是 i 的左子女
    Type temp = heap[i];
    while ( j <= EndOfHeap ) {
        if ( j < EndOfHeap && heap[j] > heap[j+1] ) j++; //两子女中选小者
        if ( temp <= heap[j] ) break;
        else { 
            heap[i] = heap[j]; //下面的上浮
            i = j; 
            j = 2*j+1; //向下滑动
        }
    }
    heap[i] = temp;
}

向上调整

  • 与父节点比较，小于则交换，否则不动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class Type> void MinHeap<Type> :: FilterUp ( int start ) {
    //从 start 开始,向上直到0,调整堆
    int j = start, i = (j-1)/2; // i 是 j 的双亲
    Type 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;
}

插入

1
2
3
4
5
6
7
8
9
10
template <class Type> int MinHeap<Type> :: Insert ( const Type &x ) {
    if ( CurrentSize == MaxHeapSize ){ //堆满
       	cerr << "堆已满" << endl; 
    	return 0; 
    }
    heap[CurrentSize] = x; //插在表尾
    FilterUp (CurrentSize); //向上调整为堆
    CurrentSize++; //堆元素增一
    return 1;
}

删除

  • 删除堆顶元素
  • 最后一个节点填补取走的元素
  • 向下调整
1
2
3
4
5
6
7
8
9
10
11
template <class Type> int MinHeap <Type> :: Remove ( Type &x ) {
    if ( !CurrentSize ){
        cout << “ 堆已空 " << endl; 
        return 0; 
    }
    x = heap[0]; //最小元素出队列
    heap[0] = heap[CurrentSize-1];
    CurrentSize--; //用最小元素填补
    FilterDown ( 0, CurrentSize-1 ); //调整
    return 1;
}

Huffman树

  • 路径长度：PL
    • 根节点层数为0，从根节点到第L层节点的路径长度为L
  • 树的路径长度
    • n个节点的完全二叉树的路径长度为n个节点的路径长度之和
  • Huffman树：带权路径长度
    • 扩充二叉树

Huffman算法

  1. n个权值各成一棵树
  2. 选两个最小的树构成一个新的树，新树权值为两树权值之和
  3. 新树加入树list，并将两个子树删去
  4. 重复2、3，直到剩最后一棵树，两棵树构成新树
  • Title: 树
  • Author: SyEic_L
  • Created at : 2025-10-29 22:01:16
  • Updated at : 2025-10-29 22:01:16
  • Link: https://blog.syeicl.vip/2025/10/29/树/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
线性表 线性表 排序 排序 数组、串与广义表 数组、串与广义表
推荐阅读
线性表 线性表 排序 排序
Comments
On this page
树
  1. 树和森林概念
  2. 二叉树
    1. 分类
    2. 性质
    3. 二叉树存储表示
  3. 二叉树遍历
    1. 递归实现
    2. 非递归实现
  4. 二叉树建立
  5. 二叉树计数
  6. 线索二叉树
  7. 树和森林
    1. 树与二叉树转换
    2. 森林转二叉树
    3. 树的遍历
    4. 森林遍历
  8. 堆
    1. 堆的建立
    2. 调整堆
  9. Huffman树
    1. Huffman算法