数据结构--【二叉树】重难点总结

vlambda
2022-04-23

数据结构--【二叉树】重难点总结

知识总结

关注我

突然的灵感啊

计算机基础知识重难点总结，算法深度讲解，代码逐句刨析，python机器学习，深度学习实战，让你从理论小白进阶算法大佬，带你真正实践python

17篇原创内容

重难点

重点：

二叉树的存储结构
三种遍历算法的区别

难点：

三种遍历算法的理解和应用

二叉树的存储结构

基本知识

链式存储结构--二叉链表存储结构

lchild

data

rchild

data表示数据域，存储对应的数据元素

lchild表示左指针域，存储此元素左孩子结点的位置

rchild表示右指针域，存储此元素右孩子结点的位置

注意：叶子结点左右指针域为空NULL。

遍历算法

先序遍历

1. 二叉树为空，退出

2. 不空，则访问根节点，先序遍历左子树，先序遍历右子树。

Void Preorder(BTNode *p){   if(p != NULL){    Visit(p);          Preorder(p -> lchild);      Preorder(p -> rchild);   }}

数据结构--【二叉树】重难点总结

我们以这棵树为例，体验一下三种遍历算法。

先序遍历：

1. 树不空，访问根节点1，

2. 再先序遍历左子树（2，4，5），1的左孩子为2，2不空，访问2.

3. 再先序遍历左子树（4），2的左孩子为4，4不空，访问4.

4. 然后再访问右子树（5），2的右子树为5，左子树遍历结束。

5. 先序遍历右子树（3），右子树遍历结束，遍历完成。

遍历的顺序为：1，2，4，5，3

中序遍历

1. 二叉树为空，退出

2. 不空，则中序遍历左子树，访问根节点，中序遍历右子树。

Void inorder(BTNode *p){   if(p != NULL){         inorder(p -> lchild);      Visit(p);      inorder(p -> rchild); }}

数据结构--【二叉树】重难点总结

中序遍历：

1. 树不空，中序遍历左子树（2，4，5），1的左孩子为2。

2. 2不空，再中序遍历左子树（4），2的左孩子为4.

3. 4没有左孩子了，访问4。

4. 4的根节点为2，访问2。

5. 2的右孩子为5，访问5.

6. 访问根节点1。

7. 中序遍历右子树（3），访问3，遍历结束。

遍历的顺序为：4，2，5，1，3

后序遍历

1. 二叉树为空，退出

2. 不空，则后序遍历左子树，后序遍历右子树，访问根节点。

Void Postorder(BTNode *p){   if(p != NULL){
      Postorder(p -> lchild);      Postorder(p -> rchild);      Visit(p); }}

中序遍历：

1. 树不空，后序遍历左子树（2，4，5），1的左孩子为2。

2. 2不空，再后序遍历左子树（4），2的左孩子为4.

3. 4没有左孩子了，访问4。

4. 2的右孩子为5，访问5.

5. 4的根节点为2，访问2。

6. 后序遍历右子树（3），访问3。

7. 访问根节点1，遍历结束。

遍历的顺序为：4，5，2，3，1

END

往期回顾:

vlambda博客
学习文章列表