python中創建和遍歷二叉樹

• 2020 年 1 月 9 日
• 筆記

python創建和遍歷二叉樹，可以使用遞歸的方式，源代碼如下：

#!/usr/bin/python  class node():  	def __init__(self,k=None,l=None,r=None):  		self.key=k;  		self.left=l;  		self.right=r;    def create(root):  	a=raw_input('enter a key:');  	if a is '#':  		root=None;  	else:  		root=node(k=a);  		root.left=create(root.left);  		root.right=create(root.right);  	return root;    def preorder(root):      #前序遍歷  	if root is None:  		return ;  	else :  		print root.key;  		preorder(root.left);  		preorder(root.right);    def inorder(root):     #中序遍歷  	if root is None:  		return ;  	else:  		inorder(root.left);  		print root.key;  		inorder(root.right);    def postorder(root):   # 後序遍歷  	if root is None:  		return ;  	else :  		postorder(root.left);  		postorder(root.right);  		print root.key;    root=None;     # 測試代碼  root=create(root);  preorder(root);  inorder(root);  postorder(root);

運行程序，建立二叉樹如圖：

前序遍歷結果為： a  b  c  d  e  f

中序遍歷結果為：c  b  d  a  f  e 

後序遍歷結果為：c  d  b  f  e  a