抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

关于二叉树（上）

发布于：2023年8月15日

次浏览

前言

最近经常刷到二叉树的题，那么好好把二叉树的相关知识点都过一下吧。

本文参考了代码随想录关于二叉树的介绍。原文链接

分类

满二叉树

一个二叉树除了叶节点外每个节点都有两个子节点，且叶节点在同一层的二叉树。就是看上去都是满的。

深度为kk。节点数量就是2k−12^k-1个。

image.png

完全二叉树

除了最底层节点没填满外，其他节点都是满的。且最底层节点必须从左到右连续！

所以，满二叉树同时也是一个完全二叉树。

二叉搜索树

二叉搜索树是有数值且有序的。

它的子节点的位置要满足三个条件。

  • 左子树上所有节点都小于根节点
  • 右子树上所有节点都大于根节点
  • 左右子树都满足二叉搜索树

如图：

以根节点10为例，左子节点6<106<10，右子节点16>1016>10。

节点6同理，节点16也同理。

平衡二叉搜索树

平衡二叉搜索树也是有序树，但它跟二叉搜索树的区别在于它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

为什么要专门有个平衡二叉树呢？

因为一个二叉搜索树极端情况下退化为链表结构，根节点在尾部或头部。这样一来搜索的效率就低了。

存储

二叉树存储有两种方式，链式存储（指针实现）和顺序存储（数组实现）。

链式存储

一般链式存储较多，例如（Leetcode默认构造的二叉树）:

1
2
3
4
5
6
7
8
9
10
struct TreeNode
{
	int val;          //当前节点存放的数据
	TreeNode* left;   //指向左子节点
	TreeNode* right;  //指向右子节点
  //构造函数
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

顺序存储

而顺序存储则是使用下标来存储节点。

通过观察可以知道第ii个节点的左子结点下标为i∗2+1i*2+1，右子节点下标为i∗2+2i*2+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
vector<int> inorderTraversal(TreeNode* root)
{
  stack<TreeNode*> s;
  unordered_map<TreeNode*, bool> umap{{nullptr, false}};
  vector<int> res;
  s.push(root);
  TreeNode* temp;
  while (!s.empty())
  {
  	temp = s.top();
  	s.pop();
  	if (!temp)
  		continue;
  	if (umap[temp])
  		res.push_back(temp->val);
  	else
  	{
  		umap[temp] = true;
      //由于是栈，反过来看就是左中右
  		s.push(temp->right);
  		s.push(temp);
  		s.push(temp->left);
  	}
  }
  return res;
  }
};

该方法只需更改s.push()的位置就可直接实现前中后序遍历。

广度优先搜索

使用广度优先搜索实现的遍历方法为层序遍历。

使用队列来实现层序遍历。因为队列先进先出的特点可以实现广度优先搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> inorderTraversal(TreeNode* root)
	{
		queue<TreeNode*> q;
		vector<int> res;
		if (root) q.push(root);
		int len = q.size();
		while (!q.empty())
		{
			len = q.size();
			for (int i = 0; i != len; ++i)  //这里不能写i!=q.size()。因为len在循环体内会发生变化，会导致出错。
			{
				TreeNode* node = q.front();
				q.pop();
				res.push_back(node->val);
				if (node->left) q.push(node->left);
				if (node->right) q.push(node->right);
			}
		}
		return res;
	}

未完待续…

更新于：2024年4月2日

数据结构

二叉树

评论