二叉樹的遍歷演算法實驗報告

㈠ 用C語言編程實現二叉樹的中序遍歷演算法

#include<stdio.h>
#include<stdlib.h>
struct BiTNode *stack[100];
struct BiTNode//定義結構體
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序創建樹
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //前序遍歷（輸出二叉樹）
{
int i=-1;
while(1)
{
while(p!=NULL)
{
stack[++i]=p->rchild;/*printf("ok？\n");*/
printf("%c",p->data);
p=p->lchild;
}
if(i!=-1)
{
p=stack[i];
i--;
}
else
return;
}
}
void main()//主函數
{
struct BiTNode *p,*t;
later(p);
print(p);
}

㈡ 二叉樹以二叉鏈表存儲，結點數據類型為整型，試定義二叉鏈表的結構， 試編寫演算法，將二叉樹所有結點的值

演算法不難，會樹的遍歷就好理解了。
演算法如下：
void MultiValue(Tree *r)
{
if(r == NULL)
return ;
r->data = (r->data)*10;
MultiValue(r->left);
MultiValue(r->right);
}

㈢ 二叉樹的操作及其應用：1、以二叉鏈表作存儲結構，試編寫前序、中序、後序及層次順序遍歷二叉樹的演算法。 2

文件 main.cpp 代碼如下：

#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣

typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;

int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}

void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}

㈣ 二叉樹遍歷演示

四、 遍歷二叉樹 二叉樹是一種非線性的數據結構，在對它進行操作時，總是需要逐一對每個數據元素實施 操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。所謂遍歷二叉樹就 是按某種順序訪問二叉樹中的每個結點一次且僅一次的過程。這里的訪問可以是輸出、比 較、更新、查看元素內容等等各種操作。
二叉樹的遍歷方式分為兩大類：一類按根、左子樹和右子樹三個部分進行訪問；另一類按 層次訪問。下面我們將分別進行討論。
1、 按根、左子樹和右子樹三部分進行遍歷 遍歷二叉樹的順序存在下面6種可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三種順序在左右子樹之間均是先右子樹後左子樹，這與人們先左後右的習慣不同，因此，往往不予採用。餘下的三種順序TLR、LTR和LRT根據根訪問的位置不同分別被稱為先序遍歷、中序遍歷和後序遍歷。（1）先序遍歷若二叉樹為空，則結束遍歷操作；否則訪問根結點；先序遍歷左子樹；先序遍歷右子樹。（2）中序遍歷若二叉樹為空，則結束遍歷操作；否則中序遍歷左子樹；訪問根結點；中序遍歷右子樹。（3）後序遍歷若二叉樹為空，則結束遍歷操作；否則後序遍歷左子樹；後序遍歷右子樹；訪問根結點。例如。以下是一棵二叉樹及其經過三種遍歷所得到的相應遍歷序列二叉樹的兩種遍歷方法：（1）對一棵二叉樹中序遍歷時，若我們將二叉樹嚴格地按左子樹的所有結點位於根結點的左側，右子樹的所有結點位於根右側的形式繪制，就可以對每個結點做一條垂線，映射到下面的水平線上，由此得到的順序就是該二叉樹的中序遍歷序列
（2）任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這條包線對於理解二叉樹的遍歷過程很有用。 由此可以看出：（1）遍歷操作實際上是將非線性結構線性化的過程，其結果為線性序列，並根據採用的遍歷順序分別稱為先序序列、中序序列或後序序列；（2）遍歷操作是一個遞歸的過程，因此，這三種遍歷操作的演算法可以用遞歸函數實現。（1）先序遍歷遞歸演算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild);
}（2）中序遍歷遞歸演算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}（3）後序遍歷遞歸演算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 2 、按層次遍歷二叉樹 實現方法為從上層到下層，每層中從左側到右側依次訪問每個結點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結點的遍歷序列。
void LevelOreder(QBTree BT) {
for (i=1;i<=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);
}二叉樹用鏈式存儲結構表示時，按層遍歷的演算法實現訪問過程描述如下：訪問根結點，並將該結點記錄下來；若記錄的所有結點都已處理完畢，則結束遍歷操作；否則重復下列操作。取出記錄中第一個還沒有訪問孩子的結點，若它有左孩子，則訪問左孩子，並將記錄下來；若它有右孩子，則訪問右孩子，並記錄下來。 在這個演算法中，應使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作； 而取出記錄的結點就是出隊操作。這樣一來，我們的演算法就可以描述成下列形式：（1）訪問根結點，並將根結點入隊；（2）當隊列不空時，重復下列操作：從隊列退出一個結點；若其有左孩子，則訪問左孩子，並將其左孩子入隊；若其有右孩子，則訪問右孩子，並將其右孩子入隊；void LevelOrder(BTree *BT) {
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //訪問根結點，並將根結點入隊
while (!QueueEmpty(Q)) { //當隊非空時重復執行下列操作
DeQueue(&Q,&p); //出隊
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //處理左孩子<br> if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //處理右孩子<br> }
}
五、典型二叉樹的操作演算法 1、 輸入一個二叉樹的先序序列，構造這棵二叉樹 為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉 樹的位置上填補一個特殊的字元，比如，'#'。在演算法中，需要對每個輸入的字元進行判 斷，如果對應的字元是'#'，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結 點。整個演算法結構以先序遍歷遞歸演算法為基礎，二叉樹中結點之間的指針連接是通過指針 參數在遞歸調用返回時完成。演算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL; //構造空樹
else { BT=(BTree)malloc(sizeof(BTLinklist)); //構造新結點
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //構造左子樹
BT->rchild =Pre_Create_BT( ); //構造右子樹
return BT;
}
} 2、 計算一棵二叉樹的葉子結點數目 這個操作可以使用三種遍歷順序中的任何一種，只是需要將訪問操作變成判斷該結點是否 為葉子結點，如果是葉子結點將累加器加1即可。下面這個演算法是利用中序遍歷實現的。演算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count); //計算左子樹的葉子結點個數
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
Leaf(BT->rchild,&count); //計算右子樹的葉子結點個數
}
} 3、 交換二叉樹的左右子樹 許多操作可以利用三種遍歷順序的任何一種，只是某種遍歷順序實現起來更加方便一 些。而有些操作則不然，它只能使用其中的一種或兩種遍歷順序。將二叉樹中所有結點的左右子樹進行交換這個操作就屬於這類情況。演算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchild<->BT->rchild;
}
} 4 、求二叉樹的高度 這個操作使用後序遍歷比較符合人們求解二叉樹高度的思維方式。首先分別求出左右子樹 的高度，在此基礎上得出該棵樹的高度，即左右子樹較大的高度值加1。演算法：int hight(BTree BT) { //h1和h2分別是以BT為根的左右子樹的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
} 六、樹、森林與二叉樹的轉換 1、 樹、森林轉換成二叉樹 將一棵樹轉換成二叉樹的方法： 將一棵樹轉換成二叉樹實際上就是將這棵樹用孩子兄弟表示法存儲即可，此時，樹中的每個結點最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側第一個兄弟。當你將這兩個指針看作是二叉樹中的左孩子指針和孩子右指針時，就是一棵二叉樹了。 特點：一棵樹轉換成二叉樹後，根結點沒有右孩子。 將森林轉換成二叉樹的方法與一棵樹轉換成二叉樹的方法類似，只是把森林中所有樹的根 結點看作兄弟關系，並對其中的每棵樹依依地進行轉換。 2 、二叉樹還原成樹或森林 這個過程實際上是樹、森林轉換成二叉樹的逆過程，即將該二叉樹看作是樹或森林的孩子兄弟表示法。比如，若二叉樹為空，樹也為空；否則，由二叉樹的根結點開始，延右指針向下走，直到為空，途經的結點個數是相應森林所含樹的棵數；若某個結點的左指針非空，說明這個結點在樹中必有孩子，並且從二叉樹中該結點左指針所指結點開始，延右指針向下走，直到為空，途經的結點個數就是這個結點的孩子數目。
第 3 節 哈夫曼樹及其應用 1、哈夫曼樹的定義及特點
在二叉樹中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。這三棵二叉樹的帶權路徑長度分別為：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼樹的一個重要特點是：沒有度為1的結點。
2、構造哈夫曼樹的過程：
（1）將給定的n個權值{w1,w2,...,wn}作為n個根結點的權值構造一個具有n棵二叉樹的森林{T1,T2,...,Tn}，其中每棵二叉樹只有一個根結點；（2）在森林中選取兩棵根結點權值最小的二叉樹作為左右子樹構造一棵新二叉樹，新二叉樹的根結點權值為這兩棵樹根的權值之和；（3）在森林中，將上面選擇的這兩棵根權值最小的二叉樹從森林中刪除，並將剛剛新構造的二叉樹加入到森林中；（4）重復上面（2）和（3），直到森林中只有一棵二叉樹為止。這棵二叉樹就是哈夫曼樹。 例如： 假設有一組權值{5,29,7,8,14,23,3,11}，下面我們將利用這組權值演示構造哈夫曼樹的過程。
它的帶權的路徑長度為：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定樹 在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著 程序的執行效率。例如，編制一個程序，將百分制轉換成五個等級輸出。大家可能認為 這個程序很簡單，並且很快就可以用下列形式編寫出來：if (socre<60) printf("bad");
else if (socre<70) printf("pass");
else if (score<80) printf("general");
else if (score<90) printf("good");
esle printf("very good"); 在實際應用中，往往各個分數段的分布並不是均勻的。下面就是在一次考試中某門課程的各分數段的分布情況：

4．前綴編碼 在電文傳輸中，需要將電文中出現的每個字元進行二進制編碼。在設計編碼時需要遵守兩 個原則：（1）發送方傳輸的二進制編碼，到接收方解碼後必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；（2）發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。
（1）等長編碼 這種編碼方式的特點是每個字元的編碼長度相同（編碼長度就是每個編碼所含的二進制位 數）。假設字元集只含有4個字元A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。若現在有一段電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文後，將按兩位一段進行解碼。這種編碼的特點是解碼簡單且具有唯一性，但編碼長度並不是最短的。（2）不等長編碼 在傳送電文時，為了使其二進制位數盡可能地少，可以將每個字元的編碼設計為不等長的，使用頻度較高的字元分配一個相對比較短的編碼，使用頻度較低的字元分配一個比較長的編碼。例如，可以為A，B，C，D四個字元分別分配0，00，1，01，並可將上述電文用二進制序列：000011010發送，其長度只有9個二進制位，但隨之帶來了一個問題，接收方接到這段電文後無法進行解碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即解碼不唯一，因此這種編碼方法不可使用。（1）利用字元集中每個字元的使用頻率作為權值構造一個哈夫曼樹；（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，並從根到葉子方向形成該葉子結點的編碼。假設有一個電文字元集中有8個字元，每個字元的使用頻率分別為{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，現以此為例設計哈夫曼編碼。
哈夫曼編碼設計過程為：
（1）為方便計算，將所有字元的頻度乘以100，使其轉換成整型數值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的數值作為葉子結點的權值構造一棵哈夫曼樹，如圖5-27所示；
（3）由此哈夫曼樹生成哈夫曼編碼，如圖5-28所示。
最後得出每個字元的編碼為：比如，發送一段編碼：0000011011010010， 接收方可以准確地通過解碼得到：⑥⑥⑦⑤②⑧。

㈤ 二叉樹的層次遍歷以及用層次遍歷演算法顯示所有葉子節點

#include <iostream>
using namespace std;
struct segtree{int a,b;} tree[10001];
void buildtree(int l,int r,int root = 0) //建樹 { tree[root].a=l; tree[root].b=r; if (l==r) return; int mid=(l+r)>>1; root<<=1; buildtree(l,mid,root+1); buildtree(l,mid,root+2);}
void dfs(int level,int root = 0){ for (int i=1;i<level;i++) cout<<' '; cout<<"Lv"<<level<<" : ["<<tree[root].a<<","<<tree[root].b<<"]\n"; if (tree[root].a!=tree[root].b) { root<<=1; dfs(level+1,root+1); dfs(level+1,root+2); }}
struct {int root,level;} st[100001];
void bfs(){ int top=1,first=0; st[first].root=0; st[first].level=1; while (first<top) { for (int i=st[first].level;i>1;i--) cout<<' '; cout<<"Lv"<<st[first].level<<" : ["<<tree[st[first].root].a<<","<<tree[st[first].root].b<<"]\n"; if (tree[st[first].root].a!=tree[st[first].root].b) { st[top].root=st[first].root*2+1; st[top++].level=st[first].level+1; st[top].root=st[first].root*2+2; st[top++].level=st[first].level+1; } first++; }}
int main(){ int t,i; cout<<"以[1,9]線段樹為例，生成一個二叉樹。\n\n"; buildtree(1,9); cout<<"以深度遍歷該樹（深搜）：\n"; dfs(1); cout<<"以深度遍歷該樹（寬搜）：\n"; bfs(); system("pause"); return 0;}

㈥ java實現二叉樹層次遍歷

import java.util.ArrayList;

public class TreeNode {
private TreeNode leftNode;
private TreeNode rightNode;
private String nodeName;
public TreeNode getLeftNode() {
return leftNode;
}

public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}

public TreeNode getRightNode() {
return rightNode;
}

public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}

public String getNodeName() {
return nodeName;
}

public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public static int level=0;

public static void findNodeByLevel(ArrayList<TreeNode> nodes){
if(nodes==null||nodes.size()==0){
return ;
}
level++;
ArrayList<TreeNode> temp = new ArrayList();
for(TreeNode node:nodes){
System.out.println("第"+level+"層:"+node.getNodeName());
if(node.getLeftNode()!=null){
temp.add(node.getLeftNode());
}
if(node.getRightNode()!=null){
temp.add(node.getRightNode());
}
}
nodes.removeAll(nodes);
findNodeByLevel(temp);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode();
root.setNodeName("root");
TreeNode node1 = new TreeNode();
node1.setNodeName("node1");

TreeNode node3 = new TreeNode();
node3.setNodeName("node3");

TreeNode node7 = new TreeNode();
node7.setNodeName("node7");
TreeNode node8 = new TreeNode();
node8.setNodeName("node8");

TreeNode node4 = new TreeNode();
node4.setNodeName("node4");

TreeNode node2 = new TreeNode();
node2.setNodeName("node2");

TreeNode node5 = new TreeNode();
node5.setNodeName("node5");
TreeNode node6 = new TreeNode();
node6.setNodeName("node6");

root.setLeftNode(node1);

node1.setLeftNode(node3);

node3.setLeftNode(node7);
node3.setRightNode(node8);

node1.setRightNode(node4);

root.setRightNode(node2);

node2.setLeftNode(node5);
node2.setRightNode(node6);

ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
nodes.add(root);
findNodeByLevel(nodes);

}

}

㈦ 二叉樹遍歷程序

二叉樹的遍歷有3種方式：

a
/ \
/ \
b e
/ \ \
/ \ \
c d f

（先序）先根遍歷：（根左右）先訪問根，再訪問左子樹，最後訪問右子樹，則可得如下的序列：abcdef

（中序）中根遍歷：（左根右）先訪問左子樹，再訪問根，最後訪問右子樹，則可得如下的序列：cbdaef

（後序）後根遍歷：（左右根）先訪問左子樹，再訪問右子樹，最後訪問根，則可得如下的序列：cdbfea

本文給出二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。

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 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

㈧ 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[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;

}

㈨ 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。

按層次遍歷演算法如下：
#include <iostream>
using namespace std;

typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;

typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;

void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}

if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}