精华内容
下载资源
问答
  • 建立线索二叉链表结构,实现二叉树中序线索化中序线索二叉树的遍历算法。 #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -1 typedef int Status; typedef char ElemType; typedef enum ...

    建立线索二叉链表结构,实现二叉树的中序线索化及中序线索二叉树的遍历算法。

    #include<stdlib.h>
    #include<stdio.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    typedef  int Status;
    typedef  char ElemType;
    typedef enum PointerTag {Link, Thread};//Link=0:指针;Thread=1:线索
    //带线索的二叉树链表结构
    typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,*rchild;   //左右指针
        PointerTag   LTag, RTag;               //左右标志
    }BiTNode,*BiTree;
    
    
    //打印元素
    Status PrintElement(BiTree T);
    //1-创建二叉树
    //按先序次序输入二叉树中结点的值(一个字符),空格表示空树
    Status CreateBiTree(BiTree &T);
    //2中序遍历二叉树,并将其中序线索化
    Status InOrderThreading_Head(BiTree &Thrt, BiTree T);
    //3线索化二叉树
    void InThreading(BiTree p,BiTree &pre);
    //4中序遍历二叉线索树(非递归)
    Status InOrderTraverse_Thr(BiTree T);
    
    
    //打印元素
    Status PrintElement(ElemType e)
    {
    printf("%c",e);
    return OK;
    }
    
    
    //1-创建二叉树
    // 按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
    Status CreateBiTree(BiTree &T)
    {  
      ElemType ch;
      ch=getchar();
      if (ch==' ') T = NULL;
      else 
      {  
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))  exit(OVERFLOW);
    T->data = ch;              // 生成根结点
    T->LTag = Link;
    T->RTag = Link;
        CreateBiTree(T->lchild);      // 构造左子树
        CreateBiTree(T->rchild);      // 构造右子树
      }
      return OK;
    } // CreateBiTree
    
    
    //2中序遍历二叉树,并将其中序线索化
    Status InOrderThreading_Head(BiTree &Thrt, BiTree T) 
    {  
    BiTree pre;
       if (!(Thrt = (BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
            Thrt->LTag = Link;  Thrt->RTag =Thread;  // 建头结点
            Thrt->rchild = Thrt;              // 右指针回指
           if (!T) Thrt->lchild = Thrt;      // 若二叉树空,则左指针回指
          else {
          Thrt->lchild = T;    pre = Thrt;
          InThreading(T,pre);  // 算法6.7
          pre->rchild = Thrt;  pre->RTag = Thread; // 最后一个结点线索化
          Thrt->rchild = pre;  
       }
       return OK;
    } // InOrderThreading
    
    
    
    
    //3线索化二叉树
    //线索二叉树
    void InThreading(BiTree p, BiTree &pre)
    {
    
    if(p){
    InThreading(p->lchild, pre);
    if(!p->lchild){p->LTag = Thread;p->lchild = pre;}
    if(!pre->rchild){pre->RTag = Thread;pre->rchild = p;}
    pre = p;
    InThreading(p->rchild, pre);
    }
    }
    
    
    
    
    //4中序遍历二叉线索树(非递归)
    Status InOrderTraverse_Thr(BiTree T)
    {
    BiTree p = T->lchild;
    while(p != T)
    {
    while(p->LTag == Link)
    p = p->lchild; 
       PrintElement(p->data);
    while(p->RTag  == Thread && p->rchild!= T){
    p = p->rchild;
    PrintElement(p->data);
    }
    p = p->rchild;
    }
    return OK;
    }
    
    
    void main()
    {
    BiTree T,Thrt;
    printf("按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树:\n");
        CreateBiTree(T);
        InOrderThreading_Head(Thrt,T);
        printf("\n中序线索遍历二叉树:");
        InOrderTraverse_Thr(Thrt);
    printf("\n");
    }




    展开全文
  • #include"stdio.h" #include"stdlib.h" typedef struct TBTNode { ...//ltag == 0表示存在左孩子 ,ltag == 1表示存在前驱线索 struct TBTNode *lchild; struct TBTNode *rchild; } TBTNode; ...


    #include"stdio.h"
    #include"stdlib.h"
    typedef struct TBTNode {
        int data;
        int ltag,rtag;//ltag == 0表示存在左孩子 ,ltag == 1表示存在前驱线索
        struct TBTNode *lchild;
        struct TBTNode *rchild;
    } TBTNode;

    //先序遍历建立二叉树
    void createBTree(TBTNode* &bt) {
        int a;
        scanf("%d",&a);
        if(a == -1) ;
        else {
            bt=(TBTNode*)malloc(sizeof(TBTNode));
            bt->data = a;
            bt->ltag= 0;
            bt->rtag = 0; //结点是否有线索?1:有,0:没有。建立线索二叉树时,默认0
            bt->lchild = NULL;
            bt->rchild = NULL;
            createBTree(bt->lchild);
            createBTree(bt->rchild);
        }
    }

    //先序遍历输出二叉树
    void preorder(TBTNode *bt) {
        if(bt!= NULL) {
            printf("%d ",bt->data);
            preorder(bt->lchild);
            preorder(bt->rchild);
        }
    }

    //中序线索化二叉树,使之成为中序线索二叉树
    void inorderCreateTBTree(TBTNode *&p,TBTNode* &pre) {
        if(p != NULL) {
            inorderCreateTBTree(p->lchild,pre);
            if(p->lchild == NULL) { //建立当前结点的前驱线索
                p->ltag = 1;
                p->lchild = pre;
            }
            if(pre!= NULL &&pre->rchild == NULL) { //建立前驱结点的后继线索;pre != NULL必须放在前面, 否则,刚开始pre==NULL,后面的pre->rchild 会报错
                pre->rtag = 1;
                pre->rchild = p;
            }
            pre = p; //前驱结点记录当前结点
            inorderCreateTBTree(p->rchild,pre);
        }
    }

    //中序线索二叉树一旦建立完成,只能根据 ltag或者rtag 来区分叶子节点,非叶子节点,左孩子以及右孩子。
    //比如,未线索化二叉树的叶子节点其左右孩子都指向NULL,建立中序线索二叉树后,叶子节点 的左孩子可以指向前驱,右孩子可以指向后继。
    //查找第一个结点,即根结点的最左下结点
    TBTNode *first(TBTNode *p) {
        if(p!=NULL) {
            while(p->ltag == 0)
                p = p->lchild;
        }
        return p;

    }
    //查找最后一个结点,即根结点的最右下结点
    TBTNode *last(TBTNode *p) {
        if(p!= NULL) {
            while(p->rtag == 0)
                p = p->rchild;
        }
        return p;
    }
    //查找当前结点的后继结点,即其右孩子的最左下结点
    TBTNode *next(TBTNode *p) {
        if(p!= NULL) {
            if(p->rtag == 0)
                return first(p->rchild);
        }
        return p->rchild;
    }
    //查找当前结点的前驱结点,即其左孩子的最右下结点
    TBTNode *prefind(TBTNode *p) {
        if(p!= NULL) {
            if(p->ltag == 0)
                return last(p->lchild);
        }
        return p->lchild;
    }
    //中序遍历中序线索二叉树
    void inorder(TBTNode* root) {
        for(TBTNode* p=first(root); p!=NULL; p=next(p)) {
            printf("%d ",p->data);
        }
    }

    //删除中序线索二叉树的一个结点 -----start
    //第一步:找到要删除结点p,若p存在,执行第二步,否则,算法结束
    TBTNode* findTBTnode(TBTNode *root,int e) {
        for(TBTNode* p=first(root); p!=NULL; p=next(p)) {
            if(p->data == e)
                return p;
        }
    }
    //第二步:情况1.若当前p为叶子结点,(归根结底,删除操作只在叶子结点上进行)要根据“五种不同的叶子结点情况(写在末尾)”删除p结点,算法结束;
    //情况2.若p有左孩子无右孩子,那么找到其前驱结点pre,把pre的结点值赋值到p上,对pre结点进行判断删除,即令p = pre再执行第二步;
    //情况3.若p有右孩子无左孩子,那么找到其后继结点n,把n的结点值赋值到p上,对n结点进行判断删除,即令p = n再执行第二步;
    //情况4.若p有左右孩子,那么除了这句话开头的条件发生了变化,执行步骤可以按情况2或者情况3进行。这里选择情况三,即找到p的后继结点n,把n的结点值赋值到p上,对n结点进行判断删除,即令p = n再执行第二步。
    void deleteTBTNode(TBTNode *&bt,TBTNode *&p) { //因为要对线索二叉树进行改变,这里使用引用型指针变量
        if(p!= NULL) {
            TBTNode* pre,*n;
            pre = prefind(p);
            n = next(p);
            if(p->ltag == 1 && p->rtag == 1) { //当前结点是叶子结点
                if(p == first(bt) && n != NULL) { //情况1:无前驱结点有后继结点  //指针变量的值表示地址
                    n->ltag = p->ltag;
                    n->lchild = p->lchild;
                } else if(p == last(bt) && pre != NULL) { //情况2:若有前驱结点无后继结点
                    pre->rtag = p->rtag;
                    pre->rchild = p->rchild;
                } else if(n&&pre&& p == pre->rchild) { //情况3:若当前结点的前驱是其双亲结点
                    pre->rtag = p->rtag;
                    pre->rchild = p->rchild;
                } else if(n&&pre&& p == n->lchild) { //情况4:若当前结点的后继是其双亲结点
                    n->ltag = p->ltag;
                    n->lchild = p->lchild;
                }
                if(p == bt) bt = NULL; //情况5:中序线索二叉树只有一个结点,即根节点时
                free(p); //释放指针所指向的内存空间,然后设置指针为NULL
                p = NULL;
            } else if(p->ltag == 0 && p->rtag == 1) { // 当前结点有左孩子无右孩子
                p->data = pre->data;
                deleteTBTNode(bt,pre);
            } else if(p->ltag == 1 && p->rtag == 0) { //当前结点有右孩子无左孩子
                p->data = n->data;
                deleteTBTNode(bt,n);
            } else {  //当前结点既有右孩子又有左孩子
                p->data = n->data;
                deleteTBTNode(bt,n);
            }
        }
    }
    //删除中序线索二叉树的一个结点 -----end


    int main() {
        TBTNode *bt;
        printf("先序遍历建立和打印二叉树\n");
        createBTree(bt);
        preorder(bt);
        printf("\n");

        printf("中序遍历线索化和打印中序线索二叉树\n");
        TBTNode *pre = NULL;
        if(bt!= NULL) {
            //中序线索化二叉树
            inorderCreateTBTree(bt,pre);
            //末尾结点处理
            pre->rtag = 1;
            pre->rchild = NULL;
        }
        inorder(bt);
        printf("\n");

        printf("删除中序线索二叉树的某个结点\n");
        TBTNode *p;
        int a;
        while(bt!= NULL) {
            scanf("%d",&a);
            p = findTBTnode(bt,a);
            deleteTBTNode(bt,p);
            inorder(bt);
            printf("\n");
        }

    //    preorder(bt); 二叉树线索化后只能通过线索遍历
        return 0;
    }

    //输入格式:1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 7 -1 8 -1 -1
    //输出格式:
    //先序遍历建立和打印二叉树
    //1 2 3 4 5 6 7 8
    //中序遍历线索化和打印中序线索二叉树
    //3 2 5 4 6 1 7 8
    //删除中序线索二叉树的某个结点
    //3
    //2 5 4 6 1 7 8
    //2
    //5 4 6 1 7 8
    //5
    //4 6 1 7 8
    //4
    //6 1 7 8
    //6
    //1 7 8
    //1
    //7 8
    //7
    //8
    //8 

    //删除中序线索二叉树的一个结点,类似于删除二叉排序树的一个结点。
    //二者在删除过程中有两处不同。第一,对于中序线索二叉树,在查找元素算法中,只需返回指向要被删除元素的指针;在删除结点算法中,可以根据线索快速找到当前要被删除结点的前驱结点和后继结点。
    //对于二叉排序树,在查找元素算法中,返回指向被删除元素的前驱结点的指针和被删除元素的指针,在删除结点算法中,只需要找到当前要被删除结点的前驱结点即可

    //二,在中序线索二叉树中,删除叶子结点时,对线索信息的保留比较繁琐,要考虑五种情况(记住,删除的前提是当前结点为叶子结点)
    //情况1,无前驱结点(就是前驱结点是NULL)有后继结点;
    //情况2,有前驱结点无后继结点(就是后继结点是NULL),
    //情况3,无前后驱结点(就是中序线索二叉树的根结点,前后驱结点都为NULL),
    //情况4,有前后驱结点(又分为两种情况,1.当前结点的后继的左孩子是当前结点,2.当前结点的前驱的右孩子是当前结点)
    //若删除的是非叶子结点,要分三种情况讨论,情况1,有左子树无右子树,情况2,有右子树无左子树,情况三,有左右子树。

    //总的来说,中序线索二叉树是通过递归的方式判断并删除结点,删除操作在叶子结点上进行,而二叉排序树删除操作可以在叶子结点上或者双亲结点上进行。

    展开全文
  • //中序线索二叉树算法 #include &lt;stdio.h&gt; #include &lt;malloc.h&gt; #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; int ltag,rtag; //增加的线索...
    //中序线索二叉树的算法
    #include <stdio.h>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    typedef struct node 
    {
    	ElemType data;
    	int ltag,rtag;      //增加的线索标记
    	struct node *lchild;
    	struct node *rchild;
    } TBTNode;
    void CreateTBTree(TBTNode * &b,char *str)
    {
    	TBTNode *St[MaxSize],*p=NULL;
    	int top=-1,k,j=0;  
    	char ch;
    	b=NULL;				//建立的二叉树初始时为空
    	ch=str[j];
    	while (ch!='\0')	//str未扫描完时循环
    	{
       	   	switch(ch) 
    		{
    		case '(':top++;St[top]=p;k=1; break;		//为左节点
    		case ')':top--;break;
    		case ',':k=2; break;                      	//为右节点
    		default:p=(TBTNode *)malloc(sizeof(TBTNode));
    				p->data=ch;p->lchild=p->rchild=NULL;
    		        if (b==NULL)					//*p为二叉树的根节点
    					b=p;
    				else  							//已建立二叉树根节点
    				{	
    					switch(k) 
    					{
    					case 1:St[top]->lchild=p;break;
    					case 2:St[top]->rchild=p;break;
    					}
    				}
    		}
    		j++;
    		ch=str[j];
    	}
    }
    void DispTBTree(TBTNode *b) 
    {
    	if (b!=NULL)
    	{
    		printf("%c",b->data);
    		if (b->lchild!=NULL || b->rchild!=NULL)
    		{
    			printf("(");
    			DispTBTree(b->lchild);
    			if (b->rchild!=NULL) printf(",");
    			DispTBTree(b->rchild);
    			printf(")");
    		}
    	}
    }
    TBTNode *pre;						//全局变量
    void Thread(TBTNode *&p)			//线索化二叉树 
    {
    	if (p!=NULL)	
    	{	
    		Thread(p->lchild);    		//左子树线索化
    		if (p->lchild==NULL)		//前驱线索
    		{
    			p->lchild=pre;        	//建立当前节点的前驱线索
    			p->ltag=1;
    		}
    		else p->ltag=0;
    		if (pre->rchild==NULL)		//后继线索
    		{	
    			pre->rchild=p;     		//建立前驱节点的后继线索
    		   	pre->rtag=1;
    		} 
    		else pre->rtag=0;
    	    pre=p;						//起到推进的作用 
    	   	Thread(p->rchild);  		//右子树线索化
    	}
    }
    TBTNode *CreateThread(TBTNode *b)     //中序线索化二叉树
    {
    	TBTNode *root;
    	root=(TBTNode *)malloc(sizeof(TBTNode));  //创建根节点
    	root->ltag=0;root->rtag=1;
    	root->rchild=b;
    	if (b==NULL)                //空二叉树
    		root->lchild=root;
    	else
    	{  	
    		root->lchild=b;
    		pre=root;             	//pre是*p的前驱节点,供加线索用
    		Thread(b);   			//中序遍历线索化二叉树
    		pre->rchild=root;    	//最后处理,加入指向根节点的线索
    		pre->rtag=1;
    		root->rchild=pre;    	//根节点右线索化
    	}
        return root;
    }
    void DestroyTBTree1(TBTNode *&b)	//销毁
    {	if (b->ltag==0)					//节点b有左孩子,释放左子树
    		DestroyTBTree1(b->lchild);
    	if (b->rtag==0)					//节点b有右孩子,释放右子树
    		DestroyTBTree1(b->rchild);
    	free(b);
    }
    void DestroyTBTree(TBTNode *&tb)	//销毁一棵带头结点的中序线索树tb
    {
    	DestroyTBTree1(tb->lchild);		//释放以tb->lchild为根节点的树
    	free(tb);						//释放头节点
    }
    
    void ThInOrder(TBTNode *tb)			//遍历中序 线索化二叉树 
    {
    	TBTNode *p=tb->lchild;		//指向根节点
    	while (p!=tb)		
    	{
    		while (p->ltag==0) p=p->lchild;
    		printf("%c ",p->data);
    		while (p->rtag==1 && p->rchild!=tb)
    		{
    			p=p->rchild;
    			printf("%c ",p->data);
    		}
    		p=p->rchild;
    	}
    }
    int main()
    {
    	TBTNode *b,*tb;
    	CreateTBTree(b,"A(B(D(,G)),C(E,F))");
    	printf(" 二叉树:");DispTBTree(b);printf("\n");
    	tb=CreateThread(b);
    	printf(" 线索中序序列:");ThInOrder(tb);printf("\n");
    	DestroyTBTree(tb);
    	return 1;
    }
    

    展开全文
  • 二叉树中序线索化算法

    千次阅读 2013-05-14 19:23:00
    // 二叉树线索化的头文件:BinaryThreadTree.h #ifndef B_T_T_H #define B_T_T_H #include // // 返回OK表示正常返回 #define OK 1 // // 返回ERROR,表示异常返回 #define ERROR 0 // // 返回OVERFLOW,表示...
    //
    // 二叉树线索化的头文件:BinaryThreadTree.h
    
    #ifndef B_T_T_H
    #define B_T_T_H
    
    #include <stdio.h>
    
    //
    // 返回OK表示正常返回
    #define OK 1
    
    //
    // 返回ERROR,表示异常返回
    #define ERROR 0
    
    //
    // 返回OVERFLOW,表示内存溢出
    #define OVERFLOW -1
    
    //
    // 线索结构体
    typedef enum 
    {
    	Link = 0,  // 指针
    	Thread = 1 // 线索
    }PointerTag;
    
    //
    // 树结点的数据的类型
    typedef char ElemType; 
    
    //
    // 返回值类型
    typedef int Status;
    
    //
    // 线索二叉树结构体
    typedef struct tagBinaryThreadTree
    {
    	ElemType data;
    	struct tagBinaryThreadTree *lchild; // 左孩子指针
    	struct tagBinaryThreadTree *rchild; // 右孩子指针
    	PointerTag leftTag;   // 左标志          
    	PointerTag rightTag;  // 右标志
    
    }BinThrTree, *LinkBinThrTree;
    
    //
    // 按先序顺序输入数据,以建立线索二叉树
    // 输入的#表示子树为空
    Status CreateBinaryThreadTree(LinkBinThrTree *pBinThrTree);
    
    //
    // 中序遍历线索化二叉树
    Status InOrderTraverse(LinkBinThrTree pBinThrTree);
    
    //
    // 线索化
    void InThreading(LinkBinThrTree p);
    
    //
    // 中序线索化二叉树
    Status InOrderThreading(LinkBinThrTree *threadTree, LinkBinThrTree tree);
    
    #endif
    //
    // 线索二叉线的实现文件:BinaryThreadTree.c
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #include "BinaryThreadTree.h"
    
    LinkBinThrTree pre = NULL; //定义pre为函数InThreading的外部变量,使其指向最后一个节点
    
    //
    // 按先序顺序输入数据,以建立线索二叉树
    // 输入的#表示子树为空
    Status CreateBinaryThreadTree(BinThrTree **pBinThrTree)
    {
    	char ch;
    
    	scanf ("%c", &ch);
    
    	if (ch == '#')
    	{
    		*pBinThrTree = NULL;
    	}
    	else
    	{
    		*pBinThrTree = (LinkBinThrTree)malloc(sizeof(BinThrTree));
    
    		if (!(*pBinThrTree))
    		{
    			exit(OVERFLOW);
    		}
    
    		(*pBinThrTree)->data = ch;
    		(*pBinThrTree)->leftTag = Link;
    		(*pBinThrTree)->rightTag = Link;
    
    		CreateBinaryThreadTree(&(*pBinThrTree)->lchild);
            CreateBinaryThreadTree(&(*pBinThrTree)->rchild);
    	}
    
    	return OK;
    }
    
    //
    // 中序遍历线索化二叉树
    Status InOrderTraverse(LinkBinThrTree pBinThrTree)
    {
    	LinkBinThrTree p = NULL;
    
    	p = pBinThrTree->lchild;
    
    	while (p != pBinThrTree)
    	{
    		while (p->leftTag == Link)
    		{
    			p = p->lchild; // 沿着根向左走到尽头
    		}
    
    		printf("%c", p->data); // 输出
    
    		// 沿着线索向右走到尽头
    		while (p->rightTag == Thread && p->rchild != pBinThrTree)
    		{
    			p = p->rchild;
                printf("%c", p->data); // 输出
    		}
    
    		p = p->rchild;
    	}
    
    	return OK;
    }
    
    //
    // 线索化
    void InThreading(LinkBinThrTree p)
    {
    	if (p)
    	{
    		InThreading(p->lchild);
    
    		if (!p->lchild)
    		{
    			p->leftTag = Thread;
    			p->lchild = pre;
    		}
    
    		if (!pre->rchild)
    		{
    			pre->rightTag = Thread;
    			pre->rchild = p;
    		}
    
    		pre = p;
    
    		InThreading(p->rchild);
    	}
    }
    
    //
    // 中序线索化二叉树
    Status InOrderThreading(LinkBinThrTree *threadTree, LinkBinThrTree tree)
    {
    	if (!((*threadTree) = (LinkBinThrTree)malloc(sizeof(BinThrTree))))
    	{
    		exit(OVERFLOW);
    	}
    
    	(*threadTree)->leftTag = Link;
    	(*threadTree)->rightTag = Thread;
    	(*threadTree)->rchild = (*threadTree);
    
    	if (!tree) // 若树空,左指针回指
    	{
    		(*threadTree)->lchild = (*threadTree);
    	}
    	else
    	{
    		(*threadTree)->lchild = tree;
    		pre = (*threadTree);
    
    		InThreading(tree);
    
    		pre->rchild = tree;
    		pre->rightTag = Thread;
    		tree->rchild = pre;
    	}
        
    	return OK;
    }
    

    //
    // 测试线索二叉树的算法的使用
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #include "BinaryThreadTree.h"
    
    int main()
    {
    	BinThrTree *tree = NULL, *head = NULL;
    
    
    	freopen("test.txt", "r", stdin);
    
    	if (CreateBinaryThreadTree(&tree))
    	{
    		printf("二叉树创建成功!\n");
    	}
    
    	if (InOrderThreading(&head, tree))
    	{
    		printf("\n中序线索化二叉树完毕!\n");
    	}
    
    	printf("\n中序遍历线索化二叉树:\n");
    	InOrderTraverse(tree);
    
    	fclose(stdin);
    	putchar(10);
    
    	return 0;
    }


    展开全文
  • 中序线索化的C程序 中序线索化的C程序 中序线索化的C程序 中序线索化的C程序 中序线索化的C程序
  • 为什么使用的是顺序栈来保存遍历过程中需要回溯的结点指针到最后面要free(st)free函数不是只有动态分配内存才可以用?,使用顺序栈并没有动态分配内存的呀[img=...[/img]
  • 文章目录线索二叉树的结构及数据类型定义根据输入结点初始化二叉树中序遍历二叉树线索化遍历中序线索二叉树项目完整代码运行实现截图 线索二叉树的结构及数据类型定义 //定义数据类型 typedef char ElemType; //...
  • 二叉树线索化算法

    2021-06-05 14:55:23
    二叉树线索化 简述 为什么需要线索二叉树? 对于普通的二叉树来说,如果随便给出二叉树中的一个结点,让你从这个结点遍历整个二叉树,这是做不到的(其实对于普通的二叉树来说要做到找出一个结点的前驱需要创建两个...
  • #include#define OK 1#define ERROR 0#define OVERFLOW -1typedef int Status;typedef char ElemType;typedef enum PointerTag {Link, ...Thread=1:线索//带线索二叉树链表结构typedef struct BiTNode{ElemT...
  • /* ...  * All rights reserved。  * 文件名称 :1.cpp  * 作 者 :杨俊杰 ... * 完成日期 :2016年 11月10日 ... * 问题描述 :中序线索化二叉树算法的验证  * 输出描述 :  */
  • /* ... All rights reserved. 文件名称:项目.cpp 作 者:纪冬雪 完成日期:2015年11月20日 ...问题描述: 运行并重复测试教学内容中涉及的算法。... 可以从更多角度体会算法,以达到逐渐掌握算法的程度。
  • /* ...03.*All rights reserved. 04.*文件名称:cengcibianli.cpp 05.*作者:朱希康 06.*完成日期:2015年11月20日 07.*版本号:vc++6.0 ...09.*问题描述:线索二叉树 10.*输入描述:无 11.*程序输出:二叉树 1
  • 首先, 我们需要找到二叉树T中第一个被中序遍历的结点: 根据中序遍历的算法逻辑, (※)也就是找到二叉树T的最左下结点. 下面的算法可定位到二叉树的最左下结点. BiTreeNode* FirstNode(BiTreeNode* T)//在以T为根...
  • 中序线索化二叉树的非递归算法:设计技巧:依某种顺序遍历二叉树,对每个结点p,判断其左指针是否为空,以及其前驱结点pre的右指针是否为空。
  • void InThread(TBTNode *p, TBTNode *&pre) { if (p != NULL) { InThread(p->lchild, pre); if (p->lchild == NULL) { p->lchild = pre;...//中序遍历的最后一个结点没有右孩子 } }  
  • /* ...All rights reserved. 文件名称:项目1-3.cbp 作 者:孙立立 完成日期:2015年12月7日 ...问题描述:实现中序线索化二叉树算法验证,并测试数据。 输入描述:无 程序输出:测试数据 */ 代码: #include #incl
  • 中序线索二叉树(建立二叉树线索化,输出二叉树
  • 二叉树中序遍历线索化 中序遍历有一个特点,只要不是叶子节点,遍历的时候左孩子一定是当前节点的上一个访问节点;右孩子一定是当前节点的下一个访问节点。 如果把叶子节点的左右孩子都利用起来,把空的左孩子做成...
  • /* ... * All rights reserved. * 文件名称: main.cpp * 作者:唐子健* 完成日期:2015年11月16日 ...* 问题描述: 中序线索化二叉树算法验证 * 输入描述: 无 * 程序输出: 见运行结果 */ #include #i
  • 中序线索二叉树就是在普通的二叉树上加上了中序线索。 为了节省空间,只增加两个判定位。flagLeft 和 flagRight,当为0时,表示存放的是子女节点。为1时,表示存放的线索。 其中,左节点存放中序前继,右节点存放...
  • TBTNode *CreaThread(TBTNode *b) //中序线索化二叉树 { TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode)); //创建根结点 root->ltag=0; root->rtag=1; root->rchild=b; if (b==NULL) //空...
  • *问题描述:中序线索化二叉树算法验证 *输入描述:无 *程序输出:若干数据 */   #include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ...
  • 问题及代码: /*2015,烟台大学计算机与控制... *问题描述:中序线索化二叉树算法验证 */ 代码: #include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data
  • 中序线索二叉树算法

    2010-03-31 13:56:00
    参考:http://www.cnblogs.com/yuchen198112/archive/2007/01/02/610058.html 理解下面两句话 (1)若上次访问到的结点的右指针为空,则将当前访问到的结点序号填入,并置右标志为1。(2)若当前访问到的结点的左...
  • 中序遍历线索二叉树

    2018-11-18 19:35:41
    中序遍历线索二叉树的实现与操作二叉线索树的结构定义创建一棵二叉树创建一棵二叉树及二叉树基本操作中序遍历二叉树线索化的递归算法通过中序遍历建立中序线索二叉树中序遍历主函数测试 二叉线索树的结构定义 ...

空空如也

空空如也

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

中序二叉树线索化算法