二叉树一. 斐波那契数列先来看看递归版的斐波那契函数:intfib(intn){if(n1||n2){return1;}else{returnfib(n-1)fib(n-2);}}那它与二叉树有什么关系呢让我们通过递归调用的过程来分析。当我们调用fib(n)时函数会分解为两个子问题fib(n-1)和fib(n-2)。这种分解过程会持续进行直到遇到基准情况n1或n2。不妨看看这张图它展示了fib(6)的递归调用过程从图中可以清晰地看到每个函数调用对应一个节点fib(n)的两个递归调用fib(n-1)和fib(n-2)分别对应节点的左子树和右子树基准情况n1或n2对应树的叶子节点所以这个递归函数fib的执行过程实际上构造了一个二叉树结构二. 二叉树的基本知识什么是二叉树结合上面的斐波那契函数我们可以看到递归调用形成了一个树形结构。二叉树正是这样一种数据结构每个节点最多有两个子节点左子节点和右子节点就像fib函数中每个调用会产生两个新的递归调用一样。再来看看二叉树的结构二叉树的基本性质在二叉树的第i层上至多有2^(i-1)个节点i1深度为k的二叉树至多有2^k-1个节点k1对任何一棵二叉树T如果其终端节点数为 n0度为2的节点数为 n2则 n0 n21三. 常见二叉树的分类1. 完美二叉树 何为完美二叉树完美二叉树是指所有叶子节点都在同一层且每个非叶子节点都有两个子节点的二叉树。也就是说完美二叉树的每一层都是满的具有以下特点所有叶子节点都在同一深度每个非叶子节点都有恰好两个子节点第i层有2^(i-1)个节点深度为k的完美二叉树共有2^k-1个节点需要注意的是完美二叉树和满二叉树是两个不同的概念 满二叉树 (Full Binary Tree)每个节点要么有0个子节点叶子节点要么有2个子节点 完美二叉树 (Perfect Binary Tree)所有叶子节点都在同一层且每个非叶子节点都有两个子节点2. 完全二叉树何为完全二叉树完全二叉树是指除了最后一层外其他层的节点数都达到最大并且最后一层的节点都集中在该层最左边的若干位置上在最后一层的最右边的若干位置上可能缺少若干叶子节点。四. 二叉树的遍历常见的遍历方法有三种前序遍历中序遍历后序遍历我们先建立一棵简单的二叉树1. 前序遍历遍历的顺序为根节点-左子树-右子树在上面的那棵树中节点的访问顺序就是1-2-32. 中序遍历遍历的顺序为左子树-根节点-右子树在上面的那棵树中节点的访问顺序就是2-1-33. 后序遍历遍历的顺序为左子树-右子树-根节点在上面的那棵树中节点的访问顺序就是2-3-1再来举个例子 有一个如下图的二叉树它的节点的前序遍历顺序是1 2 4 5 3中序遍历顺序是4 2 5 1 3后序遍历顺序就是4 5 2 3 1这是我在学习过程中的个人笔记整理旨在记录和分享对二叉树相关概念的理解。内容可能存在理解不准确或表述不当之处仅供参考如有错误欢迎指正。