python二叉樹遍歷
1. 二叉樹的遍歷問題
程序VS2003成功編譯運行
#include
"stdafx.h"
#include<iostream>
using
namespace
std;
typedef
struct
tree
{
char
data;
//數據域
struct
tree
*lchild;
//左孩子
struct
tree
*rchild;
//右孩子
struct
tree
*next;
//用於構造隊列
}bintree;
//二叉樹的建立
bintree
*create(char*
str,
int
pose,
int
size)
{
char
ch;
bintree
*
t;
char*
p=str;
ch
=
p[pose];
if(ch=='
'||
ch=='\n'||
pose>=size)
return
NULL;
//
表示空結點
else
{
t=(bintree
*)malloc(sizeof(bintree));
//非空則構造新結點
t->data=ch;
//新結點數據域即為讀入字元
t->next=NULL;
//新結點next域暫時不用，賦空
t->lchild=create(p,
2*pose+1,size);
//建立左子樹
t->rchild=create(p,
2*pose+2,size);
//建立右子樹
}
return(t);
}
void
PrintTree(bintree
*T,int
Layer)
{//
按豎向樹狀列印的二叉樹//
int
i;
if(T==NULL)
return;
PrintTree(T->rchild,Layer+1);
for(i=0;i<Layer;i++)
printf("
");
printf("%c
\n",T->data);
//按逆中序輸出結點，用層深決定結點的左右位置
PrintTree(T->lchild,Layer+1);
}
void
visitT(char
e)
{
printf("%c
",e);
}
//先序遍歷
void
preorder(bintree
*root,
void(*vi)(char))
{
bintree
*t=root;
if(NULL!=t)
{
vi(t->data);
//訪問根結點
preorder(t->lchild,
vi);
//先序遍歷左子樹
preorder(t->rchild,
vi);
//先序遍歷右子樹
}
}
//層次遍歷
void
levelorder(bintree
*root,
void(*vi)(char))
{
bintree
*t=root;
struct
tree
*head=t,*tail=t;
//head指向源結點，稱頭指針；tail指向末結點，稱尾指針//
while(NULL!=head)
//若源結點非空，且有左或右孩子，則將其孩子依次入隊；若源結點為空，則跳出循環//
{
if(NULL!=head->lchild)
{
tail->next=head->lchild;
tail=tail->next;
}
//若源結點有左孩子，則該左孩子入隊，尾指針後移一位/燃鉛/
if(NULL!=head->rchild)
{
tail->next=head->rchild;
tail=tail->next;
}
//若源結點有右孩子，則該右孩子入隊，尾指針後移一位//
head=head->next;
//依次訪問完敗銀源結點的左右孩子後，頭指針後移一個，進入下次循環//
}
while(t!=NULL)
{
vi(t->data);
//訪問根結點
t=t->next;
}
}
//主函數
void
main()
{
bintree
*root;
char
a[20];
printf("給察段宴出建立二叉樹的字元串:");
cout
<<"輸入CH"
<<endl;
cin
>>
a;
root=create(a,
0,strlen(a));
printf("\n二叉樹的凹入表示:\n");
PrintTree(root,0);
printf("\n先序遍歷序列:
");
preorder(root,visitT);
printf("\n層次遍歷序列:
");
levelorder(root,visitT);
printf("\n");
system("pause");
}
2. 二叉樹的層次遍歷
設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存當前節點的左右孩子的隊列
InitQueue(Q); // 初始化隊列
if (Root == NULL) return ; //樹為空則返回
BiNode *p = Root; // 臨時保存樹根Root到指針p中
Visit(p->data); // 訪問根節點
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子進隊列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子進隊列
while (!QueueEmpty(Q)) // 若隊列不空，則層序遍歷 { DeQueue(Q, p); // 出隊列
Visit(p->data);// 訪問當前節點
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子進隊列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子進隊列
}
DestroyQueue(Q); // 釋放隊列空間
return ;
這個已經很詳細了！你一定可以看懂的！加油啊！
3. 二叉樹的遍歷
遍歷概念
所謂遍歷(Traversal)是指沿著某條搜索路線 依次對樹中每個結點均做一次且僅做一次訪問 訪問結點所做的操作依賴於具體的應用問題 遍歷是二叉樹上最重要的運算之一 是二叉樹上進行其它運算之基礎
遍歷方案
．遍歷方案 從二叉樹的遞歸定義可知 一棵非空的二叉樹由根結點及左 右子樹這三個基本部分組成 因此 在任一給定結點上 可以按某種次序執行三個操作 （ ）訪問結點本身(N) （ ）遍歷該結點的左子樹(L) （ ）遍歷該結點的右子樹(R) 以上三種操作有六種執行次序 NLR LNR LRN NRL RNL RLN 注意 前三種次序與後三種次序對稱 故只討論先左後右的前三種次序
．三種遍歷的命名 根據訪問結點操作發生位置命名 ① NLR 前序遍歷(PreorderTraversal亦稱(先序遍歷))——訪問結點的操作發生在遍歷其左右子樹之前 ② LNR 中序遍歷(InorderTraversal)——訪問結點的操作發生在遍歷其左右子樹之中(間) ③ LRN 後序遍歷(PostorderTraversal)——訪問結點的操作發生在遍歷其左右子樹之後 注意 由於被訪問的結點必是某子樹的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解釋為根 根的左子樹和根的右子樹 NLR LNR和LRN分別又稱為先根遍歷 中根遍歷和後根遍歷
遍歷演算法
．中序遍歷的遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( )遍歷左子樹 ( )訪問根結點 ( )遍歷右子樹
．先序遍歷的遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( ) 訪問根結點 ( ) 遍歷左子樹 ( ) 遍歷右子樹
．後序遍歷得遞歸演算法定義 若二叉樹非空 則依次執行如下操作 ( )遍歷左子樹 ( )遍歷右子樹 ( )訪問根結點
．中序遍歷的演算法實現 用二叉鏈表做為存儲結構 中序遍歷演算法可描述為 void InOrder(BinTree T) { //演算法里①~⑥是為了說明執行過程加入的標號 ① if(T) { // 如果二叉樹非空 ② InOrder(T >lchild) ③ printf( ％c T >data) // 訪問結點 ④ InOrder(T >rchild); ⑤ } ⑥ } // InOrder
遍歷序列
．遍歷二叉樹的執行蹤跡 三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示） 具體線路為 從根結點出發 逆時針沿著二叉樹外緣移動 對每個結點均途徑三次 最後回到根結點 ．遍歷序列 （ ） 中序序列 中序遍歷二叉樹時 對結點的訪問次序為中序序列【例】中序遍歷上圖所示的二叉樹時 得到的中序序列為 D B A E C F （ ） 先序序列 先序遍歷二叉樹時 對結點的訪問次序為先序序列【例】先序遍歷上圖所示的二叉樹時 得到的先序序列為 蔽拿衡 A B D C E F （ ） 後序序列 後宏做序遍歷二叉樹時 對結點的訪問次序為後序序列【例】後序遍歷上圖所示的二叉樹時 得到的後序序列為 D B E F C A 注意 （ ） 在搜索路線中 若訪問結點均是第一次經過結點時進行的 則是前序遍歷 若訪問結點均是在第二次(或第三次)經過結點時進行敏羨的 則是中序遍歷(或後序遍歷) 只要將搜索路線上所有在第一次 第二次和第三次經過的結點分別列表 即可分別得到該二叉樹的前序序列 中序序列和後序序列 （ ） 上述三種序列都是線性序列 有且僅有一個開始結點和一個終端結點 其餘結點都有且僅有一個前趨結點和一個後繼結點 為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念 對上述三種線性序列 要在某結點的前趨和後繼之前冠以其遍歷次序名稱 【例】上圖所示的二叉樹中結點C 其前序前趨結點是D 前序後繼結點是E 中序前趨結點是E 中序後繼結點是F 後序前趨結點是F 後序後繼結點是A 但是就該樹的邏輯結構而言 C的前趨結點是A 後繼結點是E和F
二叉鏈表的構造
． 基本思想 基於先序遍歷的構造 即以二叉樹的先序序列為輸入構造 注意 先序序列中必須加入虛結點以示空指針的位置 【例】建立上圖所示二叉樹 其輸入的先序序列是 ABD∮∮CE∮∮F∮∮
4. 二叉樹的遍歷演算法
這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
5. python 如何將一段字元串用二叉樹的後序遍歷列印出來
# -*- coding:utf-8 -*-def fromFMtoL( mid ): global las #全局後序遍歷 global fir #先序遍歷 root = fir[0] #取出當前樹根 fir = fir[1:] #取出樹根後 先序遍歷把根拿出來 下面一個元素做樹根 root_po = mid.find( root ) #在中序遍歷當中樹根的位置 left = mid[0:root_po] #左子樹 right = mid[root_po+1:len(mid)] #右子樹 ''' 後序遍歷： 左 右 根 先左子樹 再右子樹 最後跟 ''' #有左子樹的時候 if len(left) > 0: fromFMtoL( left ) #有右子樹的時候 if len(right) > 0: fromFMtoL( right ) #樹根寫進結果 las += rootif __name__ == "__main__" : # fir = input("請輸入先序遍歷：") #前序遍歷的結果 # mid = input("請輸入中序遍歷：") #中序遍歷的結果 fir = "DBACEGF" mid = "ABCDEFG" # fir = "ABC" # mid = "BAC" las = "" fromFMtoL( mid ) print(las)
6. Python演算法系列—深度優先遍歷演算法
一、什麼是深度優先遍歷
深度優先遍歷演算法是經典的圖論演算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷演算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。
二、二叉樹
2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。
空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.
註：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
術語 解釋
度 節點的度為節點的子樹個數
葉子節點 度為零的節點
分支節點 度不為零的節點
孩子節點 節點下的兩個子節點
雙親節點 節點上一層的源節點
兄弟節點 擁有同一雙親節點的節點
根 二叉樹的源頭節點
深度 二叉樹中節點的層的數量
DLR（先序）：
LDR（中序）：
LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根
6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題+勵志
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
2.用你熟悉的語言說說怎麼創建二叉樹？ python看上文
7. 二叉樹的遍歷演算法
void
preorder(BiTree
root)
/*先序遍歷輸出二叉樹結點，root為指向二叉樹根節點的指針*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好這個程序,你首先定義了一個preorder函數,然後在函數體中又調用了本函數,這是函數的自調用.執行printf(root->data);語句的時候輸出當前遍歷的數據,preorder(root->Lchild);在執行到4的時候,root->Lchild=NULL,但是執行preorder(root->Rchild);語句,由此轉向下一個結點,即5
8. python列印二叉樹所有路徑的主函數怎樣寫
基本演算法就是二叉樹的遍歷，首先想到的是深度優先遍歷。
難點在於，如何實現每個子路徑的記錄和append
binaryTreePaths函數只給了root變數，無法存儲每個子路徑，考慮寫輔助函數res，添加存儲路徑的變數
res(root,temp)
同時還需要一個全局變數result存儲最後的輸出結果，result.append(temp)
9. python怎麼做二叉查找樹
可以的，和C++中類的設計差不多，以下是二叉樹的遍歷
class BTree:
def __init__(self,value):
self.left=None
self.data=value
self.right=None
def insertLeft(self,value):
self.left=BTree(value)
return self.left
#return BTree(value)
def insertRight(self,value):
self.right=BTree(value)
return self.right
def show(self):
print self.data
def preOrder(node):
node.show()
if node.left:
preOrder(node.left)
if node.right:
preOrder(node.right)
def inOrder(node):
if node:
if node.left:
inOrder(node.left)
node.show()
if node.right:
inOrder(node.right)
if __name__=='__main__':
Root=BTree('root')
A=Root.insertLeft('A')
C=A.insertLeft('C')
D=A.insertRight('D')
F=D.insertLeft('F')
G=D.insertRight('G')
B=Root.insertRight('B')
E=B.insertRight('E')
preOrder(Root)
print 'This is binary tree in-traversal'
inOrder(Root)
10. 關於python中一個遞歸二叉樹遍歷的問題
你在出錯的地方前面加個print，把這兩個值都print出來不就知道錯在哪個了？