##二叉树基本定义

​ img

定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成

特点

1）每个结点最多有两颗子树
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

二叉树遍历

1
2
3
#判断当前节点是否为空
#执行当前节点操作
#执行左右子树操作

1.前序遍历

前序遍历执行的是中左右的遍历原则，即先遍历中间的根节点，然后左节点，最后右节点。

1
2
3
4
5
6
7
8
9
def preorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        tree.append(node.val)
        helper(node.left)
        helper(node.right)
    helper(root)
    return tree

2.中序遍历

中序遍历执行的是左中右的遍历原则，即先遍历中间的左节点，然后中间节点，最后右节点

1
2
3
4
5
6
7
8
9
def innerorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        tree.append(node.val)
        helper(node.right)
    helper(root)
    return tree

3.后序遍历

后序遍历执行的是左右中的遍历原则，即先遍历中间的左节点，然后右节点，最后中节点。

1
2
3
4
5
6
7
8
9
def postorderTraversal(root):
    tree = []
    def helper(node):
        if not node: return 
        helper(node.left)
        helper(node.right)
        tree.append(node.val)
    helper(root)
    return tree

4.总结规律

基于以上代码可见，二叉树的遍历基本的代码框架如下：

1
2
3
4
5
6
7
8
def Traversal(root):
    tree = []
    def helper(node):
        #判断当前节点是否为空
        #执行当前节点操作
        #执行左右子树操作
    helper(root)
    return tree

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:

文章作者:imlch

发布时间:2020年09月19日 - 19时22分

最后更新:2020年09月19日 - 20时21分

原始链接:http://blog.imlch.cn/2020/09/19/二叉树解题模板/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 定义
  2. 2. 特点
  3. 3. 二叉树遍历
  4. 4. 1.前序遍历
  5. 5. 2.中序遍历
  6. 6. 3.后序遍历
  7. 7. 4.总结规律
,