二叉树的各种遍历方式的完整C++代码在github仓库上

二叉树

遍历

  • 按照遍历方式可以分为递归遍历和迭代遍历
  • 按照遍历结果可以分成深度遍历和广度遍历

广度优先遍历

层序遍历

深度优先遍历

深度优先遍历按照遍历方式可以分为递归遍历和迭代遍历, 按照遍历结果可以分为前序遍历、中序遍历和后续遍历, 前、中、后序指的是父节点的遍历顺序.

递归方式

递归方式调用栈这种方式与二叉树的三种深度优先遍历方式天然契合 节点的遍历顺序和节点的处理顺序完全一致
使用迭代方式是需要我们额外模拟调用栈的作用机制 让他表现为节点的便利顺序 和处理顺序一致

前序遍历

配套练习 144.二叉树的前序遍历

遍历顺序 中->左->右

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
template <typename T>
void BinaryTree<T>::InnerPreorderTraversalRecursion(BinaryTreeNode<T> *cur, Queue<BinaryTreeNode<T>> *queue)
{
    // 前序遍历 中->左->右
    if (cur == nullptr)
    {
        return;
    }

    // 输出cur的index
    queue->EnQueue(cur);
    // 遍历左
    InnerPreorderTraversalRecursion(cur->left, queue);
    // 遍历右
    InnerPreorderTraversalRecursion(cur->right, queue);
}

template <typename T>
void BinaryTree<T>::PreorderTraversalRecursion(Queue<BinaryTreeNode<T>> *queue)
{
    // 在使用C++时，当向一个方法请求返回一组数据结构时，最好的做法是调用这个方法，并向这个方法中传入用来存储结果的指针
    // 因为这样能确保这个指针的new和delete是成对出现的
    // 如果你在这个方法内部new了一个队列 然后返回出去 外部很有可能在完成操作后忘记对这个队列执行delete操作，这就造成内存泄漏了
    InnerPreorderTraversalRecursion(_root, queue);
}

中序遍历

配套练习 94.二叉树的中序遍历
⚠️注意: 中序遍历要比前序和后序特殊 因为遍历树节点的顺序和处理树节点的顺序是不一样的

遍历顺序 左->中->右

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
// 中序遍历
template <typename T>
void BinaryTree<T>::InorderTraversalRecursion(Queue<BinaryTreeNode<T>> *queue)
{
    InnerInorderTraversalRecursion(_root, queue);
}

template <typename T>
void BinaryTree<T>::InnerInorderTraversalRecursion(BinaryTreeNode<T> *cur, Queue<BinaryTreeNode<T>> *queue)
{
    // 前序遍历 中->左->右
    if (cur == nullptr)
    {
        return;
    }

    // 遍历左
    InnerInorderTraversalRecursion(cur->left, queue);

    // 输出cur的index
    queue->EnQueue(cur);

    // 遍历右
    InnerInorderTraversalRecursion(cur->right, queue);
}

后序遍历

配套练习 145.二叉树的后序遍历

遍历顺序 左->右->中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
void BinaryTree<T>::InnerPostorderTraversalRecursion(BinaryTreeNode<T> *cur, Queue<BinaryTreeNode<T>> *queue)
{
    // 前序遍历 中->左->右
    if (cur == nullptr)
    {
        return;
    }

    // 遍历左
    InnerPostorderTraversalRecursion(cur->left, queue);

    // 遍历右
    InnerPostorderTraversalRecursion(cur->right, queue);

     // 输出cur的index
     queue->EnQueue(cur);
}

迭代方式

  • 前序遍历
  • 后序遍历
  • 中序遍历 ⚠️注意: 中序遍历要比前序和后序特殊 因为遍历树节点的顺序和处理树节点的顺序是不一样的

迭代方式

前序方式

不能用递归了, 那就要用迭代的方式尝试模拟递归的思想, 那么我们就需要在代码中手动的创建一个栈, 用来模拟递归方式中的函数调用栈
由二叉树节点的结构可知, 我们可以通过一个节点找到该节点的左右孩子(如果有的话),

后序遍历
配套练习 145.二叉树的后序遍历

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
template <typename T>
void BinaryTree<T>::PostorderTraversalIteration(Queue<BinaryTreeNode<T>> *queue)
{
    Stack<BinaryTreeNode<T>> stack = Stack<BinaryTreeNode<T>>();

    stack.Push(_root);
    
    // 而后续遍历的顺序是左 -> 右 -> 中 需要将队列翻转一下
    while(!stack.IsEmpty()){
        BinaryTreeNode<T> *node = stack.Pop();
        queue->EnQueue(node);
        if(node->left != nullptr){
            stack.Push(node->left);
        }
        if (node->right != nullptr)
        {
            stack.Push(node->right);
        }
    }

    // 将队列反转

    queue->Reverse();
}

中序遍历

中序遍历需要引入一个cur指针, 思考引入这个指针的目的是什么? 目前我的理解是, 这个指针是一个右转标记, 如果指针是null了, 代表以当前栈顶节点为根结点的树的左子树已遍历完毕

迭代方式的统一写法(标记法)

迭代方式的困难点在于 我们通过二叉树节点 能够遍历节点的方式 和 二叉树的前、中、后序遍历方式都不太一样, 我们可以通过给节点打标记的方式 来判断一个节点到底是该进行遍历还是写入结果集和.

注意

不同的编译器 Win上的MinGW和Mac上的clang貌似对于指针释放操作有不同的处理，必须下面这段代码，笔者在二叉树类的析构方法中把二叉树中所有的节点全部释放掉：

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
BinaryTree<T>::~BinaryTree()
{
    // 前序遍历所有节点
    Queue<BinaryTreeNode<T>> *queue = new Queue<BinaryTreeNode<T>>();
    PreorderTraversalRecursion(queue);
    while(!queue->IsEmpty()){
        BinaryTreeNode<T>* node = queue->DeQueue();
        delete node;
    }
    delete queue;
}

在调用二叉树类的地方main方法中，手动释放掉二叉树对象占用的内存，在Mac的Clang中，该操作会报错，但是在Win的MinGW中，就不会有这个问题。

时间复杂度

常用时间复杂度表示O(n) O(log n) O(n!) O(n^2)

1
2
3
int multiply(int A, int B) {
    return B?multiply(A<<1,B>>1)+(B&1?A:0):0;
}

代码功能
这段代码通过递归和位操作实现了两个整数的乘法，避免了直接使用 * 运算符。

关键点
位操作：

左移操作 A << 1 相当于 A * 2。
右移操作 B >> 1 相当于 B / 2。
按位与操作 B & 1 用于检查 B 的最低位是否为 1。
递归：

每次递归计算当前位的贡献，并将问题规模缩小一半，直到 B == 0。
时间复杂度：

每次递归将 B 减少一半，因此递归深度为 O(log B)。
每次递归的计算量为常数，因此总时间复杂度为 O(log B)。