二叉樹的遍歷演算法代碼
A. c語言二叉樹遍歷代碼
1.t = malloc(sizeof(tree));
2.t->rchild =createTree();
3.void qianxu(tree *t)
4.zhongxu(t->lchild );//再讀左子樹
printf("%c",t->data);//先讀根結點
zhongxu(t->rchild );//再讀右子樹
5.houxu(t->lchild );//再讀左子樹
houxu(t->rchild );//再讀右子樹
printf("%c",t->data);//先讀根結點
6.return 0;
7.n=count(t->lchild)+count(t->rchild)+1;
8.t1->data=t->data;
9.return t1;
10.return m+1;
PS:注意有些語句結尾是沒有分號的
B. 二叉樹遍歷的演算法實現
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。 根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問根結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之中（間）。
③ LRN：後序遍歷(PostorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。 1．先（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
2．中（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
3．後（根）序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。 用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild）；
③ printf(%c，T->data）； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder 計算中序遍歷擁有比較簡單直觀的投影法，如圖
⑴在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次（或第三次）經過結點時進行的，則是中序遍歷（或後序遍歷）。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
⑵上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前驅結點和一個後繼結點。為了區別於樹形結構中前驅（即雙親）結點和後繼（即孩子）結點的概念，對上述三種線性序列，要在某結點的前驅和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前驅結點是D，前序後繼結點是E；中序前驅結點是E，中序後繼結點是F；後序前驅結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前驅結點是A，後繼結點是E和F。
二叉鏈表基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree **T){ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參（根指針）本身 char ch； if((ch=getchar())=='') *T=NULL； //讀入空格，將相應指針置空 else{ //讀人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode））； //生成結點 （*T)->data=ch； CreateBinTree(&(*T)->lchild）； //構造左子樹 CreateBinTree(&(*T)->rchild）； //構造右子樹 }}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
示例
設root是一根指針（即它的類型是BinTree），則調用CreateBinTree(&root）後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼（遞歸演算法）： #include<iostream>#include<cstdio>#include<cmath>#include<iomanip>#include<cstdlib>#include<ctime>#include<algorithm>#include<cstring>#include<string>#include<vector>#include<list>#include<stack>#include<queue>#include<map>#include<set>usingnamespacestd;typedefintT;classbst{structNode{Tdata;Node*L;Node*R;Node(constT&d,Node*lp=NULL,Node*rp=NULL):data(d),L(lp),R(rp){}};Node*root;intnum;public:bst():root(NULL),num(0){}voidclear(Node*t){if(t==NULL)return;clear(t->L);clear(t->R);deletet;}~bst(){clear(root);}voidclear(){clear(root);num=0;root=NULL;}boolempty(){returnroot==NULL;}intsize(){returnnum;}TgetRoot(){if(empty())throwemptytree;returnroot->data;}voidtravel(Node*tree){if(tree==NULL)return;travel(tree->L);cout<<tree->data<<'';travel(tree->R);}voidtravel(){travel(root);cout<<endl;}intheight(Node*tree){if(tree==NULL)return0;intlh=height(tree->L);intrh=height(tree->R);return1+(lh>rh?lh:rh);}intheight(){returnheight(root);}voidinsert(Node*&tree,constT&d){if(tree==NULL)tree=newNode(d);elseif(ddata)insert(tree->L,d);elseinsert(tree->R,d);}voidinsert(constT&d){insert(root,d);num++;}Node*&find(Node*&tree,constT&d){if(tree==NULL)returntree;if(tree->data==d)returntree;if(ddata)returnfind(tree->L,d);elsereturnfind(tree->R,d);}boolfind(constT&d){returnfind(root,d)!=NULL;}boolerase(constT&d){Node*&pt=find(root,d);if(pt==NULL)returnfalse;combine(pt->L,pt->R);Node*p=pt;pt=pt->R;deletep;num--;returntrue;}voidcombine(Node*lc,Node*&rc){if(lc==NULL)return;if(rc==NULL)rc=lc;elsecombine(lc,rc->L);}boolupdate(constT&od,constT&nd){Node*p=find(root,od);if(p==NULL)returnfalse;erase(od);insert(nd);returntrue;}};intmain(){bstb;cout<<inputsomeintegers:;for(;;){intn;cin>>n;b.insert(n);if(cin.peek()=='
')break;}for(;;){cout<<inputdatapair:;intod,nd;cin>>od>>nd;if(od==-1&&nd==-1）break;b.update(od,nd);}}
C. 二叉樹的建立與遍歷(C語言)
樓主你好~~~「ф」字元的源代碼我忘記了，我這里有一個自己寫過的遍歷演算法
#include<iostream.h>
typedef struct btnode
{
char data;
struct btnode *Lchild,*Rchild;
}*bitreptr;
void Create(bitreptr &p)
{
char n;
p=new btnode;
cin>>n;
if(n!='#')
{
p->data=n;
Create(p->Lchild);
Create(p->Rchild);
}
else
p=NULL;
}
void preorder(bitreptr &p)
{
if(p)
{
cout<<p->data<<" ";
preorder(p->Lchild);
preorder(p->Rchild);
}
}
void midorder(bitreptr &p)
{
if(p)
{
midorder(p->Lchild);
cout<<p->data<<" ";
midorder(p->Rchild);
}
}
void postorder(bitreptr &p)
{
if(p)
{
postorder(p->Lchild);
postorder(p->Rchild);
cout<<p->data<<" ";
}
}
void change(bitreptr &p)
{
bitreptr t,q;
if(p)
{
t=p->Lchild;
q=p->Rchild;
p->Lchild=q;
p->Rchild=t;
change(p->Lchild);
change(p->Rchild);
}
}
void main()
{
char i;
cout<<"請選擇所需功能（'A'輸出該二叉樹序列，'B'輸出交換後二叉樹序列)"<<endl;
cin>>i;
bitreptr p;
cout<<"輸入數據：";
Create(p);
switch(i)
{
case 'A':
{
cout<<"前序:";
preorder(p);
cout<<endl;
cout<<"中序:";
midorder(p);
cout<<endl;
cout<<"後序:";
postorder(p);
cout<<endl;
}break;
case 'B':
{
change(p);
cout<<"交換二叉樹前序:";
preorder(p);
cout<<endl;
cout<<"交換二叉樹中序:";
midorder(p);
cout<<endl;
cout<<"交換二叉樹後序:";
postorder(p);
cout<<endl;
}break;
}
}
這個演算法輸入時要以「#」代表空節點，及將[測試數據] 「ABCффDEфGффFффф」改成「ABC##DE#G##F###」即可。另外我的演算法包括了二叉樹左右子樹交換的代碼「change(bitreptr &p)」，只要樓主稍作修改就可以得到你想要的完美結果~
D. 二叉樹的遍歷c++代碼，要求同時使用遞歸和非遞歸
遞歸的：
#include <stdlib.h>
#include <stdio.h>
#define STACK_INIT_SIZE 50 /*MAXSIZE 存儲空間初始分配量*/
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
typedef char TElemType;
typedef struct s_BiTNode /*定義二叉樹結構*/
{
TElemType data;
struct s_BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
Status CreateBiTree(BiTree *T);
Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status Visit(TElemType e);
void main() /*main() 函數*/
{
BiTree Tr=NULL;
printf("下面以'根左右'的先序擴展順序構造二叉樹:\n");
printf("\n請輸入二叉樹元素,(/表示空),如 ABDG///EH//IK///C/F/J//\n");
if(CreateBiTree(&Tr)) /*調用 CreateBiTree()*/
printf("構造二叉樹成功!\n");
else
printf("構造二叉樹失敗!\n");
printf("\n先序遍歷序列為: ");
PreOrderTraverse(Tr,Visit);
printf("\n中序遍歷序列為: ");
InOrderTraverse(Tr,Visit);
printf("\n後序遍歷序列為: ");
PostOrderTraverse(Tr,Visit);
printf("\n");
getch();
}
Status CreateBiTree(BiTree *Tree)
{
TElemType ch;
scanf("%c",&ch);
if(ch == '/')
(*Tree) = NULL;
else
{
if(!((*Tree) = (BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
(*Tree)->data = ch;
CreateBiTree(&((*Tree)->lchild));
CreateBiTree(&((*Tree)->rchild));
}
return (OK);
}/*CreateBiTree*/
Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e))//*Fun是指向函數Visit的指針
//他的參數是(TElemType e) 他的返回類型是int
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Fun))
if(PreOrderTraverse(T->rchild,Fun))
return OK;
return ERROR;
}
else
return OK;
}
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
if(T)
{
if(InOrderTraverse(T->lchild,Fun))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Fun))
return OK;
return ERROR;
}
else
return OK;
}/*InOrderTraverse*/
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
if(T)
{
if(PostOrderTraverse(T->lchild,Fun))
if(PostOrderTraverse(T->rchild,Fun))
{
Visit(T->data);
return OK;
}
return ERROR;
}
else
return OK;
}
Status Visit(TElemType e)
{
printf("%c",e);
return OK;
}
非遞歸的：
#include <stdlib.h>
#include <stdio.h>
#define STACK_INIT_SIZE 50 /*MAXSIZE 存儲空間初始分配量*/
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
typedef char TElemType;
typedef struct s_BiTNode /*定義二叉樹結構*/
{
TElemType data;
struct s_BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
Status CreateBiTree(BiTree *T);
Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status Visit(TElemType e);
void main() /*main() 函數*/
{
BiTree Tr=NULL;
printf("下面以'根左右'的先序擴展順序構造二叉樹:\n");
printf("\n請輸入二叉樹元素,(/表示空),如 ABDG///EH//IK///C/F/J//\n");
if(CreateBiTree(&Tr)) /*調用 CreateBiTree()*/
printf("構造二叉樹成功!\n");
else
printf("構造二叉樹失敗!\n");
printf("\n先序遍歷序列為: ");
PreOrderTraverse(Tr,Visit);
printf("\n中序遍歷序列為: ");
InOrderTraverse(Tr,Visit);
printf("\n後序遍歷序列為: ");
PostOrderTraverse(Tr,Visit);
printf("\n");
getchar();
}
Status CreateBiTree(BiTree *Tree)
{
TElemType ch;
scanf("%c",&ch);
if(ch == '/')
(*Tree) = NULL;
else
{
if(!((*Tree) = (BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
(*Tree)->data = ch;
CreateBiTree(&((*Tree)->lchild));
CreateBiTree(&((*Tree)->rchild));
}
return (OK);
}/*CreateBiTree*/
Status PreOrderTraverse(BiTree T,Status (*Fun)(TElemType e))
{
BiTNode *St[STACK_INIT_SIZE],*p;
int top=-1;
if(T)
{
top++;
St[top]=T;
while(top>-1)
{
p=St[top];
top--;
Visit(p->data);
if(p->rchild)
{
top++;
St[top]=p->rchild;
}
if(p->lchild)
{
top++;
St[top]=p->lchild;
}
}
return OK;
}
else
return OK;
}
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
BiTNode *St[STACK_INIT_SIZE],*p;
int top=-1;
if(T)
{
p=T;
while(top>-1||p)
{
while(p)
{
top++;
St[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=St[top];
top--;
Visit(p->data);
p=p->rchild;
}
}
return OK;
}
else
return OK;
}/*InOrderTraverse*/
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
BiTNode *St[STACK_INIT_SIZE];
BiTNode *p;
int flag,top=-1;
if(T)
{
do
{
while(T)
{
top++;
St[top]=T;
T=T->lchild;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
T=St[top];
if(T->rchild==p)
{
Visit(T->data);
top--;
p=T;
}
else
{
T=T->rchild;
flag=0;
}
}
}while(top!=-1);
}
else
return OK;
}
Status Visit(TElemType e)
{
printf("%c",e);
return OK;
}
E. 如何用C語言實現層次遍歷二叉樹
下面是c語言的前序遍歷二叉樹的演算法，在這里假設的節點元素值假設的為字元型，
說明：演算法中用到了結構體，也用到了遞歸的方法，你看看怎麼樣，祝你好運！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定義鏈表結構
{
elemtype
data;
//定義節點值
struct
note
*lchild;
//定義左子節點值
struct
note
*rchild;
//定義右節點值
}btree;
preorder(btree
*root)
//前序遍歷
{
if(roof!=null)
//如果不是空節點
{
printf("%c\n",root->data);
//輸出當前節點
preorder(root->lchild);
//遞歸前序遍歷左子節點
preorder(root->rchild);
//遞歸前序遍歷右子節點
}
return;
//結束
}
F. 編程實現以上二叉樹中序遍歷操作，輸出遍歷序列，求寫代碼~~
#include<stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree;
BiTree CreateBiTree(BiTree T) //先序遍歷構造二叉樹
{
char ch;
scanf("%c",&ch);
if(ch=='#') //#代表空指針
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //申請結點
if(!T)
exit(OVERFLOW);
T->data=ch; //生成根結點
T->lchild=CreateBiTree(T->lchild); //構造左子樹
T->rchild=CreateBiTree(T->rchild); //構造右子樹
}
return T;
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍歷二叉樹
if(T)
{
if(InOrderTraverse(T->lchild,visit))
if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else
return OK;
}
Status PrintElement(TElemType e)
{
printf("%-2c",e);
return OK;
}
void main()
{
BiTree T=NULL;
printf("請輸入構造二叉樹的字元序列：");
T=CreateBiTree(T);
if(T)
printf("二叉樹建立成功！
");
else
printf("二叉樹構造失敗！！！
");
printf("中序遍歷二叉樹：");
InOrderTraverse(T,PrintElement);
printf("
");
}
G. 求用C語言實現二叉樹層次遍歷的遞歸演算法，謝謝！！！
演算法思想：層次遍歷目前最普遍用的就是隊列的那種方式，不是遞歸，但是用到while循環，既然題目要求用遞歸，可以用遞歸實現該while循環功能。演算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//測試程序，創建樹輸入例如ABD##E##C##,根左右創建的方式。
如下代碼是測試通過的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
H. 編寫一個程序，實現二叉樹的先序遍歷，中序遍歷，後序遍歷的各種遞歸和非遞歸演算法，以及層次遍歷的演算法
文件 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
}
這樣可以么？
I. 二叉樹的層次遍歷演算法
二叉樹的層次遍歷演算法有如下三種方法：
給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：
之後大家就可以自己畫圖了，下面給出程序代碼：
[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;
}
J. 遍歷二叉樹
遍歷方案：
1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍歷序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
A
/ \
B C
/ / \
D E F
圖
（1） 中序序列（inorder traversal）
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列（postorder traversal）
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
（4）層次遍歷（level traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右訪問每一個結點，從而實現對每一個結點的遍歷
注意：
（1）在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2）上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鏈表的構造
1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】
設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼(遞歸演算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]