将二叉树转换为完整二叉树的功能？
Function to convert binary tree to full Binary tree?
二叉树的实现如下。
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
图片中给出的树不是完整的二叉树。如何编写一个函数将上面的二叉树转换为完整的二叉树，只需将字符串数据节点添加到没有子节点的节点即可生成完整的二叉树。
手动我将在代码中添加节点以获得这样的结果树：
root.left.right = Node('a')
root.right.left = Node('a')
root.right.left.left = Node('a')
root.right.left.right = Node('a')
root.left.right.right = Node('a')
root.left.right.left = Node('a')
但是如何编写一个函数来获取根节点和 return 满二叉树的树。
首先，获取树的高度。那将是整棵树的高度。接下来，遍历树，对于每个节点，如果其深度小于树的高度，并且它的左侧或右侧 child （或两者）缺失，则添加缺失的部分，然后继续遍历。因此，对于您的输入，流程将进行
5 h=0
=> 2 h=1
=> 7 h=2
=> 9 h=3
=> 3 h=1
=> 1 h=2
=> 4 h=3
=> 6 h=3
max height seen was 3, so height of tree is 3
5 h < 3, has both children, nothing to add
=> 2 h < 3, missing right child, add 'a'
=> 7 h < 3, missing right child, add 'b'
=> 9 h = 3, nothing to add
=> b h = 3, nothing to add
=> a h < 3, missing left and right children, add 'c' and 'd'
=> c h = 3, nothing to add
=> d h = 3, nothing to add
=> 3 h < 3, missing left child, add 'e'
=> e h < 3, missing left and right children, add 'f' and 'g'
=> f h = 3, nothing to add
=> g h = 3, nothing to add
=> 1 h < 3, has both children, nothing to add
=> 4 h = 3, nothing to add
=> 6 h = 3, nothing to add
所以我们看到这添加了您手动添加的相同节点（您实际上可能错过了一个，7 在您的绘图中只有一个 child）。我们将它们标记为 a、b、c、d、e、f 和 g，但您可以编写代码，以便为它们提供相同的字符串。
您将需要创建一种方法，使您可以在树中获得最大深度。从那里你可以添加一个方法来递归地将空节点添加到该深度：
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
@property
def maxDepth(self): # compute maximum depth (i.e. levels under self)
depth = 0
if self.left: depth = self.left.maxDepth+1
if self.right: depth = max(depth,self.right.maxDepth+1)
return depth
def expandToDepth(self,depth=None): # add empty nodes to fill tree
if depth is None: depth = self.maxDepth
if not depth: return
if not self.left: self.left = Node(None)
if not self.right: self.right = Node(None)
self.left.expandToDepth(depth-1)
self.right.expandToDepth(depth-1)
def __repr__(self): # this is just to print the tree
nodeInfo = lambda n: (str(n.data or "?"),n.left,n.right)
return "\n".join(printBTree(self,nodeInfo,isTop=False))
输出：
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
## BEFORE ##
print(root)
5
/ \
2 3
/ \
7 1
/ / \
9 4 6
root.expandToDepth()
## AFTER ##
print(root)
5
_____/ \_____
2 3
__/ \_ __/ \_
7 ? ? 1
/ \ / \ / \ / \
9 ? ? ? ? ? 4 6
printBTree() 是我提供的函数，作为对另一个问题的回答：
这是它的副本（以防 link 消失）：
import functools as fn
def printBTree(node, nodeInfo=None, inverted=False, isTop=True):
# node value string and sub nodes
stringValue, leftNode, rightNode = nodeInfo(node)
stringValueWidth = len(stringValue)
# recurse to sub nodes to obtain line blocks on left and right
leftTextBlock = [] if not leftNode else printBTree(leftNode,nodeInfo,inverted,False)
rightTextBlock = [] if not rightNode else printBTree(rightNode,nodeInfo,inverted,False)
# count common and maximum number of sub node lines
commonLines = min(len(leftTextBlock),len(rightTextBlock))
subLevelLines = max(len(rightTextBlock),len(leftTextBlock))
# extend lines on shallower side to get same number of lines on both sides
leftSubLines = leftTextBlock + [""] * (subLevelLines - len(leftTextBlock))
rightSubLines = rightTextBlock + [""] * (subLevelLines - len(rightTextBlock))
# compute location of value or link bar for all left and right sub nodes
# * left node's value ends at line's width
# * right node's value starts after initial spaces
leftLineWidths = [ len(line) for line in leftSubLines ]
rightLineIndents = [ len(line)-len(line.lstrip(" ")) for line in rightSubLines ]
# top line value locations, will be used to determine position of current node & link bars
firstLeftWidth = (leftLineWidths + [0])[0]
firstRightIndent = (rightLineIndents + [0])[0]
# width of sub node link under node value (i.e. with slashes if any)
# aims to center link bars under the value if value is wide enough
#
# ValueLine: v vv vvvvvv vvvvv
# LinkLine: / \ / \ / \ / \
#
linkSpacing = min(stringValueWidth, 2 - stringValueWidth % 2)
leftLinkBar = 1 if leftNode else 0
rightLinkBar = 1 if rightNode else 0
minLinkWidth = leftLinkBar + linkSpacing + rightLinkBar
valueOffset = (stringValueWidth - linkSpacing) // 2
# find optimal position for right side top node
# * must allow room for link bars above and between left and right top nodes
# * must not overlap lower level nodes on any given line (allow gap of minSpacing)
# * can be offset to the left if lower subNodes of right node
# have no overlap with subNodes of left node
minSpacing = 2
rightNodePosition = fn.reduce(lambda r,i: max(r,i[0] + minSpacing + firstRightIndent - i[1]), \
zip(leftLineWidths,rightLineIndents[0:commonLines]), \
firstLeftWidth + minLinkWidth)
# extend basic link bars (slashes) with underlines to reach left and right
# top nodes.
#
# vvvvv
# __/ \__
# L R
#
linkExtraWidth = max(0, rightNodePosition - firstLeftWidth - minLinkWidth )
rightLinkExtra = linkExtraWidth // 2
leftLinkExtra = linkExtraWidth - rightLinkExtra
# build value line taking into account left indent and link bar extension (on left side)
valueIndent = max(0, firstLeftWidth + leftLinkExtra + leftLinkBar - valueOffset)
valueLine = " " * max(0,valueIndent) + stringValue
slash = "\" if inverted else "/"
backslash = "/" if inverted else "\"
uLine = "¯" if inverted else "_"
# build left side of link line
leftLink = "" if not leftNode else ( " " * firstLeftWidth + uLine * leftLinkExtra + slash)
# build right side of link line (includes blank spaces under top node value)
rightLinkOffset = linkSpacing + valueOffset * (1 - leftLinkBar)
rightLink = "" if not rightNode else ( " " * rightLinkOffset + backslash + uLine * rightLinkExtra )
# full link line (will be empty if there are no sub nodes)
linkLine = leftLink + rightLink
# will need to offset left side lines if right side sub nodes extend beyond left margin
# can happen if left subtree is shorter (in height) than right side subtree
leftIndentWidth = max(0,firstRightIndent - rightNodePosition)
leftIndent = " " * leftIndentWidth
indentedLeftLines = [ (leftIndent if line else "") + line for line in leftSubLines ]
# compute distance between left and right sublines based on their value position
# can be negative if leading spaces need to be removed from right side
mergeOffsets = [ len(line) for line in indentedLeftLines ]
mergeOffsets = [ leftIndentWidth + rightNodePosition - firstRightIndent - w for w in mergeOffsets ]
mergeOffsets = [ p if rightSubLines[i] else 0 for i,p in enumerate(mergeOffsets) ]
# combine left and right lines using computed offsets
# * indented left sub lines
# * spaces between left and right lines
# * right sub line with extra leading blanks removed.
mergedSubLines = zip(range(len(mergeOffsets)), mergeOffsets, indentedLeftLines)
mergedSubLines = [ (i,p,line + (" " * max(0,p)) ) for i,p,line in mergedSubLines ]
mergedSubLines = [ line + rightSubLines[i][max(0,-p):] for i,p,line in mergedSubLines ]
# Assemble final result combining
# * node value string
# * link line (if any)
# * merged lines from left and right sub trees (if any)
treeLines = [leftIndent + valueLine] + ( [] if not linkLine else [leftIndent + linkLine] ) + mergedSubLines
# invert final result if requested
treeLines = reversed(treeLines) if inverted and isTop else treeLines
# return intermediate tree lines or print final result
if isTop : print("\n".join(treeLines))
else : return treeLines
二叉树的实现如下。
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
图片中给出的树不是完整的二叉树。如何编写一个函数将上面的二叉树转换为完整的二叉树，只需将字符串数据节点添加到没有子节点的节点即可生成完整的二叉树。
手动我将在代码中添加节点以获得这样的结果树：
root.left.right = Node('a')
root.right.left = Node('a')
root.right.left.left = Node('a')
root.right.left.right = Node('a')
root.left.right.right = Node('a')
root.left.right.left = Node('a')
但是如何编写一个函数来获取根节点和 return 满二叉树的树。
首先，获取树的高度。那将是整棵树的高度。接下来，遍历树，对于每个节点，如果其深度小于树的高度，并且它的左侧或右侧 child （或两者）缺失，则添加缺失的部分，然后继续遍历。因此，对于您的输入，流程将进行
5 h=0
=> 2 h=1
=> 7 h=2
=> 9 h=3
=> 3 h=1
=> 1 h=2
=> 4 h=3
=> 6 h=3
max height seen was 3, so height of tree is 3
5 h < 3, has both children, nothing to add
=> 2 h < 3, missing right child, add 'a'
=> 7 h < 3, missing right child, add 'b'
=> 9 h = 3, nothing to add
=> b h = 3, nothing to add
=> a h < 3, missing left and right children, add 'c' and 'd'
=> c h = 3, nothing to add
=> d h = 3, nothing to add
=> 3 h < 3, missing left child, add 'e'
=> e h < 3, missing left and right children, add 'f' and 'g'
=> f h = 3, nothing to add
=> g h = 3, nothing to add
=> 1 h < 3, has both children, nothing to add
=> 4 h = 3, nothing to add
=> 6 h = 3, nothing to add
所以我们看到这添加了您手动添加的相同节点（您实际上可能错过了一个，7 在您的绘图中只有一个 child）。我们将它们标记为 a、b、c、d、e、f 和 g，但您可以编写代码，以便为它们提供相同的字符串。
您将需要创建一种方法，使您可以在树中获得最大深度。从那里你可以添加一个方法来递归地将空节点添加到该深度：
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
@property
def maxDepth(self): # compute maximum depth (i.e. levels under self)
depth = 0
if self.left: depth = self.left.maxDepth+1
if self.right: depth = max(depth,self.right.maxDepth+1)
return depth
def expandToDepth(self,depth=None): # add empty nodes to fill tree
if depth is None: depth = self.maxDepth
if not depth: return
if not self.left: self.left = Node(None)
if not self.right: self.right = Node(None)
self.left.expandToDepth(depth-1)
self.right.expandToDepth(depth-1)
def __repr__(self): # this is just to print the tree
nodeInfo = lambda n: (str(n.data or "?"),n.left,n.right)
return "\n".join(printBTree(self,nodeInfo,isTop=False))
输出：
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
## BEFORE ##
print(root)
5
/ \
2 3
/ \
7 1
/ / \
9 4 6
root.expandToDepth()
## AFTER ##
print(root)
5
_____/ \_____
2 3
__/ \_ __/ \_
7 ? ? 1
/ \ / \ / \ / \
9 ? ? ? ? ? 4 6
printBTree() 是我提供的函数，作为对另一个问题的回答：
这是它的副本（以防 link 消失）：
import functools as fn
def printBTree(node, nodeInfo=None, inverted=False, isTop=True):
# node value string and sub nodes
stringValue, leftNode, rightNode = nodeInfo(node)
stringValueWidth = len(stringValue)
# recurse to sub nodes to obtain line blocks on left and right
leftTextBlock = [] if not leftNode else printBTree(leftNode,nodeInfo,inverted,False)
rightTextBlock = [] if not rightNode else printBTree(rightNode,nodeInfo,inverted,False)
# count common and maximum number of sub node lines
commonLines = min(len(leftTextBlock),len(rightTextBlock))
subLevelLines = max(len(rightTextBlock),len(leftTextBlock))
# extend lines on shallower side to get same number of lines on both sides
leftSubLines = leftTextBlock + [""] * (subLevelLines - len(leftTextBlock))
rightSubLines = rightTextBlock + [""] * (subLevelLines - len(rightTextBlock))
# compute location of value or link bar for all left and right sub nodes
# * left node's value ends at line's width
# * right node's value starts after initial spaces
leftLineWidths = [ len(line) for line in leftSubLines ]
rightLineIndents = [ len(line)-len(line.lstrip(" ")) for line in rightSubLines ]
# top line value locations, will be used to determine position of current node & link bars
firstLeftWidth = (leftLineWidths + [0])[0]
firstRightIndent = (rightLineIndents + [0])[0]
# width of sub node link under node value (i.e. with slashes if any)
# aims to center link bars under the value if value is wide enough
#
# ValueLine: v vv vvvvvv vvvvv
# LinkLine: / \ / \ / \ / \
#
linkSpacing = min(stringValueWidth, 2 - stringValueWidth % 2)
leftLinkBar = 1 if leftNode else 0
rightLinkBar = 1 if rightNode else 0
minLinkWidth = leftLinkBar + linkSpacing + rightLinkBar
valueOffset = (stringValueWidth - linkSpacing) // 2
# find optimal position for right side top node
# * must allow room for link bars above and between left and right top nodes
# * must not overlap lower level nodes on any given line (allow gap of minSpacing)
# * can be offset to the left if lower subNodes of right node
# have no overlap with subNodes of left node
minSpacing = 2
rightNodePosition = fn.reduce(lambda r,i: max(r,i[0] + minSpacing + firstRightIndent - i[1]), \
zip(leftLineWidths,rightLineIndents[0:commonLines]), \
firstLeftWidth + minLinkWidth)
# extend basic link bars (slashes) with underlines to reach left and right
# top nodes.
#
# vvvvv
# __/ \__
# L R
#
linkExtraWidth = max(0, rightNodePosition - firstLeftWidth - minLinkWidth )
rightLinkExtra = linkExtraWidth // 2
leftLinkExtra = linkExtraWidth - rightLinkExtra
# build value line taking into account left indent and link bar extension (on left side)
valueIndent = max(0, firstLeftWidth + leftLinkExtra + leftLinkBar - valueOffset)
valueLine = " " * max(0,valueIndent) + stringValue
slash = "\" if inverted else "/"
backslash = "/" if inverted else "\"
uLine = "¯" if inverted else "_"
# build left side of link line
leftLink = "" if not leftNode else ( " " * firstLeftWidth + uLine * leftLinkExtra + slash)
# build right side of link line (includes blank spaces under top node value)
rightLinkOffset = linkSpacing + valueOffset * (1 - leftLinkBar)
rightLink = "" if not rightNode else ( " " * rightLinkOffset + backslash + uLine * rightLinkExtra )
# full link line (will be empty if there are no sub nodes)
linkLine = leftLink + rightLink
# will need to offset left side lines if right side sub nodes extend beyond left margin
# can happen if left subtree is shorter (in height) than right side subtree
leftIndentWidth = max(0,firstRightIndent - rightNodePosition)
leftIndent = " " * leftIndentWidth
indentedLeftLines = [ (leftIndent if line else "") + line for line in leftSubLines ]
# compute distance between left and right sublines based on their value position
# can be negative if leading spaces need to be removed from right side
mergeOffsets = [ len(line) for line in indentedLeftLines ]
mergeOffsets = [ leftIndentWidth + rightNodePosition - firstRightIndent - w for w in mergeOffsets ]
mergeOffsets = [ p if rightSubLines[i] else 0 for i,p in enumerate(mergeOffsets) ]
# combine left and right lines using computed offsets
# * indented left sub lines
# * spaces between left and right lines
# * right sub line with extra leading blanks removed.
mergedSubLines = zip(range(len(mergeOffsets)), mergeOffsets, indentedLeftLines)
mergedSubLines = [ (i,p,line + (" " * max(0,p)) ) for i,p,line in mergedSubLines ]
mergedSubLines = [ line + rightSubLines[i][max(0,-p):] for i,p,line in mergedSubLines ]
# Assemble final result combining
# * node value string
# * link line (if any)
# * merged lines from left and right sub trees (if any)
treeLines = [leftIndent + valueLine] + ( [] if not linkLine else [leftIndent + linkLine] ) + mergedSubLines
# invert final result if requested
treeLines = reversed(treeLines) if inverted and isTop else treeLines
# return intermediate tree lines or print final result
if isTop : print("\n".join(treeLines))
else : return treeLines