中序遍歷c演算法
1. c語言 關於二叉樹的創建和遍歷(中序遍歷)
這個還是我學《數據結構》時做的有關二叉樹的練習呢，本來是全的，包括樹的初始化，建立，遍歷（中序、前序、後序和層次），還有輸出，復制，刪除節點，求深度，樹的刪除等等，看你只問了有關創建和中序遍歷的，所以選了一部分給你，供你參考吧！
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定義數據結構
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉樹
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉樹
BiTNode *s[MaxSize];//這里定義了一個數組用作堆棧方便檢查輸入和操作
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void inorder(BiTNode *BT){//中序遍歷二叉樹——遞歸形式
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}
void main(){
BiTNode *BT;
printf("以廣義表形式表示輸入的二叉數 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
//如果想要自己輸入，可以將下邊的注釋去掉，然後自己按照廣義表形式輸入，
//（如上例的形式）此處為了方便查看，用了默認的數值
//這里之所以用此種形式（廣義表形式輸入）是為了保證輸入的數組成的二叉樹完全符合你所定義的樹的形狀
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*/
InitBtree(BT);//初始化二叉樹
CreateBiTree(BT,string);//創建二叉樹
printf("\n中序遍歷二叉樹順序為： ");
inorder(BT);//中序遍歷二叉樹
printf("\n");
}
程序不復雜，所以只是加了必要和最簡單的注釋，相信你看看應該完全可以理解的，祝你進步！
2. 二叉樹中序遍歷非遞歸演算法(c語言實現）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序，中序 建樹
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序遞歸遍歷
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}
//中序非遞歸遍歷
void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}
//主函數
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//測試事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
幾個月前自己編寫，原版
vc++ 6.0實驗通過
怎麼樣，老闆，第一次上網路知道，好激動
給點面子
給分！給分啊
3. 關於c語言中二叉樹前，中，後序遍歷，沒看懂，請問該如何理解比如中序遍歷:左，根，右。那麼拿到一個
以你的圖為准，不管是先序遍歷，中序遍歷，還是後序遍歷，都以根為主，也就是你看根就可以了。就那中序遍歷來說，按規則來，順序是左根右，根就是F，對於根的左就是F左邊的一大堆，右就是F右邊的那一堆，就可以寫成 （）F（），對左來說，根就是C，C的左右和上邊的確定方法一樣，對右來說，根就是E，E的有是有的，但E的左是空，寫成（（）C（））F（E（）），這樣依次寫下來就是ACBDFEG。當然寫的時候不需要寫括弧，只是為了說明方便，先序遍歷和後序遍歷一樣。
4. c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#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
}
5. C語言中，到底先序遍歷、中序遍歷、後續遍歷怎麼看的...真的快瘋掉了！求高人指點指點...淚目
先序遍歷就是「根左右」，不管你現在在哪個節點，都是按這種規則。上面的題目：根是A，左是B，右是C，所以是A-》B，在當前根節點B，還是按上述規則，那麼接下來到D，D之後沒有子節點，返回B，遍歷E-》X，X之後沒有子節點，返回E，E的子節點都遍歷完了，返回B，B的子節點都遍歷完了，返回A，接下來遍歷右子樹，規則同上。
中序遍歷就是「左根右」，對於A來說，先遍歷B，對於B來說，先遍歷D，對於D來說，已經沒有左子樹，所以遍歷D，D沒有右子樹,返回B，遍歷B，B有右子樹E，對於E來說，先遍歷X，完了返回E，E完了返回B，B完了返回A，遍歷A，遍歷右子樹，規則同上。
後序遍歷就是跟先序遍歷相反的，先遍歷右子樹，再左子樹，最後才是根。
好好思考一下。
6. 二叉樹編程 先序建立 中序遍歷
理論分析
數據結構的基礎知識中重要的一點就是能否根據兩種不同遍歷序列的組合（有三種：先序+中序，先序+後序，中序+後序），唯一的確定一棵二叉樹。然後就是根據二叉樹的不同遍歷序列（先序、中序、後序），重構二叉樹。顯然，這三種組合並不是都能唯一確定二叉樹的，其中先序+後序就不能唯一確定一棵二叉樹，下面是關於該問題的證明與結論。
①給定二叉樹結點的前序序列和中序序列，可以唯一確定該二叉樹。
證明：因為先序序列的第一個元素是根結點，該元素將二叉樹中序序列分成兩部分，左邊（假設有L個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（假設有R個元素）是右子樹，若為空，則右子樹為空。根據前序遍歷中"根-左子樹-右子樹"的順序，則由從先序序列的第二元素開始的L個結點序列和中序序列根左邊的L個結點序列構造左子樹，由先序序列最後R個元素序列與中序序列根右邊的R個元素序列構造右子樹。
②由中序序列和先序序列能唯一確定一棵二叉樹，但是由先序序列和後序序列不能唯一確定一棵二叉樹，因無法確定左右子樹兩部分。
反例：任何結點只有左子樹的二叉樹和任何結點只有右子樹的二叉樹，其前序序列相同，後序序列相同，但卻是兩棵不同的二叉樹。
這兩棵二叉樹的先序遍歷序列都為2-1-3，後序遍歷序列都為3-1-2。但是顯然它們是不同的二叉樹，所以根據先序序列和後序序列並不能唯一確定二叉樹。
③已經說明由二叉樹的先序序列和中序序列可以確定一棵二叉樹，現在來證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。
證明：
當n=1時，只有一個根結點，由中序序列和後序序列可以確定這棵二叉樹。
設當n=m-1時結論成立，即結點數目為m-1時，中序序列和後序序列可以唯一確定二叉樹。現證明當n=m時結論成立。
設中序序列為S1,S2,…,Sm,後序序列是P1,P2,…,Pm。因後序序列最後一個元素Pm是根，則在中序序列中可找到與Pm相等的結點（設二叉樹中各結點互不相同）Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結點，S1,S2,…,Si-1是左子樹的中序序列，而Si+1,Si+2,…,Sm是右子樹的中序序列。
若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結點數是m-1,則{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一確定右子樹，從而也確定了二叉樹。
若i=m，則Sm是根，這時二叉樹的右子樹為空，左子樹的結點數是m-1，則{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一確定左子樹，從而也確定了二叉樹。
最後，當1<i<m時，Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由於後序遍歷是"左子樹-右子樹-根結點"，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉樹的左子樹和右子樹的後序遍歷序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一確定二叉樹的左子樹，由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一確定二叉樹的右子樹。
3、構造思路
1）根據先序遍歷序列和中序遍歷序列構建二叉樹
假定已知二叉樹如下：
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那麼它的先序遍歷和中序遍歷的結果如下：
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
需要關注的幾個要點：
1）先序遍歷的第一個結點總是根結點。如上圖中的二叉樹，根結點為7，也是先序遍歷的第一個值。先序遍歷時父親結點總是在孩子結點之前遍歷。
2）可以觀察到在中序遍歷中，7是第4個值（從0開始算起）。由於中序遍歷順序為：左子樹，根結點，右子樹。所以7左邊的{4,10,3,1} 這四個結點屬於左子樹，而根結點7右邊的{11,8,2}屬於右子樹。
3）可以從上面的結論很輕松的得到遞歸式。在構建了根結點7後，我們可以根據中序遍歷{4, 10, 3, 1} 和{11,8,2}分別構建它的左子樹和右子樹。我們同時需要相應的先序遍歷結果用於發現規律。我們可以由先序遍歷知道左右子樹的先序遍歷分別是{10，4, 3, 1}和{2， 8， 11}。左右子樹也分別為二叉樹，由此可以遞歸來解決問題。
4）關於如何得到根結點在中序遍歷中的位置問題還沒有細講，如果使用線性掃描查找位置，則每次查找需要O（N）的時間，如果二叉樹平衡的話，則整個演算法需要O（NlgN）的時間。如果二叉樹不平衡，則最壞情況需要O（N^2）時間。為了提高效率，我們可以考慮使用哈希表來存儲與查找根結點在中序遍歷中的位置，每次查找只需要O（1）的時間，這樣構建整棵樹只需要O（N）的時間。 這里為了方便，只是用了一個數組用於標記位置，要是用哈希表也會很方便。需要注意的是，這里的二叉樹結點值不能有相同的值。
代碼：
// 輸入：先序和中序的第一個指針和最後一個指針，
// 遞歸調用，每次確定當前結點
BinaryTreeNode* ConstructCore(int* startPerorder, int* endPreorder, int* startInorder, int* endInorder)
{
//先序第一個為根節點
int rootValue = startPerorder[0];
BinaryTreeNode* root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
//遞歸退出條件
if ( startPerorder==endPreorder )
{
if ( startInorder==endInorder && *startPerorder==*endInorder )
return root;
else
throw std::exception("Invalid input."); //異常處理
}
// 在中序遍歷中找到根節點的值
int* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder!=rootValue)
++rootInorder;
//異常處理
if ( rootInorder==endInorder && *rootInorder!=rootValue)
throw std::exception("Invalid input.");
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPerorder+leftLength;
if ( leftLength > 0 )
{
//構建左子樹
root->m_pLeft=ConstructCore(startPerorder+1,leftPreorderEnd,startInorder, rootInorder-1);
}
if ( leftLength < endPreorder-startPerorder )
{
//構建右子樹
root->m_pRight= ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
}
return root;
}
//根據先序和中序構建二叉樹
BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
if(preorder==NULL || inorder==NULL || length <=0)
return NULL;
return ConstructCore(preorder, preorder+length-1, inorder,inorder+length-1);
}
void TraverseTreePostorder(BinaryTreeNode* proot)
{
if ( proot == NULL )
return;
if ( proot->m_pLeft != NULL )
TraverseTreePostorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePostorder(proot->m_pRight);
cout << proot->m_nValue << " ";
}
主函數測試代碼：
int main()
{
int preorder[] = {7,10,4,3,1,2,8,11};
int inorder[] = {4,10,3,1,7,11,8,2};
BinaryTreeNode* pRoot = Construct(preorder,inorder,8);
TraverseTreePostorder(pRoot);
cout <<endl;
return 0;
}
2）根據中序遍歷序列和後序序遍歷序列構建二叉樹
原理和上述原理基本一致，任然沿用上述例子
___7___
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那麼它的中序遍歷和後序序遍歷的結果如下：
inorder = {4,10,3,1,7,11,8,2}
postorder = {7,10,4,3,1,2,8,11}
代碼：
// 輸入：中序和後序的第一個指針和最後一個指針，
// 遞歸調用，每次確定當前結點
BinaryTreeNode* ConstructCore_in_post(int* startInorder, int* endInorder, int* startPostorder, int* endPostorder)
{
//後序最後一個結點為根結點
int rootValue = *endPostorder;
BinaryTreeNode* root = new BinaryTreeNode;
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
//遞歸退出條件
if ( startInorder==endInorder )
{
if ( startPostorder==endPostorder && *startInorder==*endPostorder )
return root;
else
throw std::exception("Invalid input."); //異常處理
}
//在中序中找到當前根節點
int* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder != rootValue )
++rootInorder;
int leftLength = rootInorder - startInorder;
int* leftInorderEnd = startInorder+leftLength-1;
if ( leftLength > 0 )
{
//構建左子樹
root->m_pLeft=ConstructCore_in_post(startInorder,leftInorderEnd,startPostorder, startPostorder+leftLength-1);
}
if ( leftLength < endInorder-startInorder )
{
//構建右子樹
root->m_pRight= ConstructCore_in_post(rootInorder+1,endInorder,startPostorder+leftLength,endPostorder-1);
}
return root;
}
//根據先序和中序構建二叉樹
BinaryTreeNode* Construct(int* inorder, int* postorder, int length)
{
if(inorder==NULL || postorder==NULL || length <=0)
return NULL;
return ConstructCore_in_post(inorder, inorder+length-1, postorder, postorder+length-1);
}
void TraverseTreePreorder(BinaryTreeNode* proot)
{
if ( proot == NULL )
return;
cout << proot->m_nValue << " ";
if ( proot->m_pLeft != NULL )
TraverseTreePreorder(proot->m_pLeft);
if ( proot->m_pRight != NULL )
TraverseTreePreorder(proot->m_pRight);
}
主函數測試：
int main()
{
int inorder[] = {4,10,3,1,7,11,8,2};
int postorder[] = {4,1,3,10,11,8,2,7};
BinaryTreeNode* pRoot = Construct(inorder,postorder,8);
TraverseTreePreorder(pRoot);
cout <<endl;
return 0;
}
7. 用c或c++實現遍歷二叉樹的中序演算法，急求
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case'(':top++;St[top]=p;k=1;break;
case')':top--;break;
case',':k=2;break;
default:p=p=(BTNode * )malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
extern void CreateBTNode(BTNode *&b,char *str);
extern void DispBTNode(BTNode *b);
void PreOrder(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void PreOrder1(BTNode *b)
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
top++;
St[top]=b;
while(top>-1)
{
p=St[top];
top--;
printf("%c",p->data);
if(p->rchild!=NULL)
{
top++;
St[top]=p->rchild;
}
if(p->lchild!=NULL)
{
top++;
St[top]=p->lchild;
}
}
printf("\n");
}
}
void InOrder(BTNode *b)
{
if(b!=NULL)
{
InOrder(b->lchild);
printf("%c",b->data);
InOrder(b->rchild);
}
}
void InOrder1(BTNode *b)
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)
{
top++;
St[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=St[top];
top--;
printf("%c",p->data);
p=p->rchild;
}
}
printf("\n");
}
}
void PostOrder(BTNode *b)
{
if(b!=NULL)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c",b->data);
}
}
void PostOrder1(BTNode *b)
{
BTNode *St[MaxSize];
BTNode *p;
int flag,top=-1;
if(b!=NULL)
{
do
{
while(b!=NULL)
{
top++;
St[top]=b;
b=b->lchild;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
b=St[top];
if(b->rchild==p)
{
printf("%c",b->data);
top--;
p=b;
}
else
{
b=b->rchild;
flag=0;
}
}
}
while(top!=-1);
printf("\n");
}
}
void TravLevel(BTNode *b)
{
BTNode *Qu[MaxSize];
int front,rear;
front=rear=0;
if(b!=NULL)
printf("%c",b->data);
rear++;
Qu[rear]=b;
while(rear!=front)
{
front=(front+1)%MaxSize;
b=Qu[front];
if(b->lchild!=NULL)
{
printf("%c",b->lchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->lchild;
}
if(b->rchild!=NULL)
{
printf("%c",b->rchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->rchild;
}
}
printf("\n");
}
void main()
{
BTNode *b;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉樹b:");DispBTNode(b);printf("\n\n");
printf("層次遍歷序列:");
TravLevel(b);
printf("\n");
printf("先序遍歷序列:\n");
printf("遞歸演算法:");PreOrder(b);printf("\n");
printf("非遞歸演算法:");PreOrder1(b);printf("\n");
printf("先序遍歷序列:\n");
printf("遞歸演算法:");InOrder(b);printf("\n");
printf("非遞歸演算法:");InOrder1(b);printf("\n");
printf("後續遍歷演算法:\n");
printf("遞歸演算法:");PostOrder(b);printf("\n");
printf("非遞歸演算法:");PostOrder1(b);printf("\n");
}
8. 二叉樹的建立、中序遍歷（用C語言實現）
#include "iostream.h"
//#include "exception.h"
//樹節點類
int count=0,mode=0,data=0;
class BinaryTreeNode
{
friend class BinaryTree;
public :
BinaryTreeNode()
{
LeftChild = RightChild = 0;
}
BinaryTreeNode(const int& e)
{
data = e;
LeftChild = RightChild = 0;
}
BinaryTreeNode(const int& e, BinaryTreeNode *l,BinaryTreeNode *r)
{
data = e;
LeftChild = l;
RightChild = r;
}
private :
int data;
BinaryTreeNode *LeftChild, //左子樹
*RightChild; // 右子樹
} ;
class BinaryTree
{
friend class BinaryTreeNode;
public :
BinaryTree( )
{
root = 0;
}
~ BinaryTree( ) { }
bool IsEmpty( ) const
{
return ((root) ? false : true);
}
bool Root(int& x) const
{// 取根節點的d a t a域，放入x
// 如果沒有根節點，則返回f a l s e
if (root)
{
x = root->data;
return true;
}
else return false; // 沒有根節點
}
void MakeTree(const int& element)
{
root = new BinaryTreeNode (element);
}
void MakeTree(const int& element,BinaryTree& left,BinaryTree& right)
{// 將left, right和element 合並成一棵新樹
// left, right和this必須是不同的樹
// 創建新樹
root = new BinaryTreeNode (element, left.root, right.root);
// 阻止訪問l e f t和r i g h t
left.root = right.root = 0;
}
void Inorder(void (*Visit) (BinaryTreeNode *u))
{
InOrder ( Visit,root ) ;
}
void Delete( )
{
PostOrder (Free,root);
root = 0;
}
private :
BinaryTreeNode *root; // 根節點指針
static void Free(BinaryTreeNode *t)
{
delete t;
}
void InOrder(void(*Visit) (BinaryTreeNode *u),BinaryTreeNode *t)
{// 中序遍歷
if (t)
{
InOrder(Visit, t->LeftChild);
Visit( t ) ;
InOrder( Visit, t->RightChild);
}
}
9. c語言中序遍歷怎麼做
求採納
10. C語言的二叉樹中序遍歷問題。
#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是關於二叉樹操作的11個簡單演算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};
/* 1.初始化二叉樹 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}
/* 2.建立二叉樹(根據a所指向的二叉樹廣義表字元串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定義s數組為存儲根結點指針的棧使用 */
int top = -1; /* 定義top作為s棧的棧頂指針，初值為-1,表示空棧 */
int k; /* 用k作為處理結點的左子樹和右子樹，k = 1處理左子樹，k = 2處理右子樹 */
int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字元串，初值為0 */
*bt = NULL; /* 把樹根指針置為空，即從空樹開始建立二叉樹 */
/* 每循環一次處理一個字元，直到掃描到字元串結束符\0為止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 對空格不作任何處理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("棧空間太小！\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉樹廣義表字元串錯誤!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 為掃描下一個字元修改i值 */
}
return;
}
/* 3.檢查二叉樹是否為空，為空則返回1,否則返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}
/* 4.求二叉樹深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 對於空樹，返回0結束遞歸 */
}else{
int dep1 = BTreeDepth(bt->left); /* 計算左子樹的深度 */
int dep2 = BTreeDepth(bt->right); /* 計算右子樹的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}
/* 5.從二叉樹中查找值為x的結點，若存在則返回元素存儲位置，否則返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分別向左右子樹遞歸查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}
/* 6.輸出二叉樹(前序遍歷) */
void printBTree(struct BTreeNode *bt)
{
/* 樹為空時結束遞歸，否則執行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 輸出根結點的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉樹，使之變為一棵空樹 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍歷 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 訪問根結點 */
preOrder(bt->left); /* 前序遍歷左子樹 */
preOrder(bt->right); /* 前序遍歷右子樹 */
}
return;
}
/* 9.前序遍歷 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍歷左子樹 */
printf("%c ", bt->data); /* 訪問根結點 */
inOrder(bt->right); /* 中序遍歷右子樹 */
}
return;
}
/* 10.後序遍歷 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 後序遍歷左子樹 */
postOrder(bt->right); /* 後序遍歷右子樹 */
printf("%c ", bt->data); /* 訪問根結點 */
}
return;
}
/* 11.按層遍歷 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 將樹根指針進隊 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 隊列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使隊首指針指向隊首元素 */
p = q[front];
printf("%c ", p->data);
/* 若結點存在左孩子，則左孩子結點指針進隊 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若結點存在右孩子，則右孩子結點指針進隊 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}
/************************************************************************/
/*
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉樹根結點的指針 */
char *b; /* 用於存入二叉樹廣義表的字元串 */
elemType x, *px;
initBTree(&bt);
printf("輸入二叉樹廣義表的字元串：\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以廣義表的形式輸出：\n");
printBTree(bt); /* 以廣義表的形式輸出二叉樹 */
printf("\n");
printf("前序："); /* 前序遍歷 */
preOrder(bt);
printf("\n");
printf("中序："); /* 中序遍歷 */
inOrder(bt);
printf("\n");
printf("後序："); /* 後序遍歷 */
postOrder(bt);
printf("\n");
printf("按層："); /* 按層遍歷 */
levelOrder(bt);
printf("\n");
/* 從二叉樹中查找一個元素結點 */
printf("輸入一個待查找的字元：\n");
scanf(" %c", &x); /* 格式串中的空格跳過空白字元 */
px = findBTree(bt, x);
if(px){
printf("查找成功：%c\n", *px);
}else{
printf("查找失敗！\n");
}
printf("二叉樹的深度為：");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}