C++ 遍歷二叉樹實(shí)例詳解
更新時(shí)間：2017年06月02日 08:48:18 投稿：lqh
這篇文章主要介紹了C++ 遍歷二叉樹實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
C++ 遍歷二叉樹實(shí)例詳解
2叉數(shù)又叫紅黑樹，關(guān)于2叉數(shù)的遍歷問題，有很多，一般有三種常用遍歷方法：
(1)前序遍歷(2)中序遍歷(3)后續(xù)遍歷
以下是經(jīng)典示例：
#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
#include <math.h >
#define MaxSize 20
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
//建立二叉樹
void CreateBiTree(BiTree *T)
{
char ch;
scanf("%c",&ch);
getchar();
if(ch==' ')
{
printf("不產(chǎn)生子樹。\n");
*T=NULL;
}
else
{
if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))
{
printf("分配空間失敗");
return;
}//生成一個(gè)新節(jié)點(diǎn)
(*T)->data = ch;
printf("產(chǎn)生左右子樹。\n");
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
//遞歸前序遍歷
void Preorder(BiTNode *T)
{
if(T)
{
printf("%c ",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//遞歸中序遍歷
void Inorder(BiTNode *T)
{
if(T)
{
Inorder(T->lchild);
printf("%c ",T->data);
Inorder(T->rchild);
}
}
//遞歸后序遍歷
void Postorder(BiTNode *T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c ",T->data);
}
}
//非遞歸前序遍歷
void NPreorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int top=-1;
if(T)
{
top++;
stack[top]=T; //根節(jié)點(diǎn)進(jìn)棧
while(top>-1) //棧不為空時(shí)循環(huán)
{
p=stack[top]; //退棧并訪問該節(jié)點(diǎn)
top--;
printf("%c ",p->data);
if(p->rchild) //右孩子進(jìn)棧
{
top++;
stack[top]=p->rchild;
}
if(p->lchild) //左孩子進(jìn)棧
{
top++;
stack[top]=p->lchild;
}
}
}
}
//非遞歸中序遍歷
void NInorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int top=-1;
p=T;
while(p||top!=-1)
{
if(p)
{
top++;
stack[top]=p;
p=p->lchild;
} //根節(jié)點(diǎn)進(jìn)棧，遍歷左子樹
else //根節(jié)點(diǎn)退棧，訪問根節(jié)點(diǎn)，遍歷右子樹
{
p=stack[top];
top--;
printf("%c ",p->data);
p=p->rchild;
}
}
}
//非遞歸后序遍歷
void NPostorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int flag,top=-1;
do
{
while(T)
{
top++;
stack[top]=T;
T=T->lchild;
} //所有左節(jié)點(diǎn)進(jìn)棧
p=NULL; //p總是指向當(dāng)前節(jié)點(diǎn)的前一個(gè)已經(jīng)訪問過的節(jié)點(diǎn)
flag=1; //flag為1表示當(dāng)前節(jié)點(diǎn)已經(jīng)訪問過了
while(top!=-1 && flag)
{
T=stack[top];
if(T->rchild==p) //右子樹不存在或者已經(jīng)被訪問過時(shí)
{
printf("%c ",T->data);
top--;
p=T; //調(diào)整p指針
}
else
{
T=T->rchild;
flag=0; //調(diào)整訪問標(biāo)志
}
}
} while(top!=-1);
}
//層次遍歷二叉樹
void Translever(BiTNode *T)
{
struct node
{
BiTNode *vec[MaxSize];
int f,r; //r為隊(duì)尾，f為隊(duì)頭
}queue;
BiTNode *p;
p=T;
queue.f=0;
queue.r=0;
if(T)
printf("%c ", p->data);
queue.vec[queue.r]=p;
queue.r=queue.r+1;
while(queue.f<queue.r)
{
p=queue.vec[queue.f];
queue.f=queue.f+1;
if(p->lchild)
{
printf("%c ",p->lchild->data);
queue.vec[queue.r]=p->lchild;
queue.r=queue.r+1;
}
if(p->rchild)
{
printf("%c ",p->rchild->data);
queue.vec[queue.r]=p->rchild;
queue.r=queue.r+1;
}
}
printf("\n");
}
//求二叉樹的深度
int Depth(BiTNode *T)
{
int dep1,dep2;
if(T==NULL)
return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
}
//輸出二叉樹
void Disptree(BiTNode *T)
{
if(T)
{
printf("%c",T->data);
if(T->lchild || T->rchild)
{
printf("(");
Disptree(T->lchild);
if(T->rchild)
printf(",");
Disptree(T->rchild);
printf(")");
}
}
}
main.cpp
void main()
{
BiTree T=NULL;
char j;
int sign = 1;
printf("本程序可以進(jìn)行建立二叉樹、遞歸與非遞歸先序、中序、后序遍歷二叉樹、層次遍歷二叉樹、輸出二叉樹的擴(kuò)展序列的操作。\n");
printf("請(qǐng)將二叉樹的先序序列輸入以建立二叉樹，葉子節(jié)點(diǎn)用空格代替。\n");
printf("您必須一個(gè)一個(gè)地輸入字符。\n");
while(sign)
{
printf("請(qǐng)選擇: \n");
printf("0.生成二叉樹 1.求二叉樹的深度\n");
printf("2.遞歸先序遍歷 3.非遞歸先序遍歷\n");
printf("4.遞歸中序遍歷 5.非遞歸中序遍歷\n");
printf("6.遞歸后序遍歷 7.非遞歸后序遍歷\n");
printf("8.層次遍歷 9.輸出二叉樹的廣義表形式\n");
printf("q.退出程序\n");
scanf("%c",&j);
getchar();
switch(j)
{
case '0':
printf("生成二叉樹:");
CreateBiTree(&T);
printf("\n");
printf("\n");
break;
case '1':
if(T)
{
printf("此二叉樹的深度為:");
printf("%d",Depth(T));
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '2':
if(T)
{
printf("遞歸先序遍歷二叉樹:");
Preorder(T);
printf("\n");
printf("\n");
}
else
printf("二叉樹為空!\n");
break;
case '3':
if(T)
{
printf("非遞歸先序遍歷二叉樹:");
NPreorder(T);
printf("\n");
printf("\n");
}
else
printf("二叉樹為空!\n");
break;
case '4':
if(T)
{
printf("遞歸中序遍歷二叉樹:");
Inorder(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '5':
if(T)
{
printf("非遞歸中序遍歷二叉樹:");
NInorder(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '6':
if(T)
{
printf("遞歸后序遍歷二叉樹:");
Postorder(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '7':
if(T)
{
printf("非遞歸后序遍歷二叉樹:");
NPostorder(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '8':
if(T)
{
printf("層次遍歷二叉樹:");
Translever(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case '9':
if(T)
{
printf("輸出二叉樹:");
Disptree(T);
printf("\n");
printf("\n");
}
else printf("二叉樹為空!\n");
break;
default:
sign=0;
printf("程序運(yùn)行結(jié)束，按任意鍵退出!\n");
}
}
}
示例：
轉(zhuǎn)換成雙向鏈表
先序列：H F C D M I N
中序列：C F D H I M N
后序列：C D F I N M H
#include <iostream>
using namespace std;
struct BSTreeNode{
char m_val;
BSTreeNode *m_pLeft;
BSTreeNode *m_pRight;
};
BSTreeNode *pHead;//鏈表顯示的頭結(jié)點(diǎn)
BSTreeNode *pListIndex;//游標(biāo)指針
void showOrderLiust(BSTreeNode *pCurrent);
void createBSTree(BSTreeNode *&pCurrent,char ch)
{
if (NULL == pCurrent) {
pCurrent = new BSTreeNode;
pCurrent->m_val = ch;
pCurrent->m_pLeft = NULL;
pCurrent->m_pRight = NULL;
}else {
if (pCurrent->m_val > ch) {
createBSTree(pCurrent->m_pLeft,ch);
}else if (pCurrent->m_val < ch) {
createBSTree(pCurrent->m_pRight,ch);
}
else
{
return;
}
}
}
//遍歷二叉樹/*先序遍歷*/
void PreOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL!=pCurrent)
{
//先遍歷根節(jié)點(diǎn)
cout<<pCurrent->m_val<<endl;
//在遍歷左節(jié)點(diǎn)
PreOrderTraverse(pCurrent->m_pLeft);
//在遍歷右節(jié)點(diǎn)
PreOrderTraverse(pCurrent->m_pRight);
}
}
//中序遍歷
void InOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL != pCurrent->m_pLeft) {
InOrderTraverse(pCurrent->m_pLeft);
}
showOrderLiust(pCurrent);
//在遍歷右節(jié)點(diǎn)
if (NULL != pCurrent->m_pRight) {
InOrderTraverse(pCurrent->m_pRight);
}
}
//后序遍歷
void EndOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL != pCurrent->m_pLeft) {
EndOrderTraverse(pCurrent->m_pLeft);
}
cout<<pCurrent->m_val<<endl;
//在遍歷右節(jié)點(diǎn)
if (NULL != pCurrent->m_pRight) {
EndOrderTraverse(pCurrent->m_pRight);
}
}
/*該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向*/
void showOrderLiust(BSTreeNode *pCurrent)
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex) {
pListIndex->m_pRight = pCurrent;
}else
{
pHead = pCurrent;
}
pListIndex = pCurrent;
cout<<pCurrent->m_val<<endl;
}
int main(int argc,char**argv)
{
BSTreeNode *pRoot = NULL;
pHead = NULL;
pListIndex = NULL;
createBSTree(pRoot,'H');
createBSTree(pRoot,'F');
createBSTree(pRoot,'C');
createBSTree(pRoot,'D');
createBSTree(pRoot,'M');
createBSTree(pRoot,'I');
createBSTree(pRoot,'N');
PreOrderTraverse(pRoot);
InOrderTraverse(pRoot);
EndOrderTraverse(pRoot);
delete pRoot;
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C++ 詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹
搜索二叉樹是一種具有良好排序和查找性能的二叉樹數(shù)據(jù)結(jié)構(gòu)，包括多種操作，本篇只介紹插入，排序（遍歷），和刪除操作，重點(diǎn)是刪除操作比較復(fù)雜2022-04-04
c語言中字符串分割函數(shù)及實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猚語言中字符串分割函數(shù)及實(shí)現(xiàn)方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-05-05
這篇文章主要該大家分享C語言佩奇借書的練習(xí)，文章主要通過描述佩奇借書的問題然后確定程序框架將結(jié)果運(yùn)算出來，下面來看詳細(xì)內(nèi)容吧,需要的朋友可以參考一下2022-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)客房管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了VC++的if語句應(yīng)用范圍分析,對(duì)VC++初學(xué)者有很好的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2014-08-08
C++中的繼承問題(繼承基本概念、菱形虛擬繼承的對(duì)象模型)
這篇文章主要介紹了C++中的繼承問題(繼承基本概念、菱形虛擬繼承的對(duì)象模型)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
C++ 實(shí)現(xiàn)的通訊錄管理系統(tǒng)詳解
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要為大家詳細(xì)介紹了C語言圖書管理系統(tǒng)簡潔版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
棧是一種特殊的線性表,其只允許在固定的一端進(jìn)行插入和刪除元素操作,進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂,另一端稱為棧底,本文給大家介紹了C語言實(shí)現(xiàn)數(shù)組棧的代碼示例,需要的朋友可以參考下2024-07-07
樹是計(jì)算機(jī)算法最重要的非線性結(jié)構(gòu)。因?yàn)闃淠芎芎玫孛枋鼋Y(jié)構(gòu)的分支關(guān)系和層次特性，所以在計(jì)算機(jī)科學(xué)和計(jì)算機(jī)應(yīng)用領(lǐng)域有著廣泛的應(yīng)用。這篇文章我就帶大家一起了解一下樹、二叉樹這種結(jié)構(gòu)，下篇文章會(huì)重點(diǎn)向大家介紹二叉樹的遍歷算法2022-05-05