C++ 遍歷二叉樹實例詳解
2叉數又叫紅黑樹，關于2叉數的遍歷問題，有很多，一般有三種常用遍歷方法：
(1)前序遍歷(2)中序遍歷(3)后續遍歷
以下是經典示例：
#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("不產生子樹。/n"); *T=NULL; } else { if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) { printf("分配空間失敗"); return; }//生成一個新節點 (*T)->data = ch; printf("產生左右子樹。/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; //根節點進棧 while(top>-1) //棧不為空時循環 { p=stack[top]; //退棧并訪問該節點 top--; printf("%c ",p->data); if(p->rchild) //右孩子進棧 { top++; stack[top]=p->rchild; } if(p->lchild) //左孩子進棧 { 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; } //根節點進棧，遍歷左子樹 else //根節點退棧，訪問根節點，遍歷右子樹 { 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; } //所有左節點進棧 p=NULL; //p總是指向當前節點的前一個已經訪問過的節點 flag=1; //flag為1表示當前節點已經訪問過了 while(top!=-1 && flag) { T=stack[top]; if(T->rchild==p) //右子樹不存在或者已經被訪問過時 { printf("%c ",T->data); top--; p=T; //調整p指針 } else { T=T->rchild; flag=0; //調整訪問標志 } } } while(top!=-1); } //層次遍歷二叉樹 void Translever(BiTNode *T) { struct node { BiTNode *vec[MaxSize]; int f,r; //r為隊尾，f為隊頭 }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("本程序可以進行建立二叉樹、遞歸與非遞歸先序、中序、后序遍歷二叉樹、層次遍歷二叉樹、輸出二叉樹的擴展序列的操作。/n"); printf("請將二叉樹的先序序列輸入以建立二叉樹，葉子節點用空格代替。/n"); printf("您必須一個一個地輸入字符。/n"); while(sign) { printf("請選擇: /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("程序運行結束，按任意鍵退出!/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;//鏈表顯示的頭結點 BSTreeNode *pListIndex;//游標指針 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) { //先遍歷根節點 cout<<pCurrent->m_val<<endl; //在遍歷左節點 PreOrderTraverse(pCurrent->m_pLeft); //在遍歷右節點 PreOrderTraverse(pCurrent->m_pRight); } } //中序遍歷 void InOrderTraverse(BSTreeNode *pCurrent) { if (NULL == pCurrent) { return; } if (NULL != pCurrent->m_pLeft) { InOrderTraverse(pCurrent->m_pLeft); } showOrderLiust(pCurrent); //在遍歷右節點 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; //在遍歷右節點 if (NULL != pCurrent->m_pRight) { EndOrderTraverse(pCurrent->m_pRight); } } /*該二元查找樹轉換成一個排序的雙向鏈表。 要求不能創建任何新的結點，只調整指針的指向*/ 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; } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
