| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 261 人关注过本帖
标题:求助python(关于树与二叉树的两道题)
只看楼主 加入收藏
Ⅳ飒
Rank: 1
等 级:新手上路
帖 子:12
专家分:7
注 册:2019-5-4
结帖率:0
  已结贴   问题点数:20  回复次数:4   
求助python(关于树与二叉树的两道题)
1、假设二叉树中的每个结点值为单个字符,采用顺序存储结构存储,设计一个算法,求二叉树t中的叶子结点个数。
2、假设二叉树以二叉链存储,设计一个算法,判断一个二叉树是否为完全二叉树。
用python做出来,分为两个py文件
2019-05-04 20:57
TysonKoothra
Rank: 3Rank: 3
等 级:论坛游侠
威 望:2
帖 子:26
专家分:157
注 册:2018-10-21
  得分:20 
我回答第一个问题
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))
2019-05-05 11:25
Ⅳ飒
Rank: 1
等 级:新手上路
帖 子:12
专家分:7
注 册:2019-5-4
  得分:0 
回复 楼主 Ⅳ飒
我答第二题
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('此二叉树不是完全二叉树')
附件: 您没有浏览附件的权限,请 登录注册
2019-05-05 19:41
Ⅳ飒
Rank: 1
等 级:新手上路
帖 子:12
专家分:7
注 册:2019-5-4
  得分:0 
回复 楼主 Ⅳ飒
我答第二题
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('此二叉树不是完全二叉树')
附件: 您没有浏览附件的权限,请 登录注册
2019-05-05 19:41
TysonKoothra
Rank: 3Rank: 3
等 级:论坛游侠
威 望:2
帖 子:26
专家分:157
注 册:2018-10-21
  得分:0 
你这不是会写嘛
2019-05-05 20:22







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.050822 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved