1. 树

定义：对一个节点而言，上层元素为直接前驱而且直接前驱唯一，下层元素为直接后继且直接后继可以有多个

  • 根，子树
  • 一个结点子树的根称为孩子节点，反之为父节点
  • 父结点的父结点是祖父结点
  • 根到某结点路径上所有结点（含根节点）都是祖先结点。反之都是祖先结点的子孙结点
  • 同一父节点的结点互为兄弟结点
  • 树中每个结点拥有孩子结点个数为结点的度，度为0是叶子结点，不为0是中间结点
  • 树的度是每个结点度的最大值
  • 根的层次数规定为1，其余结点层次数是父结点+1，所有结点层次数最大值是树的高度
  • 若每个孩子节点被规定了顺序，称为有序数，否则是无序树
  • 两棵以上的树是森林
  • 父结点是孩子结点的直接前驱，孩子节点是父结点的直接后继。直接前驱唯一，直接后继可以有多个

2. 二叉树

2.1 二叉树的定义

二叉树和树是两种完全不同的结构，二叉树不是特殊的树。

  • 二叉树允许空树存在，而树中结点个数至少是1，证明二叉树更多作为一种工具存在
  • 二叉树左右孩子要明确指出是左还是右，即使只有一个孩子也要说明是左子还是右子。有序树中孩子只是排序了，没有左右之分
  • 若k层二叉树每一层结点数量都达到最高值，则是满二叉树
  • 若k层二叉树前k-1层是满的，第k层可能缺少一些结点，==但是缺少的结点是自右向左的==，称为==完全二叉树==

2.2 二叉树的性质

  1. 一棵非空二叉树的第i层上最多有$2^{i-1}$ 个结点。
  2. 高度为k的二叉树，最多有$2^k-1$个结点
  3. 对于一棵非空二叉树，叶子结点个数为$n_0$，度数为2的结点个数为$n_2$，有：$n_0=n_2+1$。
  4. 具有n个结点的完全二叉树高度为$k=[log_2n]+1$。
  5. 若将二叉树按层次遍历编号，i>1时，父节点编号为[i/2]；若2i>n，编号为i的结点无左儿子，否则左儿子编号为2i；若2i+1>n，编号为i的结点无右儿子，否则右儿子编号为2i+1

2.3 二叉树的存储

  1. 数组存储，但是数组退化成一条链时浪费空间
  2. 链表存储：left、right、data

2.4 二叉树的遍历

2.4.1 前序遍历

根左右

递归算法：

1
2
3
4
5
6
7
8
//递归算法
void pre_order(node *t){
	if(t!=NULL){
		cout<<t->data<<" ";
		pre_order(t->left);
		pre_order(t->right);
	}
}

非递归算法：
根进栈。
重复操作：出栈并访问，访问右子，如有右子，右子进栈，若有左子，左子进栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
void pre_order(node *t){
	stack<node*> s;
	s.push(t);
	
	while(!s.empty){
		node *p=s.top();
		s.pop();
		cout<<p->data<<" ";
		
		if(p->right!=NULL) s.push(p->right);
		if(p->left!=NULL) s.push(p->left);
	}
}

时间复杂度为o(n)

2.4.2 中序遍历

左根右

递归算法：

1
2
3
4
5
6
7
void in_order(node *t){
	if (t==NULL) return;
	
	pre_order(t->left);
	cout<<t->data<<" ";
	pre_order(t->right);
}

非递归算法：
引入flag，记录结点是第几次被访问
根进栈；初始flag均为0；
重复以下操作直至栈空：出栈，若flag=0；flag++，入栈，如有左子，左子入栈；若flag=1，访问，如有右子，入栈。

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
void in_order(node *t){
	stack<node *> s;
	stack<int> flag;
	auto push_node=[&s;&flag](node *p,int f){
		s.push(p);
		flag.push(f);
	}
	push_node (t,0);
	
	while(!s.empty()){
		node *p=s.top();
		int f=flag.top();
		s.pop();
		flag.pop();
		
		if(f==0){
			push_node (p,1);
			if(p->left!=NULL) push_node (p->left,0);
		}
		else{
			cout<<p->data<<" ";
			if(p->right!=NULL) push_node(p->right,0);
		}
	}
}

时间复杂度为o(n)

2.4.3 后序遍历

左右根

递归算法：

1
2
3
4
5
6
7
void post_order(node *t){
	if(t==NULL) return;
	
	post_order(t->left);
	post_order(t->right);
	cout<<t->data<<" ";
}

非递归算法：
若flag=0，flag++，该结点再次入栈，若有左子，左子也入栈；若flag=1，flag++，该结点再次入栈，若有右子，右子入栈；若flag=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
void post_order(node *t){
	stack<node *>s;
	stack<int> flag;
	auto push_node=[&s;&flag](node *p,int f){
		s.push(p);
		flag.push(f);
	}
	push_node (t,0);
	
	while(!s.empty()){
		node *p=s.top();
		int f=flag.top();
		s.pop();
		flag.pop();
		
		if(f==0){
			push.node(p,1);
			if(p->left!=NULL) push node(p->left,0);
		}
		else if(f==1){
			push_node(p,2);
			if(p->right!=NULL) push_node(p->right,0);
		}
		else cout<<p->data<<' ';
	}
}

时间复杂度是o(n)

2.4.4 层次遍历

根节点进队
重复操作直至队空：队首结点出队访问；若有左子，左子进队；若有右子，右子进队

1
2
3
4
5
6
7
8
9
10
11
12
void BinaryTree levelOrder(){
	if(root==NULL) return;
	queue<node *>q;
	q.push(root);
	while (!q.empty()){
		int p=q.front();
		q.pop();
		cout<<p->data<<" ";
		if(p->left!=NULL) q.push(p->left);
		if(p->right!=NULL) q.push(p->right)
	}
}

时间复杂度是o(n)

2.5 二叉树类及操作实现

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
template<class T, T NULL_VALUE>
BinaryTree<T,NULL_VALUE>::BinaryTree(const vector<T> &v){
	if(v.empty()){
		root=NULL;
		return;
	}
	
	queue<Node*> q;
	root=new Node(v[0]);
	q.push(root);
	
	for(int i=1;i<v.size();i+=2){
	//i+=2跳过下面使用过的两个索引
		Node<T,NULL_VALUE> *p=q.front();
		q.pop();
		
		if(v[i]!=NULL_VALUE){
			p->left=new Node<T,NULL_VALUE>(v[i]);
			q.push(p->left);
		}		
		
		if(i+1<v.size()&&v[i+1]!=NULL_VALUE){
			p->right=new Node<T,NULL_VALUE>(v[i+1]);
			q.push(p->right);
		}
	}
}

类似层次遍历的思想，出队时两个孩子入队

size height

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T,T NULL_VALUE>
int BinaryTree<T,NULL_VALUE>::_size(Node<T,NULL_VALUE> *t){
	if(t==NULL) return 0;
	return 1+_size(t->left)+_size(t->right);
}

template<class T,T NULL_VALUE>
int BinaryTree<T,NULL_VALUE>::_height(Node<t,NULL_VALUE> *t){
	if(t==NULL) return 0;
	int hl=height(t->left);
	int hr=height(t->right);
	return (hl>hr)?(hl+1):(hr+1);
}

template<class T, T NULL_VALUE> int BinaryTree<T, NULL_VALUE>::size(){
	return _size(root);
}

template<class T,T NULL_VALUE> int BinaryTree<T,NULL_VALUE>::height(){
	return _height(root);
}

删除一棵树

1
2
3
4
5
6
7
8
9
10
11
12
template <class T,T NULL_VALUE>
void BinaryTree<T, NULL_VLAUE>::_del_tree(Node<T,NULL_VALUE> *t){
	if(t==NULL) rerturn;
	_del_tree(t->left);
	_del_tree(t->right);
	delete t;
}

template<class T,T NULL_VALUE> void BinaryTree <T,NULL_VALUE>::delTree(){
	_del_tree(root);
	root=NULL;
}

3. 遍历确定二叉树

  • 已知一棵完全二叉树的层次遍历，能唯一确定这棵完全二叉树
  • 已知一棵满二叉树的前序、后序、中序遍历之一，可以唯一确定一棵满二叉树
  • 已知一个一般二叉树的前序和中序遍历，可以唯一确定一棵二叉树
  • 已知一个一般二叉树的后序和中序遍历，可以唯一确定一棵二叉树
  • 已知一个一般二叉树的前序和后序遍历，不可以唯一确定一棵二叉树

代码实现：前序+中序
思想：由前序数组定出根结点值后，在中序数组找到根结点值所在的位置，由此找到了前序和中序序列中根的左子树下标范围，同样也找到了右子树的下标范围。接下来递归左右子树下标范围即可确定该二叉树

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
template <class T, T NULL_VALUE>
void BinaryTree<T, NULL_VALUE>::buildTreePreIn(const std::vector<T> &pre, const std::vector<T> &in) {
  // 确认输入序列不为空且长度相同
	if (pre.empty() || in.empty() || pre.size() != in.size())
	    return;
  // 确认两个序列中元素相同且不出现重复元素
	unordered_set<T> pre_set(pre.begin(), pre.end());
    unordered_set<T> in_set(in.begin(), in.end());
    if (pre_set != in_set || pre_set.size() != pre.size())
	    return;
  // 使用前序和中序序列构造二叉树
  // 定义匿名函数用于递归
    function<Node<T, NULL_VALUE> *(int, int, int, int)> build =[&](int pre_l, int pre_r, int in_l, int in_r) -> Node<T, NULL_VALUE> * {
	    if (pre_l > pre_r || in_l > in_r) // 递归终止条件
		    return nullptr;
		// 使用前序序列第一个元素构造根节点
	    Node<T, NULL_VALUE> *root = new Node<T, NULL_VALUE>(pre[pre_l]);
	    int i = in_l; // 在中序序列中找到根节点的位置
	    while (i <= in_r && in[i] != pre[pre_l])
	        ++i;
	    int left_size = i - in_l; // 左子树的结点个数
	    root->left = build(pre_l + 1, pre_l + left_size, in_l, i - 1); // 递归左子
	    root->right = build(pre_l + left_size + 1, pre_r, i + 1, in_r); // 递归右子
	    return root;
	};
  // 删除原有二叉树并构造新的二叉树
    delTree();
    root = build(0, pre.size() - 1, 0, in.size() - 1);
}

4. 最优二叉树

  • 加权路径长度（WPL）：从根节点到各个叶子结点的路径长度×该叶子权值之和
  • 最优二叉树：WPL最小，权值越大越靠近根
  • 哈夫曼算法：1.若U中只有一个结点，操作结束，否则转向第2步。2.在集合中选取两个最小节点x,y 构造新的结点z，权值为x y权值之和，在集合U中删除结点x y并加入新结点z，再转向第一步
  • 哈夫曼树一定是最优二叉树
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
34
35
36
37
38
39
class HuffmanNode{
	public:
	int data;
	int weight;
	HuffmanNode *left;
	HuffmanNode *right;
	HuffmanNode(x,y,*a,*b):data(x),weight(y),left(a),right(b){};
};

HuffmanNode buildHuffmanTree(vector<HuffmanNode *> &nodes){
	while(nodes.size()>1){
		auto [min1,min2]=findMinTwoNodes(nodes);
		HuffmanNode *new_node=new HuffmanNode('\0',min->weight+min->weight,min1,min2);
		nodes.erase(remove(nodes.begin(),nodes.end(),min1),nodes.end());
		nodes.erase(remove(nodes.begin(),nodes.end(),min2),nodes.end());
		nodes.push_back(new_node);
	}
	return nodes.empty()? NULL:nodes[0];
}

static pair<HuffmanNode *,HuffmanNode *> findMinTwoNodes(vector<HuffmanNode *> &nodes){
	HuffmanNode *min1=NULL;
	HuffmanNode *min2=NULL;
	int min_weight1=INT_MAX;
	int min_weight2=INT_MAX;
	for(auto node:nodes){
		if(node->weight<min_weight1){
			min_weight2=min_weight1;
			min2=min1;
			min_weight1=node->weight;
			min1=node;
		}
		else if(node->weight<min_weight2){
			min_weight2=node->weight;
			min2=node;
		}
		return {min1,min2};
	}
}

时间复杂度$o(n^2)$，但学了堆以后，找到权值最小的两个元素的时间复杂度降至o(logn)，时间复杂度降至o(nlogn)

哈夫曼编码：从根开始遍历。向左则字符串加0，向右加1，直至遍历到叶子结点。
==可用的编码只能出现在叶子结点上！！！==

1
2
3
4
5
6
7
8
9
void printHuffmanCodes(HuffmanNode *root,string code){
	if(!root) return;
	if(!root->left && !root->right){
		cout<<root->data<<" "<<code<<endl;
	}
	
	printHuffmanCodes(root->left,code+'0');
	printHuffmanCodes(root->right,code+'1');
}

时间复杂度为o(n)

5. 树和森林

  • 非二叉树的孩子兄弟表示法：保存数据，指向最大孩子和最大弟弟的指针。

  • 森林的孩子兄弟表示法：每棵树按孩子兄弟法存储后，再将每棵树的根视作兄弟一个一个接在最小哥哥的右分支上

  • 二叉树转化为树和森林：反过来操作

  • 树的遍历：

  1. 前序遍历：放问完根节点再从左至右前序遍历子树
  2. 后序遍历：先从左至右逐个后序遍历所有子树再访问根
  3. 根有多个孩子，故无法定义中序遍历

  • 树的先根遍历就是对应二叉树的先序遍历，==后根遍历是对应二叉树的中序遍历==

  • 森林的遍历：

  1. 前序遍历：访问第一棵树的根结点，前序遍历第一棵树中所有根结点的所有子树形成的森林，从左至右同样方式依次访问所有的树
  2. 后序遍历：中序遍历第一棵树中根的子树形成的森林，访问第一棵树的根节点，从左至右依次访问所有树
  • 森林的先根遍历就是对应二叉树的先序遍历，==后根遍历是对应二叉树的中序遍历==

在内存中有一个用二叉树表示的一棵树

  1. 如何求树的高度？二叉树的前序遍历，访问一个结点时，左子的层次为父结点层次加一，右子的层次和父结点的一样的方法来处理
  2. 求森林中树有几棵？可以在二叉树中顺着根，一路右子计数过去，便可解决

==已知一棵树的前序遍历和后序遍历，可以唯一决定一棵树。==
一棵树的前序遍历序列即其对应孩子兄弟二叉树的前序遍历，一棵树的后序遍历序列即其对应孩子兄弟二叉树的中序遍历，而已知二叉树的前序和中序遍历可以唯一确定这棵二叉树，根据这棵二叉树又能唯一对应一棵树。

6. 优先级队列

6.1 基本的优先级队列（基于线性表）

结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队。

处理优先级的两种方法：

  1. 入队时，按照优先级在队列中寻找合适的位置，将新入队的元素插入在此位置；出队操作的实现保持不变。入队操作的时间复杂度是O(N)，出队操作的时间复杂度是O(1)
  2. 入队操作的实现保持不变，将新入队的元素放在队列尾；但出队时，在整个队列中查找优先级最高的元素，让它出队。入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(N)。

6.2 二叉堆(基于树的优先级队列)

  • 最小化堆：父结点小于子结点
  • 最大化堆：父结点大于子结点

存储：
由于==二叉堆是完全二叉树==，可以采用顺序存储。二叉堆的有序性可以很容易地通过下标来反映。一般为方便计算，==根结点的下标为1==。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> class PriorityQueue {
private:
  std::vector<T> data = std::vector<T>(1);
  public:
  PriorityQueue() = default;
  PriorityQueue(const std::vector<T> &elements);
  void push(const T &value);
  T pop();
  T top() const;
  bool empty() const;
  size_t size() const;
};

push操作：
在具有最大序号的元素之后插入新的元素或结点，如果新元素放入后，没有违反堆的有序性，那么操作结束。否则，让该节点向父节点移动，直到满足有序性或到达根节点。新节点的向上移动称为向上过滤。

1
2
3
4
5
6
7
8
9
10
void push(const T &value) {
   data.push_back(value);
   heapify_up(data.size() - 1);
}
void heapify_up(int index) {
   while (index > 1 && data[index] < data[parent(index)]) {
	   std::swap(data[index], data[parent(index)]);
       index = parent(index);
    }
}

时间复杂度：最坏情况是O(logN)，即完全二叉树的高度，平均情况，过滤会提前结束

pop操作：
当最小元素被删除时，在根上出现了一个空结点，放入最后一项，向下过滤

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
T pop() {
    if (data.size() <= 1) {
        throw std::out_of_range("PriorityQueue is empty");
    }
    T maxValue = data[1];
    data[1] = data.back();
    data.pop_back();
    if (data.size() > 1) {
        heapify_down(1);
    }
    return maxValue;
}

void heapify_down(int index) {
    int size = data.size();
    while ((index *2) < size) {
	    int child = index*2; 
	    if (child + 1 < size && data[child + 1] < data[child]) {
	        child++;
	    }
	    if (data[index] <= data[child]) {
	        break;
	    }
	    std::swap(data[index], data[child]);
	    index = child;
    }
}

时间复杂度o(logn)

建堆：自下往上调整每一个子堆。从最大的非叶索引开始，每一个向下过滤

1
2
3
4
5
6
PriorityQueue(const std::vector<T> &elements) {
    for (const auto &element : elements)
      data.push_back(element);
    for (int i = data.size() / 2; i > 0; --i)
      heapify_down(i);
}

建堆时间复杂度o(n)

http://chenjiayi0505.github.io/2026/07/02/数据结构 第四章 树/
作者
Jiayi Chen
发布于
2026年7月2日
更新于
2026年6月22日
许可协议