(4) Insert(bt,X, parent)将数据域信息为x的结点插 到二叉树b中作为结点 parent的右孩子结点。如果结点 parent)原来有右孩子结点,则将结点 parent原来的右孩子结点 作为结点x的右孩子结点 (5) DeleteL(bt, parent)在二叉树b中删除结点 parentE 左子树 (6) DeleteR(bt, parent)在二叉树b中删除结点 parente 右子树。 (7) Search(bt,X)在二叉树bt中查找数据元素ⅹ。 (8) Traverse(bt)按某种方式遍历二叉树bt的全部结点。 2021年1月21日 数据结构讲义 26
2021年1月21日 数据结构讲义 26 （4）InsertR（bt，x，parent）将数据域信息为x的结点插 入到二叉树bt中作为结点parent的右孩子结点。如果结点 parent原来有右孩子结点，则将结点parent原来的右孩子结点 作为结点x的右孩子结点。 （5）DeleteL（bt，parent）在二叉树bt中删除结点parent的 左子树。 （6）DeleteR（bt，parent）在二叉树bt中删除结点parent的 右子树。 （7）Search（bt，x）在二叉树bt中查找数据元素x。 （8）Traverse（bt）按某种方式遍历二叉树bt的全部结点
算法的实现依赖于具体的存储结构,当二叉树采用 不同的存储结构时,上述各种操作的实现算法是不 同的。 下面讨论基于二叉链表存储结构的上述操作的实现 算法。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 27 • 算法的实现依赖于具体的存储结构，当二叉树采用 不同的存储结构时，上述各种操作的实现算法是不 同的。 • 下面讨论基于二叉链表存储结构的上述操作的实现 算法
(1) Initiate(bt)初始建立二叉树bt,并使bt指向头结点 在二叉树根结点前建立头结点,就如同在单链表前建立的 头结点,可以方便后边的一些操作实现。 int Initiate(BiTree *bt) *初始化建立二叉树*bt的头结点* f if(bt= BiTNode * )malloc(sizeof( BiTNode==NULL return 0 *bt->lchild=NULL bt->rchild=NUL return 1 2021年1月21日 数据结构讲义 28
2021年1月21日 数据结构讲义 28 （1）Initiate（bt）初始建立二叉树bt，并使bt指向头结点。 在二叉树根结点前建立头结点，就如同在单链表前建立的 头结点，可以方便后边的一些操作实现。 int Initiate (BiTree *bt) /*初始化建立二叉树*bt的头结点*/ { if((*bt=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return 0; *bt->lchild=NULL; *bt->rchild=NULL; return 1; }
(2) Create(x,lbt,rbt)建立一棵以x为根结点的数据 域信息,以二叉树bt和rbt为左右子树的二叉树。建立成 功时返回所建二叉树结点的指针;建立失败时返回空指 针 BiTree Create (elemtype x, BiTree Ibt, BiTree rbt) *生成一棵以x为根结点的数据域值以Ibt和rbt为左右子树的二叉树* t BiTree p if(p= BiTNode s)malloc(sizeof(BiTNode)=NULL return NULL. p->data=x p->lchild=lbt, p->rchild=rbt return p, 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 29 （2）Create（x，lbt，rbt）建立一棵以x为根结点的数据 域信息，以二叉树lbt和rbt为左右子树的二叉树。建立成 功时返回所建二叉树结点的指针；建立失败时返回空指 针。 BiTree Create（elemtype x，BiTree lbt，BiTree rbt） /*生成一棵以x为根结点的数据域值以lbt和rbt为左右子树的二叉树*/ { BiTree p; if ((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=lbt; p->rchild=rbt; return p; }
(3) InsertL(bt,x, parent) BiTree InsertL(BiTree bt, elemtype x, BiTree parent /在二叉树bt的结点 parent的左子树插入结点数据元素x*/ i BiTree p if (parent==NULL) printf(n插入出错”); return NUll if ((p= BinOde )malloc(sizeof( BiTNodeD)==NULL return null p->data=x; p->lchild=NULL, p->rchild=NULL if ( parent->Ichild--nULL parent->lchild=p else p->lchild=parent->lchild parent->lchild=;) return bt 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 30 （3）InsertL（bt，x，parent） BiTree InsertL（BiTree bt，elemtype x，BiTree parent） /*在二叉树bt的结点parent的左子树插入结点数据元素x*/ { BiTree p; if (parent==NULL) { printf(“\n插入出错”)； return NULL; } if ((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if (parent->lchild==NULL) parent->lchild=p; else { p->lchild=parent->lchild; parent->lchild=p; } return bt; }