python創(chuàng)建與遍歷二叉樹(shù)的方法實(shí)例

前言

樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹(shù)和二叉樹(shù)最為常用，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)；在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯程序中，可用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一；在機(jī)器學(xué)習(xí)中，決策樹(shù)，隨機(jī)森林，GBDT等是常見(jiàn)的樹(shù)模型。

樹(shù)（Tree）是個(gè)結(jié)點(diǎn)的有限集。在任意一棵樹(shù)中：（1）有且僅有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)；（2）當(dāng)時(shí)，其余節(jié)點(diǎn)可分為個(gè)互不相交的有限集其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)（SubTree）。

圖1 樹(shù)型結(jié)構(gòu)

python創(chuàng)建與遍歷二叉樹(shù)

python創(chuàng)建和遍歷二叉樹(shù)，可以使用遞歸的方式，源代碼如下：

#!/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;  # 測(cè)試代碼
root=create(root);
preorder(root);
inorder(root);
postorder(root);
 

運(yùn)行程序，建立二叉樹(shù)如圖：

前序遍歷結(jié)果為： a  b  c  d  e  f

中序遍歷結(jié)果為：c  b  d  a  f  e 

后序遍歷結(jié)果為：c  d  b  f  e  a 

總結(jié)

到此這篇關(guān)于python創(chuàng)建與遍歷二叉樹(shù)的文章就介紹到這了,更多相關(guān)python創(chuàng)建與遍歷二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！