潍坊专业做网站的公司,微场景WordPress,郑州网站哪家好,做海淘的网站要哪些证目录 一、二叉树的基本概念 1.二叉树的定义 2.二叉树的特点 3.特殊的二叉树 Ⅰ、斜树 Ⅱ、满二叉树 Ⅲ、完全二叉树 Ⅳ、完全二叉树和满二叉树的区别 4.二叉树的性质 5.二叉树的顺序存储 Ⅰ、完全二叉树 Ⅱ、非完全二叉树 Ⅲ、稀疏二叉树 6.二叉树的链式存储 7.二叉树的遍历概念… 目录 一、二叉树的基本概念 1.二叉树的定义 2.二叉树的特点 3.特殊的二叉树 Ⅰ、斜树 Ⅱ、满二叉树 Ⅲ、完全二叉树 Ⅳ、完全二叉树和满二叉树的区别 4.二叉树的性质 5.二叉树的顺序存储 Ⅰ、完全二叉树 Ⅱ、非完全二叉树 Ⅲ、稀疏二叉树 6.二叉树的链式存储 7.二叉树的遍历概念 8.二叉树的前序遍历 9.二叉树的中序遍历 10.二叉树的后序遍历 11.二叉树的层序遍历 二、Python中的二叉树 1.树的结点定义 2.树的定义 Ⅰ、初始化 Ⅱ、根据给定的结点ID从树结构中获取对应的结点 Ⅲ、访问函数打印元素结点值 Ⅳ、根据数组创建二叉树 Ⅴ、先序遍历 Ⅵ、中序遍历 Ⅶ、后序遍历 三、实战 1.144. 二叉树的前序遍历 方法一 递归 思路与算法 编辑 方法二 用栈 Stack 实现迭代遍历 思路与算法 2.94. 二叉树的中序遍历 方法一 递归 思路与算法 方法二 用栈实现迭代 思路与算法 3.145. 二叉树的后序遍历 方法一 递归 思路与算法 方法二 用栈实现迭代 思路与算法 等你读懂了相遇的意义有了隔阂别放弃 —— 25.3.8 一、二叉树的基本概念
1.二叉树的定义 二叉树是 n(n ≥ 0) 个结点组成的有限集合这个集合要么是空集当 n 等于 0 时要么是由一个根节点和两棵互不相交的二叉树组成其中这两棵互不相交的二叉树被称为根节点的左子树和右子树 如图所示2 是 1 的左子树3 是 1 的右子树同时4 和 5 分别是 2 的左右子树6 和 7分别是 3 的左右子树 2.二叉树的特点 二叉树是一种树它有如下几个特征 ① 每个结点最多二棵子树即每个结点的孩子结点个数为 0、1、2. ② 这两棵子树是有顺序的分别叫左子树 和 右子树就像左手和右手一样是不能颠倒 的。 ③ 如果只有一棵子树的情况也需要区分顺序如图所示
b 是 a 的左子树 c 是 a 的右子树 3.特殊的二叉树
Ⅰ、斜树 所有结点都只有左子树的二叉树被称为左斜树 所有结点都只有右子树的二叉树被称为右斜树 斜树有点类似 线性表所以线性表可以理解为一种特殊形式的树 Ⅱ、满二叉树 对于一棵二叉树如果它的所有根结点和内部结点都存在左右子树且所有叶子结点都在同一层这样的树就是满二叉树 满二叉树有如下几个特点 ① 叶子节点一定在最后一层 ② 非叶子结点的度为 2 ③ 深度相同的二叉树中满二叉树的结点个数最多为 2 ^ h - 1其中 h 代表树的深度 Ⅲ、完全二叉树 对一颗具有 n 个结点的二叉树按照层序进行编号如果编号 i 的结点 和 同样深度的满二叉树中的编号 i 的结点在二叉树中位置完全相同则被称为 完全二叉树 Ⅳ、完全二叉树和满二叉树的区别 满二叉树一定是完全二叉树而完全二叉树则不一定是满二叉树完全二叉树有如下几个特 点 ① 叶子结点只能出现在最下面两层 ② 最下层的叶子结点一定是集中在左边的连续位置倒数第二层如果有叶子结点一定集中在右边的连续位置 ③ 如果某个结点度为 1则只有左子树即 不存在只有右子树 的情况 ④ 同样结点数的二叉树完全二叉树的深度最小 如下图所示就不是一棵完全二叉树因为5号结点没有右子树但是6号结点是有左子树的不满足上述第 2 点。 4.二叉树的性质 ① 二叉树的第 i (i 1) 层上最多 2 ^ (i - 1) 个结点; ② 深度为 h 的二叉树至多 2 ^ h - 1 个结点; ③ n个结点的完全二叉树的深度为 floor(log2n) 1(其中 floor(x) 代表对 x 取下整); 5.二叉树的顺序存储 二叉树的顺序存储就是指利用顺序表对二叉树进行存储。结点的存储位置即顺序表的索引能够体现结点之间的逻辑关系比如父结点和孩子结点之间的关系左右兄弟结点之间的关系 等。
Ⅰ、完全二叉树 编号代表了顺序表索引的绝对位置映射后如下 为了方便将顺序表索引为 0 的位置留空 当知道某个结点在顺序表中的索引 x就可以知道它左右儿子的索引分别为 2x 和 2x 1.反之当知道某个结点的索引 x也能知道其父节点的索引为 floor(x / 2) Ⅱ、非完全二叉树 对于非完全二叉树只需要将对应不存在的结点设置为空即可 编号代表了顺序表索引的绝对位置映射后如下 Ⅲ、稀疏二叉树 对于较为稀疏的二叉树就会有如下情况出现这时候如果用这种方式进行存储就比较浪费内存了 编号代表了顺序表索引的绝对位置映射后如下 这种情况下为了提升内存利用率我们可以采用链表进行存储 6.二叉树的链式存储 二叉树每个结点至多有两个孩子结点所以对于每个结点设置一个数据域(data) 和 两个指针域(left 和 right) 即可。指针域 分别指向 左孩子结点 和 右孩子结点。 7.二叉树的遍历概念 二叉树的遍历是指从根结点出发按照某种次序依次访问二叉树中的所有结点使得每个结点访问一次且仅被访问一次。 对于线性表的遍历要么从头到尾要么从尾到头遍历方式较为单纯。但是树不一样它的每个结点都有可能有两个孩子结点所以遍历的顺序面临着不同的选择。 二叉树的常用遍历方法有以下四种前序遍历、中序遍历、后序遍历、层序遍历。 编号代表了顺序表索引的绝对位置映射后如下 8.二叉树的前序遍历 如果二叉树为空则直接返回否则先访问根结点再递归前序遍历左子树再递归前序遍历右子树。根、左、右前序遍历的结果如下a、b、d、g、h、c、e、f、i 9.二叉树的中序遍历 如果二叉树为空则直接返回否则先递归中序遍历左子树再访问根结点再递归中序遍历右子树。左、根、右中序遍历的结果如下g、d、h、b、a、e、c、i、f 10.二叉树的后序遍历 如果二叉树为空则直接返回否则先递归后遍历左子树再递归后序遍历右子树再访问根结点。左、右、根后序遍历的结果如下g、h、d、b、e、i、f、c、a 11.二叉树的层序遍历 如果二叉树为空直接返回否则依次从树的第一层开始从上至下逐层遍历在同一层中按从左到右的顺序对结点逐个访问。图中二叉树层序遍历的结果为a、b、c、d、e、f、g、h、i 二、Python中的二叉树
1.树的结点定义
val存放当前结点的value值
left存放当前节点的左孩子
right存放当前节点的右孩子
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right 2.树的定义
Ⅰ、初始化
接收参数 maxNodes传入结点最大数目
列表推导式
class Tree:def __init__(self, maxNodes):self.root Noneself.nodes [TreeNode() for i in range(maxNodes)]self.nodeSize maxNodes Ⅱ、根据给定的结点ID从树结构中获取对应的结点 # 根据给定的节点ID从树结构中获取对应的节点def GetTreeNode(self, id):return self.nodes[id] Ⅲ、访问函数打印元素结点值 # 访问函数打印元素结点的值def visit(self, node):print(node.val, end ) Ⅳ、根据数组创建二叉树 # 传入一个数组根据数组创建二叉树def Create(self, arr, size, nodeId):if nodeId size or arr[nodeId] None:return NonenowNode self.GetTreeNode(nodeId)nowNode.val arr[nodeId]nowNode.left self.Create(arr, size, 2 * nodeId)nowNode.right self.Create(arr, size, 2 * nodeId 1)return nowNodeⅤ、先序遍历 # 先序遍历def PreOrder(self, node):if node ! None:self.visit(node)self.PreOrder(node.left)self.PreOrder(node.right)def preOrderTraversal(self):self.PreOrder(self.root)print() Ⅵ、中序遍历 # 中序遍历def InOrder(self, node):if node ! None:self.InOrder(node.left)self.visit(node)self.InOrder(node.right)def InOrderTraversal(self):self.InOrder(self.root)print() Ⅶ、后序遍历 # 后序遍历def PostOrder(self, node):if node ! None:self.PostOrder(node.left)self.PostOrder(node.right)self.visit(node)def PostTraversal(self):self.PostOrder(self.root)print() Ⅷ、测试代码
def Test():arr [None, a, b, c, d, None, e, f, g, h, None, None, None, None, i]tree Tree(len(arr))tree.CreateTree(arr)tree.preOrderTraversal()tree.InOrderTraversal()tree.PostTraversal()Test() 三、实战
1.144. 二叉树的前序遍历 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1 输入root [1,null,2,3] 输出[1,2,3] 解释 示例 2 输入root [1,2,3,4,5,null,8,null,null,6,7,9] 输出[1,2,4,5,6,7,3,8,9] 解释 示例 3 输入root [] 输出[] 示例 4 输入root [1] 输出[1] 提示 树中节点数目在范围 [0, 100] 内-100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗 方法一 递归
思路与算法
前序遍历遵循“根 - 左 - 右”的顺序。递归函数 preorder 的核心逻辑是 如果当前节点 root 不为空则将其值加入结果列表 ret。递归遍历左子树。递归遍历右子树。 递归终止条件是当前节点为空root is None此时直接返回。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def preorder(self, root:Optional[TreeNode], ret:List[int]):if root:ret.append(root.val)self.preorder(root.left, ret)self.preorder(root.right, ret)def preorderTraversal(self, root: Optional[TreeNode]) - List[int]:ret []self.preorder(root, ret)return ret 方法二 用栈 Stack 实现迭代遍历
思路与算法
前序遍历遵循“根 - 左 - 右”的顺序。使用栈来模拟递归的过程 从根节点开始将当前节点的值加入结果列表 res并将当前节点入栈。遍历左子树直到左子树为空。回溯到上一个节点通过栈弹出并遍历其右子树。 重复上述过程直到栈为空且当前节点为空。 2.94. 二叉树的中序遍历 给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 示例 1 输入root [1,null,2,3]
输出[1,3,2]示例 2 输入root []
输出[]示例 3 输入root [1]
输出[1]提示 树中节点数目在范围 [0, 100] 内-100 Node.val 100 进阶: 递归算法很简单你可以通过迭代算法完成吗 方法一 递归
思路与算法
后序遍历遵循“左 - 右 - 根”的顺序。递归函数 PostOrder 的核心逻辑是 如果当前节点 root 不为空则递归遍历其左子树。递归遍历其右子树。将当前节点的值加入结果列表 res。 递归终止条件是当前节点为空root is None此时直接返回。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def PostOrder(self, root:Optional[TreeNode], res:List[int]):if root:self.PostOrder(root.left, res)self.PostOrder(root.right, res)res.append(root.val)def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []self.PostOrder(root, res)return res 方法二 用栈实现迭代
思路与算法
中序遍历遵循“左 - 根 - 右”的顺序。使用栈来模拟递归的过程 从根节点开始将当前节点入栈并遍历其左子树直到左子树为空。回溯到上一个节点通过栈弹出将其值加入结果列表 res。遍历其右子树。 重复上述过程直到栈为空且当前节点为空。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:res, stack [], []while root or stack:if root:stack.append(root)root root.leftelse: root stack.pop()res.append(root.val)root root.rightreturn res 3.145. 二叉树的后序遍历 给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1 输入root [1,null,2,3] 输出[3,2,1] 解释 示例 2 输入root [1,2,3,4,5,null,8,null,null,6,7,9] 输出[4,6,7,5,2,9,8,3,1] 解释 示例 3 输入root [] 输出[] 示例 4 输入root [1] 输出[1] 提示 树中节点的数目在范围 [0, 100] 内-100 Node.val 100 进阶递归算法很简单你可以通过迭代算法完成吗 方法一 递归
思路与算法
后序遍历遵循“左 - 右 - 根”的顺序。递归函数 postOrder 的核心逻辑是 如果当前节点 root 不为空则递归遍历其左子树。递归遍历其右子树。将当前节点的值加入结果列表 res。 递归终止条件是当前节点为空root is None此时直接返回。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def postOrder(self, root:TreeNode, res):if root is None:returnself.postOrder(root.left, res)self.postOrder(root.right, res)res.append(root.val)def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []self.postOrder(root, res)return res 方法二 用栈实现迭代
思路与算法
后序遍历遵循“左 - 右 - 根”的顺序。使用栈来模拟递归的过程 从根节点开始将当前节点入栈并遍历其左子树直到左子树为空。如果左子树为空则遍历其右子树。回溯到上一个节点通过栈弹出将其值加入结果列表 res。如果当前节点是栈顶节点的左子节点则继续遍历栈顶节点的右子树否则结束当前分支的遍历。 重复上述过程直到栈为空且当前节点为空。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []stack []node rootwhile stack or node:while node:stack.append(node)if node.left ! None:node node.leftelse:node node.rightnode stack.pop()res.append(node.val)if stack and stack[-1].left node:node stack[-1].rightelse:node Nonereturn res
文章转载自： http://www.morning.sgpny.cn.gov.cn.sgpny.cn http://www.morning.pfkrw.cn.gov.cn.pfkrw.cn http://www.morning.dmzzt.cn.gov.cn.dmzzt.cn http://www.morning.kgslc.cn.gov.cn.kgslc.cn http://www.morning.ctsjq.cn.gov.cn.ctsjq.cn http://www.morning.khyqt.cn.gov.cn.khyqt.cn http://www.morning.rqjxc.cn.gov.cn.rqjxc.cn http://www.morning.fdhwh.cn.gov.cn.fdhwh.cn http://www.morning.kfhm.cn.gov.cn.kfhm.cn http://www.morning.frtb.cn.gov.cn.frtb.cn http://www.morning.lrzst.cn.gov.cn.lrzst.cn http://www.morning.qkrgk.cn.gov.cn.qkrgk.cn http://www.morning.lgtcg.cn.gov.cn.lgtcg.cn http://www.morning.crdtx.cn.gov.cn.crdtx.cn http://www.morning.yzmzp.cn.gov.cn.yzmzp.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.mpflb.cn.gov.cn.mpflb.cn http://www.morning.nfbxgtj.com.gov.cn.nfbxgtj.com http://www.morning.zkqjz.cn.gov.cn.zkqjz.cn http://www.morning.jjrsk.cn.gov.cn.jjrsk.cn http://www.morning.bgygx.cn.gov.cn.bgygx.cn http://www.morning.wnqbf.cn.gov.cn.wnqbf.cn http://www.morning.cbmqq.cn.gov.cn.cbmqq.cn http://www.morning.gbgdm.cn.gov.cn.gbgdm.cn http://www.morning.gcysq.cn.gov.cn.gcysq.cn http://www.morning.bztzm.cn.gov.cn.bztzm.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.xjbtb.cn.gov.cn.xjbtb.cn http://www.morning.sjqpm.cn.gov.cn.sjqpm.cn http://www.morning.xlmgq.cn.gov.cn.xlmgq.cn http://www.morning.xlndf.cn.gov.cn.xlndf.cn http://www.morning.bwttj.cn.gov.cn.bwttj.cn http://www.morning.ldsgm.cn.gov.cn.ldsgm.cn http://www.morning.rhdln.cn.gov.cn.rhdln.cn http://www.morning.cwwts.cn.gov.cn.cwwts.cn http://www.morning.rrqbm.cn.gov.cn.rrqbm.cn http://www.morning.bgygx.cn.gov.cn.bgygx.cn http://www.morning.mqwdh.cn.gov.cn.mqwdh.cn http://www.morning.lmdkn.cn.gov.cn.lmdkn.cn http://www.morning.tbzcl.cn.gov.cn.tbzcl.cn http://www.morning.kzhgy.cn.gov.cn.kzhgy.cn http://www.morning.flpjy.cn.gov.cn.flpjy.cn http://www.morning.qnhpq.cn.gov.cn.qnhpq.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.pflpb.cn.gov.cn.pflpb.cn http://www.morning.crkhd.cn.gov.cn.crkhd.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.rfljb.cn.gov.cn.rfljb.cn http://www.morning.kdnrc.cn.gov.cn.kdnrc.cn http://www.morning.mzrqj.cn.gov.cn.mzrqj.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.yrqb.cn.gov.cn.yrqb.cn http://www.morning.wkhfg.cn.gov.cn.wkhfg.cn http://www.morning.tndxg.cn.gov.cn.tndxg.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.tbcfj.cn.gov.cn.tbcfj.cn http://www.morning.rwzkp.cn.gov.cn.rwzkp.cn http://www.morning.fwllb.cn.gov.cn.fwllb.cn http://www.morning.ttxnj.cn.gov.cn.ttxnj.cn http://www.morning.yfddl.cn.gov.cn.yfddl.cn http://www.morning.pkrtz.cn.gov.cn.pkrtz.cn http://www.morning.rhwty.cn.gov.cn.rhwty.cn http://www.morning.rnrwq.cn.gov.cn.rnrwq.cn http://www.morning.rlnm.cn.gov.cn.rlnm.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.jthjr.cn.gov.cn.jthjr.cn http://www.morning.cryb.cn.gov.cn.cryb.cn http://www.morning.kkqgf.cn.gov.cn.kkqgf.cn http://www.morning.yqsr.cn.gov.cn.yqsr.cn http://www.morning.wfhnz.cn.gov.cn.wfhnz.cn http://www.morning.yjqkk.cn.gov.cn.yjqkk.cn http://www.morning.wrtpk.cn.gov.cn.wrtpk.cn http://www.morning.rycbz.cn.gov.cn.rycbz.cn http://www.morning.lqgtx.cn.gov.cn.lqgtx.cn http://www.morning.twfdm.cn.gov.cn.twfdm.cn http://www.morning.gmplp.cn.gov.cn.gmplp.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn http://www.morning.kkgbs.cn.gov.cn.kkgbs.cn
