建立排序二叉树并中序遍历

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

分析：中序遍历也叫中根遍历，顾名思义是把根节点放在中间来遍历，其遍历顺序为左子节点–>根节点–>右子节点。

方法一：

#include<iostream>
using namespace std;

struct node                     //二叉树结点结构
{
    int data;
    node *left;                 //右子树结点指针
    node *right;                //左子树结点指针
};

class Btree
{
    node *root;                 //根结点的指针
public:
    Btree()
     {
        root = NULL;
     }
    void CreateBtree(int);
    void Inorder()              //中序遍历主过程
     {
        Inorder(root);
        cout << endl;
     }
    void Inorder(node *);       //中序遍历子过程
};

void Btree::CreateBtree(int x)
{
    node *newnode = new node;
    newnode->data = x;
    newnode->left = NULL;
      newnode->right = NULL;

    if(NULL == root)
      {
        root = newnode;
     }
    else
    {
        node *back;
        node *current = root;

        while(current != NULL)   //找到要插入newnode的节点指针
        {
            back = current;
            if(current->data > x)
            {
                current=current->left;
            }
            else
            {
                current = current->right;
            }
        }

        if(back->data > x)
        {
            back->left = newnode;
        }
        else
        {
            back->right = newnode;
        }
    }
}

void Btree::Inorder(node *root)    //中序遍历排序二叉树
{
    if(root)
    {
        Inorder(root->left);
        cout << root->data << " ";
        Inorder(root->right);
    }
}

int main()
{
    Btree A;
    int arr[]={7, 4, 1, 5, 12, 8, 13, 11}; //排序二叉树：左子结点<根节点<右子节点 cout << "建立排序二叉树:" << endl; for(int i = 0; i < 8; i++) { cout << arr[i] << " "; A.CreateBtree(arr[i]); } cout << endl << "中序遍历序列:" << endl; A.Inorder(); return 0; }

运行结果：

建立排序二叉树:
7 4 1 5 12 8 13 11
中序遍历序列:
1 4 5 7 8 11 12 13
Press any key to continue