潞城建设局网站,众鱼深圳网站建设,主色调为绿色的网站,网站开发市场调查线索二叉树结构1.线索二插树的作用2.线索二叉树的定义3.线索二叉树的结构4. 线索二叉树的操作4.1. 建立一棵中序线索二叉树4.2. 在中序线索二叉树上查找任意结点的中序前驱结点4.3. 在中序线索二叉树上查找任意结点的中序后继结点4.4. 在中序线索二叉树上查找任意结点在先序下的…
线索二叉树结构1.线索二插树的作用2.线索二叉树的定义3.线索二叉树的结构4. 线索二叉树的操作4.1. 建立一棵中序线索二叉树4.2. 在中序线索二叉树上查找任意结点的中序前驱结点4.3. 在中序线索二叉树上查找任意结点的中序后继结点4.4. 在中序线索二叉树上查找任意结点在先序下的后继结点4.5. 在中序线索二叉树上查找任意结点在后序下的前驱结点4.6. 在中序线索二叉树上查找值为x的结点4.7. 中序线索二叉树上的插入与删除5. 基于中序线索二叉树的遍历算法1.线索二插树的作用
通过递归算法或者是用栈与队列实现非递归算法都会有额外空间上的开销。利用n个结点有n1个空指针域来存放线索然后利用这个线索来实现不用空额外空间来遍历二叉树。
2.线索二叉树的定义
在某种顺序遍历二叉树的时候存在直接前驱结点和后继结点的信息对于非空指针域指向原本的左右孩子而对于非空指针域来说左孩子指针指向遍历序列的直接前驱结点右孩子指向遍历序列的直接后继结点。 这种指针称为线索加了线索的二叉树称为线索二叉树。
3.线索二叉树的结构
为每个结点增设两格标志域ltag和rtag令 当Itag0表示lchild指向结点的左孩子ltag1表示lchild指向结点的前驱结点。 当rtag0表示rchild指向结点的右孩子rtag1表示rchild指向结点的后继结点。
为了将二叉树的所有空指针域都利用上并且方便判断遍历操作何时结束在存储的时候增设一个头结点该头结点和其他结点类型相同值域不存储值初始化使其左指针域指向二叉树的根结点右指针域指向自己。线索化完成后让头结点的值域指向按某种顺序 遍历下的最后一个结点。而原二叉树在某种遍历顺序下的第一个结点的前驱线索和最后一个结点的后继线索都指向。 【结构体的定义】
//线索二叉树结点的定义
typedef char ElemType;
typedef struct BiThrNode
{ElemType data;int ltag;int rtag;struct BiThrNode* lchild;struct BiThrNode* rchild;
}BiThrNode,*BiThrTree;4. 线索二叉树的操作
4.1. 建立一棵中序线索二叉树
【算法实现】
//建立中序线索二叉树
void InThreading(BiThrTree p, BiThrTree* pre)//递归算法
{if (p){InThreading(p-lchild, pre);//左子树线索化//前驱线索if (!p-lchild){p-ltag 1;p-lchild *pre;}elsep-ltag 0;//后继线索if (!(*pre)-rchild){(*pre)-rtag 1;(*pre)-rchild p;}else(*pre)-rtag 0;*pre p;InThreading(p-rchild, pre);//右子树的线索化}
}
int InOrderThr(BiThrTree* head, BiThrTree T)//带头结点的中序线索二叉树的算法
{//基于中序遍历二叉树T并将中序线索化*head指向头结点//申请头结点的空间BiThrTree pre;if (!(*head (BiThrTree)malloc(sizeof(BiThrNode))))return 0;//建立头结点(*head)-ltag 0;(*head)-rchild *head;//右指针回针if (!T)(*head)-lchild *head;//若二叉树为空则左指针回针else{(*head)-lchild T;pre *head;InThreading(T, pre);//中序遍历进行中序线索化pre-rchild *head; pre-rtag 1;//最后一个结点线索化(*head)-rtag 1;(*head)-rchild pre;}return 1;
}4.2. 在中序线索二叉树上查找任意结点的中序前驱结点
存在两种情况
如果该结点的左标志为1那么其左指针域指向的结点就是它的前驱结点。如果该结点的左标志为0那么说明该结点存在左孩子。由中序序列的定义该左孩子的右子树的最后一个结点就是该结点前驱结点。即沿着其左孩子右指针向下找当某个结点的右标志域为1时它就是该结点的前驱结点。
【算法实现】
//在中序线索二叉树上查找任意结点的中序前驱结点
BiThrTree InPreNode(BiThrTree p)
{//在中序线索二叉树上寻找结点p的中序前驱结点BiThrTree pre p-lchild;if (p-ltag 0)//有左子树找左子树最右下方的结点{while (pre-rtag 0)pre pre-rchild;}return pre;
}4.3. 在中序线索二叉树上查找任意结点的中序后继结点
如果该结点的右标志为1那么其右指针域指向的结点就是它的后继结点。如果该结点的右标志为0那么说明该结点存在右孩子。由中序序列的定义该右孩子的左子树的最后一个结点就是该结点后继结点。即沿着其右孩子左指针向下找当某个结点的左标志域为1时它就是该结点的后继结点。
【算法实现】
//在中序线索二叉树上查找任意结点的中序后继结点
BiThrTree InPostNode(BiThrTree p)
{//在中序线索二叉树上寻找结点p的中序后继结点BiThrTree post p-rchild;if (post-rtag 0)//有右子树找右子树最左下方的结点{while (post-ltag 0)post post-lchild;}return post;
}4.4. 在中序线索二叉树上查找任意结点在先序下的后继结点
1若 * p为分支结点待确定的先序下的后继结点有两种情况 ①当p-ltag0时* p的左孩子为 * p的先序下的后继结点。 ②当p-ltag1且 p-rtag0时* p 的右孩子为 * p先序下的后继结点 2若 * p为叶子结点 如果 * p的后继结点存在则说明 一定是 * p某个祖先的右孩子结点不存在则指向头结点。 【算法实现】
//在中序线索二叉树上查找任意结点在先序下的后继结点
BiThrTree InPrePostNode(BiThrTree head, BiThrTree p)
{//在中序线索二叉树上寻找结点p的先序下的后继结点head为头结点BiThrTree post;if (p-ltag 0)post p-lchild;//*p有左子树else{post p;while (post-rtag 1 post-rchild ! head)post post-rchild;post post-rchild;}return post;
}4.5. 在中序线索二叉树上查找任意结点在后序下的前驱结点
两种情况 ①存在右孩子则右孩子是后序下的前驱结点存在左孩子但是不存在右孩子则左孩子是后序的前驱结点。 ②是叶子结点则它的在后序下的前驱结点是其某个祖先的左孩子或者不存在则是头结点。 【算法实现】
//在中序线索二叉树上查找任意结点在后序结点下的前驱结点
BiThrTree InPostPreNode(BiThrTree head, BiThrTree p)
{//在线索二叉树上寻找结点p的后序下的前驱结点head为头结点BiThrTree pre;if (p-rtag 0)pre p-rchild;else{pre p;while (pre-ltag 1 pre-lchild ! head)pre pre-lchild;pre pre-lchild;}return pre;
}4.6. 在中序线索二叉树上查找值为x的结点
先找打中序序列中的第一个结点在依次往后遍历整个中序线索二叉树。 【算法实现】
//在中序线索二叉树上查找值为x的结点
BiThrTree Search(BiThrTree head, ElemType x)
{//以head的头结点的中序线索二叉树中查找值为x的结点BiThrTree p head-lchild;while (p-ltag 0 p ! head)p p-lchild;//找到中序序列的第一个结点while (p ! head p-data ! x)p InPostNode(p);if (p head){printf(Not Found the data!\n);return 0;}else return p;
}4.7. 中序线索二叉树上的插入与删除
插入和删除一个结点都需要重新进行线索化。在这里讨论插入一个结点使其成为右孩子。 【算法实现】
//在中序线索二叉树上的插入与删除
void InsertThrRight(BiThrTree s, BiThrTree p)
{//在中序线索二叉树中插入结点p使其称为结点s的右孩子BiThrTree w;//将s变为p的中序前驱p-rchild s-rchild;p-rtag s-rtag;p-lchild s;p-ltag 1;//p变成s的右孩子s-rchild p;s-rtag 0;//当前s原来的右子树不为空找到s的后继w将w变成p的后继并将p变成w的前驱if(p-rtag0){w InPostNode(p);w-lchild p;}
}5. 基于中序线索二叉树的遍历算法
//基于中序线索二叉树的遍历算法
void ThInOrder(BiThrTree head)
{//在中序线索二叉树上进行中序遍历BiThrTree p head-lchild;while (p-ltag 0)p p-lchild;//找第一个结点while (p ! head)//依序找后继结点{printf(%c , p-data);p InPostNode(p);}
}
void ThpreInOrder(BiThrTree head)
{//在中序线索二叉树上进行前序遍历BiThrTree p head-lchild;while (p ! head)//依序找打后继结点{printf(%c , p-data);p InPrePostNode(head, p);}
}
void ThpostInOrder(BiThrTree head)
{//在中序线索二叉树上进行后序遍历的逆序BiThrTree p head-lchild;while (p ! head)//依序找到前驱结点{printf(%c , p-data);p InPostPreNode(head, p);}
}
