演算法的遍歷
A. 什麼叫遍歷演算法(最好有例子)
遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。
遍歷演算法概念延伸：
圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。
舉例：
遍歷二叉樹搜索路線：
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。
遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
B. 二叉樹的遍歷演算法
這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
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
C. 數據結構中"遍歷"是什麼意思
所謂遍歷，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點旅悄備所做的操作依賴於具體的應用問題。 遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。
(3)演算法的遍歷擴展閱讀：
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。
在數據結構中三種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和後序遍歷。
以下是三種遍歷的方法：
1、中序：若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
2、先序遍歷：若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
3、後序遍歷：若二叉樹非空，則依次執行如下操作：
⑴運猛遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。
以這3種方式遍歷一棵樹時，若按訪問結點的先後次序將結點排列起來，就可分別拆毀得到樹中所有結點的前序列表、中序列表和後序列表。相應的結點次序分別稱為結點的前序、中序和後序。
D. 二叉樹的層次遍歷演算法
二叉樹的層次遍歷演算法有如下三種方法：
給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：
之後大家就可以自己畫圖了，下面給出程序代碼：
[cpp] view plain
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最後給出完成代碼的測試用例：124##57##8##3#6##
[cpp] view plain
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree(&(*T)->lchild);
create_tree(&(*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
E. 求遍歷全排列的演算法
全排列的生成演算法就是對於給定的字元集，用有效的方法將所有可能的全排列無重復無遺漏地枚舉出來。
常見的有四種全排列演算法：
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法
這里著重介紹字典序法
對給定的字元集中的字元規定了一個先後關系，在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字元的先後。
[例]字元集{1,2,3},較小的數字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
[注意] 一個全排列可看做一個字元串，字元串可有前綴、後綴。
1）生成給定全排列的下一個排列 所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的後綴上。
[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最後面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個了。否則找出第一次出現下降的位置。
F. 二叉樹的遍歷演算法
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
G. 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看上文