两个链表的第一个节点怎么找 为什么链表无法知道前一个节点？
为什么链表无法知道前一个节点？
如果你知道链表的头指针，你可以从头指针开始向后遍历。记录下一个节点地址和上一个节点地址。如果当前节点地址与指定的节点地址相同，则找到前一个节点。
为什么链表的每个节点中都恰好包含一个指针？
链表的每个节点恰好包含一个指针是错误的。
链表包括单链表和双链表，双链表实际上是单链表的改进。
链表中的每个节点可以包含多个指针字段，分别存储多个指针。例如，双向链表中的一个节点可以包含两个指针字段，分别存储指向其直接前任和直接继任者的指针。
如何判断两个链表是否相交，以及交点？
方法一:直接判断第一个链表的每个节点是否在第二个链表中，时间复杂度为O(l
顺序存储的二叉树是如何创建和遍历的？
首先，简单介绍一下什么是a "二叉树 "。二叉树是n个节点的有限集合，其定义是递归的:
(1)n0时，为空树；
(2)n1时，只有一个节点，称为根节点；
(ngt1时，除根节点外的其他节点可以分成两个不相交的子集，称为左右子树，左右子树本质上也是二叉树。
图1二叉树
根据二叉树的结构和定义，二叉树的特征可以概括为:
(1)非空二叉树的第一层最多有2∧(i-1)个节点；
(2)深度为k的二叉树最多有2∧k-1个节点。
二叉树二叉树的存储结构是非线性结构，每个节点最多有一个 "前任 "，但它可以有多个 "接班人 "。它可以采用顺序存储结构和链式存储结构。
1.顺序存储结构
二叉树的顺序存储是用一组连续的存储单元来存储二叉树的节点。二叉树的所有节点必须排列成适当的序列，节点在这个序列中的相互位置可以反映节点之间的逻辑关系。
要介绍顺序存储结构，首先要了解一个概念——完全二叉树。如果深度为k，当k和n满足2∧(k-1)≦n≦2∧k-1时，一棵有n个节点的二叉树称为完全二叉树。
对于二叉树，如果不是完全二叉树，先添加一些不存在的空节点使之成为完全二叉树，然后将树中的节点按照从上到下，从左到右的顺序存储在数组中。
以图1为例，补充成如图2所示的完整二叉树。
图2完成后的二叉树
其顺序存储状态为:
a B C D E∧H∧F G I显然，当一棵不完全二叉树采用顺序存储结构时，需要添加许多空节点，因为这样会造成很大的空间浪费。
2.链式存储结构
二叉树的链式存储结构是指用链式表示的二叉树节点之间的逻辑关系。
通常的方法是链表中的每个节点由三个域组成:
左指针字段数据字段右指针字段，即Lchild数据Rchild，其中:数据字段存储节点的数据信息；Lchild和Rchild分别存储左右分支的指针。当分支不存在时，相应的指针字段为空(用符号∧ NULL表示)。与图1中的节点C一样，因为它的左分支不存在，所以它的Lchild值为NULL。
三、二叉树的遍历算法二叉树常见的遍历方法有:前序遍历、中间遍历、后继遍历和顺序遍历。
1.前序遍历
首先访问根节点，然后是左边的子树，最后是右边的子树。
图1中前序遍历的结果是:
a-gt b-gtD-gtE-gtF-gtG-gtC-gtH-gtI
2.中序遍历
首先访问左边的子树，然后是根节点，最后是右边的子树。
图1中中间序列遍历的结果是:
d-gtB-gtF-gtE-gtG-gtA-gtC-gtI-gtH
3.后续遍历
首先访问左边的子树，然后是右边的子树，最后是根节点。
图1中后续遍历的结果是:
d-gtgtF-gtG-gtE-gti-gtH-gt b-gtC-gtA
4.序列遍历
从顶层节点开始，依次从左到右遍历，然后到第二层，继续从左到右遍历，…直到遍历完所有节点。
图1中的序列遍历结果如下:
a-gt b-gtC-gt D-gtE-gtH-gtF-gtG-gtI
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
