用递归方法对二叉树进行先序、中序和后序遍历-白红宇

用递归方法对二叉树进行先序、中序和后序遍历

阅读量：4289 次

发布时间：2019-05-27

本文共 1328 字，大约阅读时间需要 4 分钟。

二叉树为：

2 3

4 5 6 7

程序如下：

[cpp]
 
 #include<iostream>  
 #define N 7  
 using namespace std;  
   
 typedef struct node  
 {  
     struct node *leftChild;  
     struct node *rightChild;  
     int data;  
 }BiTreeNode, *BiTree;  
   
 BiTreeNode *createNode(int i)  
 {  
     BiTreeNode * q = new BiTreeNode;  
     q->leftChild = NULL;  
     q->rightChild = NULL;  
     q->data = i;  
   
     return q;  
 }  
   
 BiTree createBiTree()  
 {  
     BiTreeNode *p[N] = {NULL};  
     int i;  
     for(i = 0; i < N; i++)  
         p[i] = createNode(i + 1);  
   
     for(i = 0; i < N/2; i++)  
     {  
         p[i]->leftChild = p[i * 2 + 1];  
         p[i]->rightChild = p[i * 2 + 2];  
     }  
   
     return p[0];  
 }  
   
 int visit(BiTree T)  
 {  
     return T->data;  
 }  
   
 // 先序遍历  
 void preOrderTraverse(BiTree T)  
 {  
     if(T)  
     {  
         cout << visit(T) << " ";  
         preOrderTraverse(T->leftChild);  
         preOrderTraverse(T->rightChild);  
     }  
 }  
   
 // 中序遍历  
 void inOrderTraverse(BiTree T)  
 {  
     if(T)  
     {  
         inOrderTraverse(T->leftChild);  
         cout << visit(T) << " ";  
         inOrderTraverse(T->rightChild);  
     }  
 }  
   
 // 后序遍历  
 void postOrderTraverse(BiTree T)  
 {  
     if(T)  
     {  
         postOrderTraverse(T->leftChild);  
         postOrderTraverse(T->rightChild);  
         cout << visit(T) << " ";  
     }  
 }  
   
 int main()  
 {  
     BiTree T = createBiTree();  
       
     cout << "先序遍历:" << endl;  
     preOrderTraverse(T);  
     cout << endl << endl;  
       
     cout << "中序遍历:" << endl;  
     inOrderTraverse(T);  
     cout << endl << endl;  
       
     cout << "后序遍历:" << endl;  
     postOrderTraverse(T);  
     cout << endl << endl;  
   
     return 0;  
 }  