树,一种非线性表数据结构:
最常用的树结构。
每个节点最多有两个子节点:左子节点,右子节点。
为啥就把最后一层的叶子节点靠左排列的叫完全二叉树?靠右排列为啥就不行?
要搞清楚完全二叉树为啥这么定义,先学习
每个节点有三个字段:
大部分二叉树代码都是通过这种结构实现的。
若节点X存储在数组中下标为i的位置
2 * i
存储左子节点
2 * i + 1
存储右子节点
i/2
存储其父节点
由于这是个完全二叉树,所以仅“浪费”了一个下标0的存储位置。若是非完全二叉树,就会浪费较多存储空间:
所以完全二叉树用数组存储最省内存,就不像链式存储法,还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。
堆也是一种完全二叉树,所以其最常用的存储方式就是数组。
这些都是递归过程。
递归代码的关键就是递推公式,递推公式的关键就是,如果要解决问题A,就假设子问题B、C已经解决,然后再来看如何利用B、C来解决A。
所以可以写出前、中、后序遍历的
前序遍历
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码,表示打印root节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码,表示打印root节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码,表示打印root节点
}
每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数n成正比,也就是说二叉树遍历的时间复杂度是O(n)。
参考