bitree

前中序或中后序求二叉树

在此拿前中序举例，前序由根+左子树+右子树的形式构成，中序由左子树+根+右子树构成 。在中序找到从前序得知的根节点位置，根据中序分成左右子树，用递归的方法求得二叉树。代码如下：

typedef char TElemType;
//二叉树结构
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void CrtBT(BiTree &T,char pre[],char ino[],int ps,int is,int n){
	// 已知pre[ps..ps+n-1]为二叉树的先序序列， 
    // ino[is..is+n-1]为二叉树的中序序列
    if(n==0) T=NULL;
    else{
	    k=Search(ino, pre[ps]); // 在中序序列查找根节点位置 
	    if (k==-1)  T=NULL;
        else{   
		    T = new BiTNode; 
			T->data = pre[ps];
			if (k==is)  T->Lchild = NULL;
			else  CrtBT(T->Lchild, pre[], ino[],ps+1, is, k-is);
			if (k==is+n-1) T->Rchild = NULL;
			else  CrtBT(T->Rchild, pre[], ino[],ps+1+(k-is),k+1,n-(k-is)-1);
        }
    } 
}

线索二叉树的实现和遍历

这个算法我觉得表面还是比较好理解的，如果想搞清楚每一层递归和外边层的关系就有点混乱，比如这个pre，外边层的pre变量是前一次执行完一次递归后的那个pre，而且pre如果是NULL时不能进入判断会访问非法，要加一个pre是否为空的判断.还有一个大，最开始创建树的时候没有对两个标志变量赋初值。导致出现死循环和输出少的情况，最后实现了这个算法，下面是代码:(输入前序输出中序)

#include<iostream>
using namespace std;

typedef char TElemType;
typedef enum {Link,Thread} PointerTag;//Link:表示指向孩子指针,Thread:表示指向线索指针
typedef struct BiThrNode{	//线索二叉树节点 
	TElemType data;
	struct BiThrNode *lchild,*rchild;
	PointerTag LTag;
	PointerTag RTag;
}BiThrNode,*BiThrTree;

void CreateBiTree(BiThrTree *T){
	TElemType ch;
	cin>>ch;
	if(ch=='#') *T=NULL;
	else{
		*T=new BiThrNode;
		(*T)->data=ch;
		(*T)->LTag=Link;
		(*T)->RTag=Link;
		CreateBiTree(&((*T)->lchild));
		CreateBiTree(&((*T)->rchild));
	}
}

BiThrTree pre=NULL; 
void InThreading(BiThrTree T){
	if(T){
		InThreading(T->lchild);
		if(!T->lchild){
			T->LTag=Thread;
			T->lchild=pre;
		}
		if(pre&&!pre->rchild){
			pre->RTag=Thread;
			pre->rchild=T;
		}
		pre=T;
		InThreading(T->rchild);
	}	
}

void InOrderTraverse_Thr(BiThrTree tep){
	while(tep){
		while(tep->LTag == Link) tep = tep->lchild;//找到中序第一个节点 
		cout<<tep->data<<endl;
		while(tep->RTag == Thread && tep->rchild != NULL){
			tep = tep->rchild;
			cout<<tep->data<<endl;
		}
		tep = tep->rchild;
	}
}

int main(){
	BiThrTree con=new BiThrNode;
	CreateBiTree(&con);
	InThreading(con);
	InOrderTraverse_Thr(con);
	return 0;
}