詳細了解C語言二叉樹的建立與遍歷
更新時間：2021年07月30日 16:13:03 作者：LuckyLazyPig
這篇文章主要介紹了C中二叉樹的建立和各種遍歷實例代碼，涉及樹節(jié)點的定義，后序遍歷，層序遍歷，深度優(yōu)先和廣度優(yōu)先等相關(guān)內(nèi)容，具有一定借鑒價值,需要的朋友可以參考下
這里給一個樣例樹：
代碼：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* 二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義 */
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("請按先序遍歷的結(jié)果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
Create(&T);
printf("先序遍歷的結(jié)果為：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍歷的結(jié)果為：\n");
InOrderTraverse(T);
printf("\n");
printf("后序遍歷的結(jié)果為：\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}
輸出結(jié)果如下
PS：下面是一個用C++里面的取引用代替了二級指針
#include<bits/stdc++.h>
using namespace std;
/* 二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義 */
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("請按先序遍歷的結(jié)果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
Create(T);
printf("先序遍歷的結(jié)果為：\n");
PreOrderTraverse(T);
printf("\n");
printf("中序遍歷的結(jié)果為：\n");
InOrderTraverse(T);
printf("\n");
printf("后序遍歷的結(jié)果為：\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);
}
}
//主函數(shù)
int main()
{
BiTree T;
char j;
int flag=1;
printf("本程序?qū)崿F(xiàn)二叉樹的操作。\n");
printf("葉子結(jié)點以#表示。\n");
printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");
printf("請建立二叉樹。\n");
printf("建樹將以三個空格后回車結(jié)束。\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("程序運行結(jié)束，按任意鍵退出!\n");
}
}
}
總結(jié)
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
這篇文章主要介紹了opencv3機器學(xué)習(xí)之EM算法的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
這篇文章主要介紹了c++中try catch的用法小結(jié),需要的朋友可以參考下2018-01-01
關(guān)于C++中cout的使用，相信大家再熟悉不過了，然而對于cout是如何輸出的？輸出的機制是啥，需要進一步的了解。本章娓娓道來。前幾天在網(wǎng)上看到這么一個題目2013-10-10
VSCode下.json文件的編寫之(1) linux/g++ (2).json中參數(shù)與預(yù)定義變量的意義解釋
這篇文章主要介紹了VSCode下.json文件的編寫之(1) linux/g++ (2).json中參數(shù)與預(yù)定義變量的意義解釋,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-03-03
下面小編就為大家?guī)硪黄肅語言編輯畫圖程序的實現(xiàn)方法(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了如何利用Matlab實現(xiàn)山脊圖的繪制，文中的示例代碼講解詳細，對我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2022-05-05
這篇文章主要介紹了 C語言中聯(lián)合體union的實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
從這篇博客開始，我就要和大家介紹有關(guān)二叉搜索樹的知識，它還衍生出了兩棵樹——AVL樹和紅黑樹，在后面兩篇博客我都會介紹。今天先從二叉搜索樹開始引入2022-03-03
這篇文章介紹了C++通過boost.date_time進行時間運算的方法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)井字棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10