提到可以对链表数据结构进行的 2 个修改,以便将其转换为二叉树数据结构?
问问题
125 次
2 回答
1
这个问题相当模糊,但这就是我认为它可能的意思。
链表中使用的结构将有一个next
指针:
struct LinkedListNode {
LinkedListNode *next;
// data element(s)
};
二叉树中使用的结构将具有left
和right
指针:
struct BinaryTreeNode {
BinaryTreeNode *left;
BinaryTreeNode *right;
// data element(s)
}
所以,我猜这个问题所指的两个修改可能是:
- 将
next
指针改为left
指针 - 添加
right
指针
于 2013-09-01T04:47:11.580 回答
0
我没有得到“2修改”的意思,但是要将 a 转换LinkedList
为 a BinaryTree
,我们可以遵循两种方法
- 自下而上
- 自顶向下
1) 自上而下的方法:
在这种方法中,我们可以将两个子列表分为LinkedList
两个子列表,中间元素将是父节点,每个子节点都调用此递归方法,用于左右子列表。
这背后的基本逻辑可以是,
ListToBinaryTree(LinkedList list, int start, int end) {
mid -> start + (end - start) / 2;
left -> ListToBinaryTree(list, start, mid-1);
right -> ListToBinaryTree(list, mid+1, end);
}
2) 自下而上的方法:
在这种方法中,我们将首先创建子元素,然后再创建父元素。
这背后的基本逻辑可以是,
ListToBinaryTree(ListNode *& list, int start, int end) {
mid -> start + (end - start) / 2;
leftChild -> ListToBinaryTree(list, start, mid-1);
parent -> new BinaryTree(list -> data);
parent -> left = leftChild;
list = list -> next;
parent -> right = ListToBinaryTree(list, mid+1, end);
}
希望这会有用。
于 2013-11-08T09:40:34.180 回答