二叉树的创建与转换

一、二叉树的创建

遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，比如建立二叉树。

为了建立一颗二叉树，将二叉树中每个结点的空指针引入一个虚结点，其值为一特定值如 " # ",以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。

扩展二叉树的前序遍历序列：A B # D # # C # #

设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针,二叉链表的建立过程是: 首先输入根结点,若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL;否则输入的字符应该赋给root->data，之后依次递归建立它的左子树和右子树。

BiTree::BiTree()
{
    root = Creat(root);
}

// 写法1
BiNode* BiTree::Creat(BiTree *bt)
{
    input(ch);    // 输入结点的数据信息，假设为字符
    if(ch == '#')
    {
        bt = NULL;
    }
    else
    {
        bt = New BiNode;
        bt->data= ch;
        bt->lchild = Creat(bt->lchild);
        bt->rchild = Creat(bt->rchild);
    }
    return bt;
}

//写法2
BiNode* BiTree::Creat(BiTree* &bt)
{
    input(ch);    // 输入结点的数据信息，假设为字符
    if(ch == '#')
    {
        bt = NULL;
    }
    else
    {
        bt = New BiNode;
        bt->data= ch;
        Creat(bt->lchild);  // 递归建立左子树
        Creat(bt->rchild);  // 递归建立右子树
    }
    return bt;
}

二、根据二叉树的遍历确定二叉树

已知前序序列为ABC，则可能的二叉树有5钟：

已知前序遍历序列为ABC，后序遍历序列为CAB，则下列二叉树都满足条件：

只有根据前(红)序遍历和中序遍历结果能唯一确定二叉树

前序：ABCDEFGHI 后序：BCAEDGHFI 首先找到根节点A，就可以确定左子树和右子树 然后依次确定左右子树的根节点 如图：

三、二叉树的转换 1.树转换为二叉树

树和二叉树之间的关系： (1) 树：兄弟关系 二叉树 ：双亲和右孩子

(2)树：双亲和长子 二叉树：双亲和左孩子

树----> 二叉树 =(1)兄弟加线

(2)保留双亲与第一个孩子的连线，删除与其他孩子的连线

(3)顺时针转动，使之层次分明 小结： (1加线——树中所有相邻兄弟之间加一条连线

(2)去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线

(3)层次调整——以根结点为轴心,将树顺时针转动一定的角度,使之层次分明

注： (1)树的前序遍历等于二叉树的前序遍历

(2)树的后序遍历等于与二叉树的中序遍历

2.森林转换为二叉树

(1)将森林中的每棵树转化为二叉树

(2)从第二棵二叉树开始，依次把后一颗的二叉树的根节点作为前一棵二叉树根节点的右孩子，当所有二叉树连接起来，此时所得到的二叉树就是森林转换得到的二叉树

二叉树转换为树(森林）

(1)加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、…，都与结点y用线连起来

(2去线——删去原二叉树中所有的双亲结点与右孩子结点的连线

(3)层次调整——整理所得到的树或森林，使之层次分明

四、森林的遍历

森林有两种遍历方法: (1)前序（根）遍历:前序遍历森林即为前序遍历森林中的每一棵树

⑵后序（根）遍历:后序遍历森林即为后序遍历森林中的每一棵树。