当前位置：首页 » 编程语言 » python实现二叉树

python实现二叉树

发布时间: 2021-03-21 14:02:03

① 如何用python构造一个n层的完全二叉树

用python构造一个n层的完全二叉树的代码如下：
typedefstruct{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储huffman树
算法设计
voidcreateHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);//动态分配数组存储huffman树,0号单元未用
//m:huffman树中的结点数（m=2*n-1）
for(i=1;i<=m;++i)
ht[i].parent=ht[i]->lch=ht[i]->rch=0;
for(i=1;i<=n;++i)
ht[i].weight=w[i];//初始化，w[i]：n个叶子的权值
for(i=n+1;i<=m,++i)｛//建哈夫曼树
select(i-1),s1,s2);//在ht[k](1<=k<=i-1)中选择两个双亲域为零而权值取最小的结点:s1和s2
ht[s1].parent=ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
};
}

② Python怎么实现二叉树排序

常用的排序算法（主要指面试中）包含两大类，一类是基础比较模型的，也就是回排序的过程答，是建立在两个数进行对比得出大小的基础上，这样的排序算法又可以分为两类：一类是基于数组的，一类是基于树的；基础数组的比较排序算法主要有：冒泡法，插入法，选择法，归并法，快速排序法；基础树的比较排序算法主要有：堆排序和二叉树排序；基于非比较模型的排序，主要有桶排序和位图排序（个人认为这两个属于同一思路的两个极端）。

③ python 二叉树是怎么实现的

#coding:utf-8
#author:Elvis

classTreeNode(object):
def__init__(self):
self.data='#'
self.l_child=None
self.r_child=None

classTree(TreeNode):
#createatree
defcreate_tree(self,tree):
data=raw_input('->')
ifdata=='#':
tree=None
else:
tree.data=data
tree.l_child=TreeNode()
self.create_tree(tree.l_child)
tree.r_child=TreeNode()
self.create_tree(tree.r_child)

#visitatreenode
defvisit(self,tree):
#输入#号代表空树
iftree.dataisnot'#':
printstr(tree.data)+'	',
#先序遍历
defpre_order(self,tree):
iftreeisnotNone:
self.visit(tree)
self.pre_order(tree.l_child)
self.pre_order(tree.r_child)

#中序遍历
defin_order(self,tree):
iftreeisnotNone:
self.in_order(tree.l_child)
self.visit(tree)
self.in_order(tree.r_child)

#后序遍历
defpost_order(self,tree):
iftreeisnotNone:
self.post_order(tree.l_child)
self.post_order(tree.r_child)
self.visit(tree)

t=TreeNode()
tree=Tree()
tree.create_tree(t)
tree.pre_order(t)
print'
'
tree.in_order(t)
print'
'
tree.post_order(t)

④ 如何实现Python多叉树

classnode:

def__init__(self,data):
self._data=data
self._children=[]

defgetdata(self):
returnself._data

defgetchildren(self):
returnself._children

defadd(self,node):
##iffull
iflen(self._children)==4:
returnFalse
else:
self._children.append(node)

defgo(self,data):
forchildinself._children:
ifchild.getdata()==data:
returnchild
returnNone

classtree:

def__init__(self):
self._head=node('header')

deflinktohead(self,node):
self._head.add(node)

definsert(self,path,data):
cur=self._head
forstepinpath:
ifcur.go(step)==None:
returnFalse
else:
cur=cur.go(step)
cur.add(node(data))
returnTrue

defsearch(self,path):
cur=self._head
forstepinpath:
ifcur.go(step)==None:
returnNone
else:
cur=cur.go(step)
returncur


'''
definenode
'''
a=node('A')
b=node('B')
c=node('C')
d=node('D')
e=node('E')
f=node('F')
g=node('G')
h=node('H')
i=node('I')
j=node('J')
k=node('K')
l=node('L')
m=node('M')
n=node('N')
o=node('O')

'''
addingnodetobuildtrue
'''
a.add(b)
a.add(g)
a.add(h)
b.add(c)
b.add(e)
g.add(i)
g.add(j)
g.add(k)
g.add(l)
h.add(m)
h.add(n)
h.add(o)
c.add(d)
c.add(f)
i.add(node(29))
j.add(node(28))
k.add(node(27))
l.add(node(26))
m.add(node(25))
n.add(node(24))
o.add(node(23))
f.add(node(30))


tree=tree()
tree.linktohead(a)


#testcase
print'Node',tree.search("ABE").getdata()
print'Node',tree.search("ABC").getdata()
print'Node',tree.search("AHM").getdata()
tree.insert("ABCD",1)
foriind.getchildren():
print'valueafter',d.getdata(),'is',i.getdata()

⑤ python编写欧式二叉树的问题

所以我就遇到了一下几个问题：
1、该怎么把二叉树各个节点连起来？
2、怎么定义内部数据成员？
3、如何实例化左右孩子？

在网上也没找到比较简单比较通用的Python二叉树类实现，所以我花了点时间自己写一个。
[python] view plain 在CODE上查看代码片派生到我的代码片
class Tree:
def __init__(self, val = '#', left = None, right = None):
self.val = val
self.left = left
self.right = right

#前序构建二叉树
def FrontBuildTree(self):
temp = input('Please Input: ')
node = Tree(temp)
if(temp != '#'):
node.left = self.FrontBuildTree()
node.right = self.FrontBuildTree()
return node#因为没有引用也没有指针，所以就把新的节点给返回回去

#前序遍历二叉树
def VisitNode(self):
print(self.val)
if(self.val != '#'):
self.left.VisitNode()
self.right.VisitNode()

if __name__ == '__main__':
root = Tree()
root = root.FrontBuildTree()
root.VisitNode()

⑥ 求一个python feiditui 已知二叉树求中序遍历和后续遍历的代码

classNode:
	def__init__(self,val):
		self.val=val
		self.left,self.right=None,None
classTree:
	defcreate_tree(self,pre,mid):
		ifpre:
			root_val=pre[0]
			root_val_index_mid=mid.index(root_val)
			root=Node(root_val)
			root.left=self.create_tree(pre[1:root_val_index_mid+1],mid[:root_val_index_mid])
			root.right=self.create_tree(pre[root_val_index_mid+1:],mid[root_val_index_mid+1:])
		else:
			returnNone
		returnroot

	defprint_tree(self,root):
		nodes=[root]
		whilenodes:
			node=nodes.pop(0)
			print(node.val)
			ifnode.left:
				nodes.append(node.left)
			ifnode.right:
				nodes.append(node.right)

	defmid_series(self,root):
		'''中序遍历'''
		stack,stack2=[],[]
		node=root
		whilenodeorstack:
			ifnode:
				stack.append(node)
				node=node.left
			else:
				node=stack.pop()
				stack2.append(node.val)
				node=node.right
		print(stack2)

	defback_series(self,root):
		'''后序遍历'''
		stack,stack2=[root],[]
		whilestack:
			node=stack.pop()
			stack2.insert(0,node.val)
			ifnode.left:
				stack.append(node.left)
			ifnode.right:
				stack.append(node.right)

		print(stack2)


tree=Tree()
root=tree.create_tree(['1','2','4','3','5','6'],['2','4','1','5','3','6'])
#tree.print_tree(root)
tree.mid_series(root)
tree.back_series(root)

⑦ 如何将数据存储为二叉树python

（1）二叉树是有序树，即使只有一个子树，也必须区分左、右子树；
（2）二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；
（3）二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。

⑧ python 二叉树实现思想

第一：return 的缩进不对，

ifself.root==None:
self.root=node
return#如果这里不缩进，下面的语句无意义，直接返回，不会执行内。

while queue这个循环的容作用的是从root根结点开始，向下查找第一个左(右)子结点为空的结点，将node插入这个位置,queue的作用是将查找到的非空子结点保存在queue中，然后依次向下查找这些子结点的左右子结点

⑨ python字典怎么表现二叉树

用python构造一个n层的完全二叉树的代码如下： typedef struct {int weight;int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树算法设计void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode.

阅读全文

python实现二叉树

与python实现二叉树相关的阅读推荐