数据结构_二叉树遍历
?
課題二
一、?? 目的
二叉樹的遍歷算法實現
二、?? 實習環境
個人計算機，Windows操作系統，Visual C++6.0編譯開發環境
三、?? 實習內容、步驟與要求
遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
遞歸算法的算法實現：
先序遍歷：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；(2) 遍歷左子樹；(3) 遍歷右子樹。
中序遍歷：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹； (2)訪問根結點；(3)遍歷右子樹。
后序遍歷：
若二叉樹非空，則依次執行如下操作：
（1）遍歷左子樹；(2)遍歷右子樹；(3)訪問根結點。
非遞歸算法的實現：
中序遍歷：
??對于任一結點P，
? 1)若其左孩子不為空，則將P入棧并將P的左孩子置為當前的P，然后對當前結點P再進行相同的處理；
??2)若其左孩子為空，則取棧頂元素并進行出棧操作，訪問該棧頂結點，然后將當前的P置為棧頂結點的右孩子；
? 3)直到P為NULL并且棧為空則遍歷結束
后序遍歷：
要保證根結點在左孩子和右孩子訪問之后才能訪問，因此對于任一結點P，先將其入棧。
1）???????? 如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。
2）???????? 若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結點前面被訪問。
?
四：源程序：
#include<stdlib.h>
#include<stdio.h>
#define MAX? 50
#define MAS? 20
#define CHAR 1
?
typedef char elem;
//定義二叉樹的數據結構
typedef struct node{
??? elem data;//二叉樹的值
??? ?struct node *lchild;??? //左孩子
??? ?struct node *rchild;//右孩子
??? ?struct node *parent;//父節點
}BinTNode,*BinTree;
//定義二叉樹的初始化函數
BinTNode *Init_BinTree(BinTNode *tree){
??? ?tree=NULL; //將NULL賦值給tree
??? ?return tree; //返回tree
}
//創建二叉樹
BinTNode *Create_BinTree(BinTNode *tree){
??? elem ch;
??? scanf("%c",&ch);???????? //將鍵入值賦給二叉樹的節點
??? ?if(ch==' ')??????????????? // 以空格作為空左孩子和空右孩子的表示
?????? tree=NULL;
??? ?else{?????? ?//申請空間，以及通過對左右孩子的遞歸完成二叉樹的創建
?????? tree=(BinTNode *)malloc(sizeof(BinTNode));
??? ??? if(!tree)
?????????? exit(0);
??? ? tree->data=ch;
??? ? tree->parent=NULL;
??? ? tree->lchild=Create_BinTree(tree->lchild);
??? ? if(tree->lchild)
?????? ? tree->lchild->parent=tree;
??? ? tree->rchild=Create_BinTree(tree->rchild);
??? ? if(tree->rchild)
?????? ? tree->rchild->parent=tree;
??? ?}
??? ?return tree;//返回tree
}
? //在屏幕上輸出創建的二叉樹，采用遞歸算法
void PrintTree(BinTNode *tree,int i){
??? if(tree!=NULL){????????????????? //采用條件編譯對CHAR事先進行編譯
?????? PrintTree(tree->rchild,i+5);
??? #if CHAR
?????? if(tree->data!=' ')
?????? printf("%*c\n",i,tree->data);
??? #else
?????? if(tree->data!=' ')
?????? printf("%*d\n",i,tree->data);
??? #endif
?????? PrintTree(tree->lchild,i+5);
?????? i=i-5;
??? }
}
?
/*先序遍歷（遞歸）*/
void? Pre_Order(BinTNode *tree){
??? if(tree!=NULL){
?????? printf("%c"" ",tree->data);
?????? Pre_Order(tree->lchild);
?????? Pre_Order(tree->rchild);
??? }
}
?
?
/*中序遍歷（遞歸）*/
void In_Order(BinTNode *tree){
??? if(tree!=NULL){
?????? In_Order(tree->lchild);
?????? printf("%c"" ",tree->data);
?????? In_Order(tree->rchild);
??? }
}
//中序遍歷（非遞歸），利用棧結構存儲數據
void In_OrderX(BinTNode *tree,void(*visit)(elem)){
??? BinTNode *p,*stack[MAS];
??? int top;
??? top=0;? p=tree;
??? while(top!=0||p!=NULL){
?????? while(p!=NULL){
?????????? stack[top]=p; top++;
?????????? p=p->lchild;
?????? ?}
?????? if(top!=0){
?????????? p=stack[top-1];
?????????? top--;
?????????? visit(p->data);
?????????? p=p->rchild;
?????? }
??? }
}
/*后序遍歷（遞歸）*/
void Bac_Order(BinTNode *tree){
??? if(tree!=NULL){
?????? Bac_Order(tree->lchild);
?????? Bac_Order(tree->rchild);
?????? printf("%c"" ",tree->data);
??? }
}
/*后序遍歷（非遞歸），利用棧結構存儲數據?? */
void Bac_OrderX(BinTNode *tree,void(*visit)(elem)){
??? BinTNode *p,*stack[MAS];
??? int top;
??? top=0;
??? stack[top]=tree; top++;
??? while(top>0){
?????? p=stack[top-1];
?????? top--;
?????? while(p!=NULL){
?????????? visit(p->data);
?????????? stack[top]=p->rchild;
?????????? top++;
?????????? p=p->lchild;
?????? }
??? }
}
?
void visit(elem e){
??? printf("%c"" ",e);
}
?
?
int main()
{
??? int i;
??? BinTree tree;
??? tree=Init_BinTree(tree);
??? #if CHAR
?????? printf("請先序輸入二叉樹(如:abc? d? e? ):");
??? #else
?????? printf("請先序輸入二叉樹(如:a b??? 表示a為根結點,b為左子樹的二叉樹)\n");
??? #endif
??? tree=Create_BinTree(tree);
??? printf("輸入建立的二叉樹!!!\n");
??? PrintTree(tree,5);
??? do{
?????? printf("------------------------------------------------------------");
?????? printf("\n 主菜單:");
?????? printf("\n? 1? 先序遍歷(遞歸)");
?????? printf("\n? 2? 中序遍歷(遞歸)");
?????? printf("\n? 3? 中序遍歷(非遞歸)");
?????? printf("\n? 4? 后序遍歷(遞歸)");
?????? printf("\n? 5? 后序遍歷(非遞歸)");
??? //? printf("\n? 6????????????????? ");
?????? printf("\n? 0??? 退出");
?????? printf("\n----------------------------------------------------------");
?????? printf("\n");
?????? printf("親，請輸入功能數字:");
?????? scanf("%d",&i);
?????? switch(i){
?????????? case 1: printf("先序遍歷(遞歸)結果為:");
????????????????? Pre_Order(tree); break;
?????????? case 2: printf("中序遍歷(遞歸)結果為:");
????????????????? In_Order(tree); break;
??? ??????? case 3: printf("中序遍歷(非遞歸)結果為:");
????????????????? In_OrderX(tree,visit) ;? break;
?????????? case 4:??? printf("后序遍歷(遞歸)結果為:");
????????????????? Bac_Order(tree); break;
?????????? case 5: printf("后序遍歷(非遞歸)結果為:");
????????????????? Bac_Order(tree,visit); break;
?????????? case 0: exit(0);
?????????? default :printf("親，請輸入--菜單--中的功能數字!");
?????? }
??? printf("\n \n");
??? }
??? while(i>0||i<8);
??? return 0;
}
?
轉載于:https://www.cnblogs.com/askDing/p/KE.html
總結
以上是生活随笔為你收集整理的数据结构_二叉树遍历的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 3DMM配置
- 下一篇： TCPUDP测试工具的使用