求助python（关于树与二叉树的两道题） - 编程论坛

#2

TysonKoothra2019-05-05 11:25

我回答第一个问题
def leaf_count(t):
    length = len(t)
    return length - length // 2

class Tree:
    def __init__(self, s=[]):
        self.storage = s

    def __len__(self):
        return len(self.storage)

if __name__ == "__main__":
    t = Tree(['a', 'b', 'c', 'd'])
    print(leaf_count(t))

#3

Ⅳ飒2019-05-05 19:41

回复楼主 Ⅳ飒

我答第二题
class Node(object):
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

def trans(a,i,n): #n是以顺序存储元素个数
    if (i>n):
        return None
    b=Node(a[i-1])
    if b.elem=='#':
        return None
    b.lchild=trans(a,2*i,n)
    b.rchild=trans(a,2*i+1,n)
    return b

def isCBTree(root):
    if not root:
        return False
    queue = [root]
    result = True
    hasNoChild=False
    while queue:
        cur=queue.pop(0)
        if hasNoChild:
            if cur.lchild or cur.rchild:
                return False
                break
        else:
            if cur.lchild and cur.rchild:
                queue.append(cur.lchild)
                queue.append(cur.rchild)
            elif cur.lchild and not cur.rchild:
                queue.append(cur.lchild)
                hasNoChild=True
            elif not cur.lchild and cur.rchild:
                result=False
                break
            else:
                hasNoChild=True
    return result

if __name__=='__main__':
    a=input('请以顺序存储的方式输入二叉树，用#补成满二叉树：')
    n=len(a)
    cc=isCBTree(trans(a,1,n))
    if cc==True:
        print('此二叉树是完全二叉树')
    else:
        print('此二叉树不是完全二叉树')

只有本站会员才能查看附件，请登录

#4

Ⅳ飒2019-05-05 19:41

回复楼主 Ⅳ飒

我答第二题
class Node(object):
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

def trans(a,i,n): #n是以顺序存储元素个数
    if (i>n):
        return None
    b=Node(a[i-1])
    if b.elem=='#':
        return None
    b.lchild=trans(a,2*i,n)
    b.rchild=trans(a,2*i+1,n)
    return b

def isCBTree(root):
    if not root:
        return False
    queue = [root]
    result = True
    hasNoChild=False
    while queue:
        cur=queue.pop(0)
        if hasNoChild:
            if cur.lchild or cur.rchild:
                return False
                break
        else:
            if cur.lchild and cur.rchild:
                queue.append(cur.lchild)
                queue.append(cur.rchild)
            elif cur.lchild and not cur.rchild:
                queue.append(cur.lchild)
                hasNoChild=True
            elif not cur.lchild and cur.rchild:
                result=False
                break
            else:
                hasNoChild=True
    return result

if __name__=='__main__':
    a=input('请以顺序存储的方式输入二叉树，用#补成满二叉树：')
    n=len(a)
    cc=isCBTree(trans(a,1,n))
    if cc==True:
        print('此二叉树是完全二叉树')
    else:
        print('此二叉树不是完全二叉树')

只有本站会员才能查看附件，请登录

#5

TysonKoothra2019-05-05 20:22

你这不是会写嘛

#6

汪瑞2019-05-30 03:43

你这不是会写嘛