[数据结构与算法]?将树转化为二叉树代码实现?

核心思路是在插入的时候，如果儿子结点为空，就将新结点插入儿子节点的的位置，如果儿子结点不为空，就将新结点作为兄弟结点插入兄弟节点的位置。插入的数据哪来，其实就是普通树的数据。下面代码是直接输入结点数据了。（估计这节的内容不太会考）

#include<iostream>
using namespace std;

//定义了一个名为pSTreeNode的指针类型, 它指向结构体STreeNode
typedef struct STreeNode *pSTreeNode;
// 定义了一个名为TreeDataType的int类型
typedef int TreeDataType;

//定义树节点结构体
struct STreeNode {
    TreeDataType data;
    pSTreeNode pFirstChild;
    pSTreeNode pNextBrother;
    //下面注释的定义其实是和上面的定义等价的
    //int data;
    //STreeNode* pFirstChild;
    //STreeNode* pNextBrother;

    //结构体构造函数
    STreeNode(TreeDataType Value) {
        data = Value;
        pFirstChild = NULL;
        pNextBrother = NULL;
    }
};

//定义类
class CTree{
public:
    pSTreeNode pRoot;

    CTree(){
        pRoot = NULL;
    }
    CTree(TreeDataType Value){
        pRoot = new STreeNode(Value);
    }
    ~CTree(){
        if (pRoot == NULL)
            return;
        FreeMemory(pRoot);
    }
    //该函数是为了插入子结点或兄弟结点
    //parentValue:该点的父亲节点;Value:该点的值
    void Insert(TreeDataType parentValue, TreeDataType Value){
        if(pRoot==NULL)
            return;
        //先找出父亲节点
        pSTreeNode pFindNode = Search(pRoot, parentValue);
        //父结点为空，说明插不进去，直接返回
        if(pFindNode == NULL)
            return;
        //父结点不为空，父结点的左孩子为空
        if(pFindNode->pFirstChild == NULL){
            pFindNode->pFirstChild = new STreeNode(Value);
            return;
        }else{
            //父结点不空，父结点的左孩子也不空，那么插入右兄弟即可
            //注意该函数左边传入的参数，传入的是左结点（左结点作为父亲啦！）
            InsertBrother(pFindNode->pFirstChild, Value);
            return;
        }
    }
    //插入右兄弟节点
    void InsertBrother(pSTreeNode pBrotherNode, TreeDataType Value){
        //传入的父亲已经有兄弟结点了，那么将该兄弟结点作为父亲传入下一个插入右节点的函数中
        if(pBrotherNode->pNextBrother != NULL)
            InsertBrother(pBrotherNode->pNextBrother, Value);
        else {
            //传入的父亲的兄弟节点还是空的，直接插入即可
            pBrotherNode->pNextBrother = new STreeNode(Value);
            return;
        }
    }
    //查找函数
    pSTreeNode Search(pSTreeNode pNode, TreeDataType Value){
        if (pNode == NULL)
            return NULL;
        //直接根节点就是所找，返回根节点
        if (pNode->data == Value)
            return pNode;
        //除了根节点就没有其他节点了
        if (pNode->pFirstChild==NULL && pNode->pNextBrother == NULL)
            return NULL;
        else{
            if (pNode->pFirstChild != NULL) {
                //左结点不为空，直接递归搜索左结点
                pSTreeNode pNodeTemp = Search(pNode->pFirstChild, Value);
                if (pNodeTemp != NULL)
                    return pNodeTemp;
                else {
                    //左结点为空，那么就递归搜索右兄弟
                    return Search(pNode->pNextBrother, Value);
                }
            }
            else
                return Search(pNode->pNextBrother, Value);
        }
    }
    //前序遍历
    void Preorder(pSTreeNode pNode){
        if(pNode == NULL)
            return;
        cout << " " << pNode->data << " ";
        Preorder(pNode->pFirstChild);
        Preorder(pNode->pNextBrother);
    }
    //中序遍历
    void Inorder(pSTreeNode pNode){
        if (pNode == NULL)
            return;
        Inorder(pNode->pFirstChild);
        cout << " " << pNode->data << " ";
        Inorder(pNode->pNextBrother);
    }
    //后序遍历
    void postorder(pSTreeNode pNode){
        if (pNode == NULL)
            return;
        postorder(pNode->pFirstChild);
        postorder(pNode->pNextBrother);
        cout<<" "<<pNode->data<<" ";
    }
    //释放堆内存
    void FreeMemory(pSTreeNode pNode){
        if(pNode == NULL)
            return;
        if(pNode->pFirstChild != NULL)
            FreeMemory(pNode->pFirstChild);
        if(pNode->pNextBrother != NULL)
            FreeMemory(pNode->pNextBrother);
        delete pNode;
        pNode = NULL;
    }
};

//主函数
int main(){
    CTree *pTree = new CTree(1);
    pTree->Insert(1, 2);
    pTree->Insert(1, 3);
    pTree->Insert(1, 4);
    pTree->Insert(1, 5);
    pTree->Insert(1, 6);
    pTree->Insert(1, 7);
    pTree->Insert(4, 8);
    pTree->Insert(5, 9);
    pTree->Insert(5, 10);
    pTree->Insert(6, 11);
    pTree->Insert(6, 12);
    pTree->Insert(6, 13);
    pTree->Insert(10, 14);
    pTree->Insert(10, 15);
    cout << "前序遍历:" << endl;
    pTree->Preorder(pTree->pRoot);
    cout << endl;
    cout << "中序遍历:" << endl;
    pTree->Inorder(pTree->pRoot);
    cout << endl;
    cout << "后序遍历:" << endl;
    pTree->postorder(pTree->pRoot);
    cout << endl;
    delete pTree;
    pTree = NULL;
    return 0;
}

我是花花，祝自己也祝您变强了~