本文主要是介绍三叉链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在二叉链表的基础上增加了一个指向双亲的指针域。
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用线连起来;
⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线;
⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林,使之层次分明。
森林的遍历
⑴前序(根)遍历:前序遍历森林即为前序遍历森林中的每一棵树。
⑵后序(根)遍历:后序遍历森林即为后序遍历森林中的每一棵树。
这篇关于三叉链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!