文档介绍：二叉树的二叉链表存储结构构建方法假设有关二叉树的二叉链表存储的类型定义如下:typedefstructBiTNode{//结点结构ElemTypedata;//数据域structBiTNode*Lchild;//左孩子指针structBiTNode*Rchild;//右孩子指针}BiTNode,*BiTree;1利用扩展二叉树的先序序列构建只根据二叉树的先序序列是不能唯一确定一棵二叉树的[3]。针对这一问题,可做如下处理:对二叉树中每个结点的空指针引出一个虚结点,设其值为#,表示为空,把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的先序序列可唯一确定这棵二叉树。如图1所示,给出了一棵二叉树的扩展二叉树,以及该扩展二叉树的先序序列。文档收集自网络,仅用于个人学习建立二叉链表的算法如下:voidCreate(BiTree&T){//输入扩展二叉树的先序序列,构建二叉链表scanf(&ch);//输入一个元素if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));//申请根结点T->data=ch;//给根结点数据域赋值Create(T->Lchild);//建左子树Create(T->Rchild);//建右子树}}//Create2利用二叉树的先序序列和中序序列容易证明:由一棵二叉树的先序序列和中序序列可唯一的确定一棵二叉树。基本思想:先根据先序序列的第一个元素建立根结点;然后在中序序列中找到该元素,确定根结点的左、右子树的中序序列;根据左、右子树的中序序列确定左、右子树中结点的个数;再根据结点个数在先序序列中确定左、右子树的先序序列;最后由左子树的先序序列与中序序列建立左子树,由右子树的先序序列与中序序列建立右子树。文档收集自网络,仅用于个人学习显然,这是一个递归过程。假设先序序列放在数组pre[0..n-1]中,中序序列放在数组mid[0..n-1]中,n是二叉树中元素的个数,其算法如下:文档收集自网络,仅用于个人学习intFind(ElemType*P,intL2,intH2,ElemTypex){//在数组P的区间L2..H2内确定x的位置i=L2;while(P[i]!=x)i++;returni;}//FindvoidCreate(BiTree&T,intL1,intH1,intL2,intH2)文档收集自网络,仅用于个人学习{//已知先序序列pre[L1..H1],//中序序列mid[L2..H2]构建二叉链表if(L2>H2)T=NULL;//建空树else{T=(BiTree)malloc(sizeof(BiTNode));//创建根结点TT->data=pre[L1];//给根数据域赋值k=Find(mid,L2,H2,pre[L1]);//找根在中序序列的位置Create(T->Lchild,L1+1,k+L1-L2,L2,k-1);//创建左子树Create(T->Rchild,k+L1-L2+1,H1,k+1,H2);//创建右子树}}//Create3利用扩展完全二叉树的顺序存储约定对二叉树上的结点从根结点起,自上而下,自左而右进行连续编号,根结点的编号为1。深度为k的,有n个结点的二叉树,当且仅当其每个结点的编号都与深度为k的满二叉树中编号为1至n中的结点