会计学二叉树的存储(cúnchǔ)表示空树：None非空树：[data,left,right]tree=[‘*’,[3,None,None],[‘+’,[5,None,None],[7,None,None]]]空树：None非空树：若结点(jiédiǎn)的左右子树均为空，则为data否则：[data,left,right]tree=[‘*’,3,[‘+’,5,7]]list表示是利用了Python的list可以含有(hányǒu)不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构；由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。classBinTNode:def__init__(self,data,left=None,right=None):self.data=dataself.left=leftself.right=right2025/3/6root=BinTNode(‘*’,BinTNode(3,None,None),BinTNode(‘+’,BinTNode(5,None,None),BinTNode(7,None,None)))root=BinTNode(‘*’,BinTNode(3),BinTNode(‘+’,BinTNode(5),BinTNode(7)))三叉链表三叉链表相当于线性表中的“双向”链表，方便由孩子(háizi)找到双亲。二叉树的递归遍历(biànlì)若二叉树为空，则空操作；否则(fǒuzé)：访问根结点(v)；先序遍历左子树(L)；先序遍历右子树(R)。先序：-+a*b-cd/efdefpreorder(tree):iftree!=None:print(tree[0],end='')#对根的访问(fǎngwèn)preorder(tree[1])preorder(tree[2])defpreorder(root):ifroot!=None:print(root.data,end=‘’)#对根的访问(fǎngwèn)preorder(root.left)preorder(root.right)若二叉树为空，则空操作(cāozuò)；否则：中序遍历左子树(L)；访问根结点(v)；中序遍历右子树(R)。中序：a+b*c-d-e/f后序(hòuxù)：abcd-*+ef/-definorder(root):ifroot!=None:inorder(root.left)print(root.data,end=‘’)#对根的访问(fǎngwèn)inorder(root.right)deforder(树T):iftree!=None:order(T的左子树);order(T的右子树);}}基于遍历(biànlì)的递归算法defcount(root):ifroot==None:return0else:n1=count(root.left)n2=count(root.right)n=1+n1+n2;returnndefnum(root):ifroot==None:return0else:return1+num(root.left)+num(root.right)defheight(root):ifroot==None:return-1else:return1+max(height(root.left),height(root.right))//注意：层次从0编号(biānhào)时，空树深度为-1!二叉树的建立(jiànlì)先序序列(xùliè)：ABHFDECKG中序序列(xùliè)：HBDFAEKCG先序序列(xùliè)：ABHFDECKG中序序列(xùliè)：HBDFAEKCG根defcreateTreeBy2Orders(preorderList,p1,p2,inorderList,i1,i2):ifp1>=p2:returnNonedata=preorderList[p1]k=inorderList.index(data,i1,i2)-i1root=BinTNode(data)root.left=createTreeBy2Orders(preorderList,p1+1,p1+k+1,inorderList,i1,i1+k)root.right=createTreeBy2Orders