C++二叉树

1、定义一个二叉树结构体

#include<iostream>
using namespace std;

typedef struct TreeNode {
    char data;
    struct TreeNode *lchild, *rchild;
}TreeNode, *Bitree;

此处取别名时，我认为*Bitree加不加*都可以，只是后面定义树的时候有区别。加*后面定义Bitree T;不加的话Bitree *T。

2、建立二叉树

为了确定二叉树是否每个结点都有左右孩子，对其进行扩展，也就是将二叉树的每个结点的空指针引出一个虚结点，并赋予一个特定值（此处我们为"#"）如上图所示。

void CreateBitree(BiTree &T) 
{
    char NodeData;
    cout << "请输入结点字符(一个字符)：";
    cin >> NodeData;
    if (NodeData == '#') {
        T = NULL;
    }
    else {
        T = new TreeNode;  //开辟空间
        if (!T)
            return;
        T->data = NodeData;
        CreateBitree(T->Ichild);  //构造左结点
        CreateBitree(T->Rchild);  //构造右结点
    }
}

传参时形参为*T或者&T都可以看个人习惯，主要是需要通过地址传递。

3、前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树(根左右)

//前序遍历
void PreOrderTraverse(BiTree T)
{
    if (!T)
        return;
    cout << T->data;
    PreOrderTraverse(T->Ichild);
    PreOrderTraverse(T->Rchild);
}

4、中序遍历

先中序遍历左子树，然后访问根节点，再中序遍历右子树(左根右)

//中序遍历
void InOrderTraverse(BiTree T)
{
    if (!T)
        return;
    InOrderTraverse(T->Ichild);
    cout << T->data;
    InOrderTraverse(T->Rchild);
}

5、后序遍历

先后序遍历左子树，然后后序遍历右子树，再访问根节点(左右根)

//后序遍历
void PostOrderTraverse(BiTree T)
{
    if (!T)
        return;
    PostOrderTraverse(T->Ichild);
    PostOrderTraverse(T->Rchild);
    cout << T->data;
}

完整代码

//二叉树

//定义二叉树结构体
typedef struct TreeNode {
    char data;
    struct TreeNode *Ichild, *Rchild;
}TreeNode, *BiTree;

//建立二叉树
void CreateBitree(BiTree &T) 
{
    char NodeData;
    cout << "请输入结点字符(一个字符)：";
    cin >> NodeData;
    if (NodeData == '#') {
        T = NULL;
    }
    else {
        T = new TreeNode;  //开辟空间
        if (!T)
            return;
        T->data = NodeData;
        CreateBitree(T->Ichild);  //构造左结点
        CreateBitree(T->Rchild);  //构造右结点
    }
}

//前序遍历
void PreOrderTraverse(BiTree T)
{
    if (!T)
        return;
    cout << T->data;
    PreOrderTraverse(T->Ichild);
    PreOrderTraverse(T->Rchild);
}

//中序遍历
void InOrderTraverse(BiTree T)
{
    if (!T)
        return;
    InOrderTraverse(T->Ichild);
    cout << T->data;
    InOrderTraverse(T->Rchild);
}

//后序遍历
void PostOrderTraverse(BiTree T)
{
    if (!T)
        return;
    PostOrderTraverse(T->Ichild);
    PostOrderTraverse(T->Rchild);
    cout << T->data;
}

int main()
{
    BiTree T;
    cout << "建立二叉树" << endl;
    CreateBitree(T);
    cout << "前序遍历：";
    PreOrderTraverse(T);
    cout << endl;

    cout << "中序遍历：";
    InOrderTraverse(T);
    cout << endl;

    cout << "后序遍历：";
    PostOrderTraverse(T);
    cout << endl;
    return 0;
}

总结

以上为二叉树建立及最常见的三种遍历的个人理解，本人小白，主要用来记录，如有错误，欢迎大佬们指点出来。