😏--二叉树的遍历（前序，中序，后序）

1. 😉详细分析过程

1：

image.png

2:

image.png
3:
image.png

4:

image.png
5:
image.png
6:
image.png
image.png
7: image.png

结果

image.png

附上代码

//
//  main.cpp
//  c++_tree_traverse
//
//  Created by oliva on 2020/1/16.
//  Copyright © 2020 oliva. All rights reserved.
//

#include <iostream>
#include <iomanip>

using namespace std;
// 首先是定义树的结构
class tree{
public:
    int data;
    class tree *left,*right;
};

// 定义树节点
typedef class tree node;
// 定义节点类型的指针
typedef node *btree;

// 函数声明
// 创造树
// 前序遍历
// 中序遍历
// 后序遍历
btree create_tree(btree,int);
void pre(btree);
void in(btree);
void post(btree);

// 主函数的编写
int main(void) {
    // 初始化函数
    int arr[] = {7,4,1,5,16,8,11,12,15,9,2};
    int i =0;
    // 初始化指针 -- root
    btree ptr = NULL;
    // 创造树
    std::cout << "原始数组数据：";
    for(i=0;i<11;i++){
        ptr = create_tree(ptr, arr[i]);
        cout<<"["<<setw(2)<<arr[i]<<"]";
    }
    
    std::cout<<std::endl;
    // 前序遍历树
    std::cout<<"前序遍历结果:"<<endl;
    pre(ptr);
    
    // 中序遍历树
    std::cout<<"中序遍历结果:"<<endl;
    in(ptr);
    
    // 后序遍历树
    std::cout<<"后序遍历结果:"<<endl;
    post(ptr);
    
    std::cout << "Hello, World!\n";
    return 0;
}
btree create_tree(btree root,int val){
    // 创建需要的指针： 新节点，当前节点，备份节点
    btree newnode,current,backup =  NULL;
    
    //  创建新的节点对象，指分配了内存空间
    newnode = new node;
    newnode->data = val;
    newnode->left = NULL;
    newnode->right  = NULL;
    
    // 开始
    if(root ==  NULL){
        root = newnode;
        return root;
    }else{
        // 从当前节点开始循环，直到为空
        for(current=root;current!= NULL;){
            // 备份当前节点
            backup = current;
            // 当前节点的内容大于 传进来的值
            if(current->data > val){
                current=current->left;
            }else{
                current=current->right;
            }
        }
        // 将先有的树和新的节点连接起来
        if(backup->data >val){
            backup->left = newnode;
        }else{
            backup->right = newnode;
        }
        return root;
    }
}

void pre(btree ptr){
    if(ptr != NULL){
        cout << "["<<setw(2)<<ptr->data<<"]";
        pre(ptr->left);
        pre(ptr->right);
    }
}
void in(btree ptr){
    if(ptr != NULL){
        in(ptr->left);
        cout << "["<<setw(2)<<ptr->data<<"]";
        in(ptr->right);
    }
    
}
void post(btree ptr){
    if(ptr != NULL){
        post(ptr->left);
        post(ptr->right);
        cout << "["<<setw(2)<<ptr->data<<"]";
    }
}