线索二叉树 订阅
在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 [1] 展开全文
在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 [1]
信息
外文名
Threaded BinaryTree
领    域
计算机科学
中文名
线索二叉树
线索二叉树概念
对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。注意:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。
收起全文
精华内容
下载资源
问答
  • 线索二叉树

    2015-11-18 14:32:00
    线索二叉树
  • 在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 文章目录一、c语言实现先序线索、中序线索、...
    
    

    在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。


    一、c语言实现先序线索、中序线索、后续线索二叉树

    代码如下(示例):

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct BiTNode {
    	int data;
    	BiTNode* lchild, * rchild;
    	int ltag=0, rtag=0;
    }BiTNode,*BiTree;
    
    BiTree pre = NULL;//全局变量
    
    void visit(BiTree P) {
    	if (P->lchild == NULL) {
    		P->lchild = pre;
    		P->ltag=1;
    	}
    	if (pre != NULL && pre->rchild == NULL) {
    		pre->rchild = P;
    		pre->rtag = 1;
    	}
    	if(P!=NULL) printf("%d\n", P->data);
    	if (P == NULL) printf("no rchild");
    	pre = P;
    }
    
    //中序线索二叉树,一边遍历一边线索化
    void MBuild(BiTree P) {
    	if(P!=NULL){
    	MBuild(P->lchild);
    	visit(P);
    	MBuild(P->rchild);
    	}
    }
    
    //中序线索树节点p的前驱节点
    BiTree MPreNode(BiTree p) {
    	if (p->ltag == 1) p = p->lchild;
    	else {
    	if (p->ltag != 1) {
    			p = p->lchild;
    			while (p->rtag != 1 && p->rchild != NULL)//注意p->rtag != 1 && p->rchild != NULL而不是p->rchild != NULL
    				p = p->rchild;
    		}
    	}
    	
    	return p;
    }
    
    //中序线索树节点p的后继节点
    BiTree MSucceedNode(BiTree p) {
    	if (p->rtag == 1) {
    		p = p->rchild; 
    	}
    	else {
    	if (p->rtag ==0) {
    			p = p->rchild;
    			while (p->ltag != 1 && p->lchild != NULL)//注意
    				p = p->lchild;
    		}
    	}
    	return p;
    }
    
    
    //先序线索树,一边遍历一边线索化
    void PBuild(BiTree T) {
    	if (T != NULL) {
    	visit(T);
    		if(T->ltag!=1)	PBuild(T->lchild);
    		PBuild(T->rchild);
    	}
    	
    }
    
    //先序线索树节点p的前驱节点   注意else!!!!!!!!!!!!!
    BiTree PPreNode(BiTree p) {
    	if (p->ltag == 1) p = p->lchild;
    	else {
    		if (p->ltag != 1) {
    			printf("can not by this way!");
    		}
    	}
    	return p;
    }
    
    //先序线索树节点p的后继节点     注意else!!!!!!!!!!!!
    BiTree PSucceedNode(BiTree p)  {
    	if (p->rtag == 1) p = p->rchild;
    	else {
    	if (p->rtag != 1) {
    			if (p->ltag!=1)  p=p->lchild;
    			else
    			if (p->ltag==1) p = p->rchild;
    		}
    	}
    	return p;
    }
    
    
    //后序线索二叉树,一边遍历一边线索化
    void LBuild(BiTree P) {
    	if (P != NULL) {
    		MBuild(P->lchild);
    		MBuild(P->rchild);
    		visit(P);
    	}
    }
    
    //后序线索树节点p的前驱节点
    BiTree LPreNode(BiTree p){
    	if (p->ltag == 1) p = p->lchild;
    	else {
    	if (p->ltag != 1) {
    			if (p->rtag!=1) p = p->rchild;
    			if (p->rtag==1) p = p->lchild;
    		}
    	}
    	return p;
    }
    
    //后序线索树节点p的后继节点
    BiTree LSucceedNode(BiTree p) {
    	if (p->rtag == 1) p = p->rchild;
    	else {
    	if (p->rtag != 1) {
    			printf("can not by this way!");
    		}
    	}
    	return p;
    }
    
    int main() {
    	BiTree a1 = (BiTree)malloc(sizeof(BiTNode));
    	a1->data = { 1 };
    	a1->ltag = 0;
    	a1->rtag = 0;
    	a1->lchild = NULL;
    	a1->rchild = NULL;
    
    	BiTree a2 = (BiTree)malloc(sizeof(BiTNode));
    	a2->data = { 2 };
    	a1->lchild = a2;
    	a2->ltag = 0;
    	a2->rtag = 0;
    	a2->lchild = NULL;
    	a2->rchild = NULL;
    
    	BiTree a3 = (BiTree)malloc(sizeof(BiTNode));
    	a3->data = { 3 };
    	a1->rchild = a3;
    	a3->lchild = NULL;
    	a3->rchild = NULL;
    	a3->ltag = 0;
    	a3->rtag = 0;
    
    	BiTree a5 = (BiTree)malloc(sizeof(BiTNode));
    	a5->data = { 5 };
    	a2->rchild = a5;
    	a5->lchild = NULL;
    	a5->rchild = NULL;
    	a5->ltag = 0;
    	a5->rtag = 0;
    
    	BiTree a6 = (BiTree)malloc(sizeof(BiTNode));
    	a6->data = { 6 };
    	a3->lchild = a6;
    	a6->lchild = NULL;
    	a6->rchild = NULL;
    	a6->ltag = 0;
    	a6->rtag = 0;
    
    	BiTree a7 = (BiTree)malloc(sizeof(BiTNode));
    	a7->data = { 7 };
    	a3->rchild = a7;
    	a7->lchild = NULL;
    	a7->rchild = NULL;
    	a7->ltag = 0;
    	a7->rtag = 0;
    
    //中序的测试
    //	MBuild(a1); 
    //	pre->rchild = NULL;
    //	BiTree n = MPreNode(a3);
    //	BiTree m = MSucceedNode(a2);
    //	printf(" %d\n",n->data);
    
    //先序的测试
    	PBuild(a1);
    	pre->rchild = NULL;
    	printf("%d\n",PPreNode(a3)->data);
    	printf("%d\n",PSucceedNode(a3)->data);
    
    //后序的测试
    //	LBuild(a1);
    //	pre->rchild = NULL;
    //	printf("  %d\n", LPreNode(a5)->data);
    //	printf("  %d\n", LSucceedNode(a6)->data);
    
    }
    

    总结

    关注一下吧!好想有几个粉丝啊

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,957
精华内容 1,982
关键字:

线索二叉树