数据结构,用链表的方法建立二叉树, 实现二叉树的先序遍历算法。
时间: 2024-10-23 08:21:46 浏览: 12
数据结构中,利用链表构建二叉树通常涉及节点的设计和递归操作。首先,我们创建一个链表节点,它包含两个指针:一个指向左子节点(`left`),另一个指向右子节点(`right`),以及存储数据值的域(如 `val`)。对于先序遍历(根节点 -> 左子树 -> 右子树),我们可以按照以下步骤进行:
1. **创建链表节点**:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```
2. **从链表到二叉树**:
- 如果链表为空,返回None表示空树。
- 否则,选择链表的第一个节点作为根节点,并将剩余的元素分别构建其左右子树。
```python
def sortedListToBST(head):
if not head or not head.next:
return TreeNode(head.val) if head else None
slow, fast = head, head.next.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
tmp = slow.next
slow.next = None
root = TreeNode(tmp.val)
root.left = sortedListToBST(head)
root.right = sortedListToBST(tmp.next)
return root
```
3. **先序遍历算法**:
- 使用递归,首先访问当前节点,然后遍历左子树,最后遍历右子树。
```python
def preorderTraversal(root):
if not root:
return []
return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
```
阅读全文