三叉链表

三叉链表

在二叉链表的基础上增加了一个指向双亲的指针域。

data、lchild和rchild三个域的含义同二叉链表的结点结构；
parent域为指向该结点的双亲结点的指针。

结点数据类型声明：

template<class T>
struct Node
{T data;Node<T> * lchild, *rchild,*parent;
};

template <class T>
BiNode<T> * BiTree<T>::Creat(BiNode<T> * &root,BiNode<T> *parent)
{T ch;cout<<"请输入创建一棵二叉树的结点数据"<<endl;cin>>ch;if (ch=="#")root = NULL;else{root = new BiNode<T>;       //生成一个结点root->data=ch;root->parent=parent;Creat(root->lchild,root );    //递归建立左子树Creat(root->rchild,root);    //递归建立右子树}return root;
}template<class T>
BiTree<T>::BiTree( int i)
{number=0;Creat(root,NULL);
}

森林转换为二叉树
⑴ 将森林中的每棵树转换成二叉树；
⑵ 从第二棵二叉树开始，
依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，
当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树或森林
⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；
⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；
⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

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