詳細瞭解C語言二叉樹的建立與遍歷
這裡給一個樣例樹：
代碼：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* 二叉樹的二叉鏈表結點結構定義 */
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/* 先序遍歷建立一個二叉樹 */
void Create (BiTree *T) // 二級指針改變地址的地址
{
char ch;
scanf("%c",&ch);
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
return ;
else
{
(*T)->data=ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
}
/* 二叉樹的前序遞歸遍歷算法 */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
/* 二叉樹的中序遞歸遍歷算法 */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
/* 二叉樹的後序遞歸遍歷算法 */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
int main()
{
printf("請按先序遍歷的結果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
Create(&T);
printf("先序遍歷的結果為：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍歷的結果為：\n");
InOrderTraverse(T);
printf("\n");
printf("後序遍歷的結果為：\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}
輸出結果如下
PS：下面是一個用C++裡面的取引用代替瞭二級指針
#include<bits/stdc++.h>
using namespace std;
/* 二叉樹的二叉鏈表結點結構定義 */
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/* 先序遍歷建立一個二叉樹 */
void Create (BiTree &T) // C++取引用
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
return ;
else
{
T->data=ch;
Create(T->lchild);
Create(T->rchild);
}
}
}
/* 二叉樹的前序遞歸遍歷算法 */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
/* 二叉樹的中序遞歸遍歷算法 */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
/* 二叉樹的後序遞歸遍歷算法 */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
int main()
{
printf("請按先序遍歷的結果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
Create(T);
printf("先序遍歷的結果為：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍歷的結果為：\n");
InOrderTraverse(T);
printf("\n");
printf("後序遍歷的結果為：\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}
PS:遍歷的PLus版，想要的自取。
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int cmax=1e2+5;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
void CreateBiTree (BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return ;
}
void PreOrder(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
// 非遞歸中序遍歷
void InOrderTraverse(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
p=new BiTNode;
while((p=S.top())&&p)
S.push(p->lchild);
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
cout<<p->data<<" ";
S.push(p->rchild);
}
}
}
// 先序非遞歸遍歷
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
while((p=S.top())&&p)
{
cout<<p->data<<" ";
S.push(p->lchild);
}
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
S.push(p->rchild);
}
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
// 非遞歸層次遍歷
void LeverTraverse(BiTree T)
{
queue <BiTree> Q;
BiTree p;
p=T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(visit(p->lchild)==1)
Q.push(p->lchild);
if(visit(p->rchild)==1)
Q.push(p->rchild);
}
}
//主函數
int main()
{
BiTree T;
char j;
int flag=1;
printf("本程序實現二叉樹的操作。\n");
printf("葉子結點以#表示。\n");
printf("可以進行建立二叉樹，遞歸先序、中序、後序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");
printf("請建立二叉樹。\n");
printf("建樹將以三個空格後回車結束。\n");
printf("例如:1 2 3 4 5 6 (回車)\n\n");
CreateBiTree(T); //初始化隊列
getchar();
printf("\n");
printf("請選擇: \n");
printf("1.遞歸先序遍歷\n");
printf("2.遞歸中序遍歷\n");
printf("3.遞歸後序遍歷\n");
printf("4.非遞歸中序遍歷\n");
printf("5.非遞歸先序遍歷\n");
printf("6.非遞歸層序遍歷\n");
printf("0.退出程序\n");
while(flag)
{
scanf(" %c",&j);
switch(j)
{
case '1':if(T)
{
printf("遞歸先序遍歷二叉樹:");
PreOrder(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '2':if(T)
{
printf("遞歸中序遍歷二叉樹:");
InOrder(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '3':if(T)
{
printf("遞歸後序遍歷二叉樹:");
PostOrder(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '4':if(T)
{
printf("非遞歸中序遍歷二叉樹:");
InOrderTraverse(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '5':if(T)
{
printf("非遞歸先序遍歷二叉樹:");
PreOrder_Nonrecursive(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '6':if(T)
{
printf("非遞歸層序遍歷二叉樹:");
LeverTraverse(T);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
default:flag=0;printf("程序運行結束，按任意鍵退出!\n");
}
}
}
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！