# 先序，中序，后序线索二叉树

+关注继续查看

//后序线索，这种方法不容易想到
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

struct TREE{
int    val;
TREE *ch[2];
TREE(){}
TREE(int val){
this->val = val;
ch[0] = ch[1] = NULL;
}
};

void buildT(TREE * &T){
int x;
scanf("%d", &x);
if(x == -1) return ;

T = new TREE(x);
buildT(T->ch[0]);
buildT(T->ch[1]);
}

if(!T) return;
if(pre){
if(pre->ch[0] == T && pre->ch[1])//T是左子树
else //T是右子树
}
}

void printT_pre(TREE *T){//前序打印
if(!T) return ;
printf("%d ", T->val);
printT_pre(T->ch[0]);
printT_pre(T->ch[1]);
}

TREE *root = T;
bool flag = true;//表明T所在的字数没有访问过
while(1){
while(flag && T->ch[0]) T = T->ch[0];
printf("%d ", T->val);
flag = false;//如果 T没有兄弟节点了，就一直沿着它的父节点向上走
else flag = true;
if(T == root){//再次回到最顶端父节点时， 结束！
printf("%d ", T->val);
break;
}
}
}

int main(){
TREE *T = NULL;
buildT(T);
printT_pre(T);
printf("\n");
printf("\n");
return 0;
}

//先序线索
#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int d;
struct tree* lchild;
struct tree* rchild;
int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
int d;
scanf("%d", &d);
if(d!=-1)
{
T=(TREE)malloc(sizeof(tree));
T->d=d;
T->lchild=T->rchild=NULL;
build_tree(T->lchild);
build_tree(T->rchild);
}
}

TREE pre;

{
if(p)
{
if(!p->lchild)
{
p->lchild=pre;
}
if(!pre->rchild)
{
pre->rchild=p;
}
pre=p;
}
}

void print_preThr_tree(TREE T)
{
TREE p=T;
while(1)
{
{
printf("%d ", p->d);
p=p->lchild;
}
printf("%d ", p->d);
p=p->rchild;
if(p==T) break;
{
printf("%d ", p->d);
p=p->rchild;
}

}
}

void print_tree(TREE T)
{
if(T)
{
printf("%d ", T->d);
print_tree(T->lchild);
print_tree(T->rchild);
}
}

int main()
{
TREE T=NULL;
build_tree(T);
print_tree(T);//递归先序遍历
printf("\n");
pre=T;
pre->rchild=T;
print_preThr_tree(T);
return 0;
}

//中序线索
#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int d;
struct tree* lchild;
struct tree* rchild;
int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
int d;
scanf("%d", &d);
if(d!=-1)
{
T=(TREE)malloc(sizeof(tree));
T->d=d;
T->lchild=T->rchild=NULL;
build_tree(T->lchild);
build_tree(T->rchild);
}
}

TREE pre;

{
if(p)
{
if(!p->lchild)
{
p->lchild=pre;
}
if(!pre->rchild)
{
pre->rchild=p;
}
pre=p;
}
}

/*

{
if(p)
{
if(!p->lchild)
{
p->lchild=pre;
}
if(pre && !pre->rchild)
{
pre->rchild=p;
}
pre=p;
}
}
*/

void print_tree(TREE T){
if(T)
{
print_tree(T->lchild);
printf("%d ", T->d);
print_tree(T->rchild);
}
}

void print_inorThr_tree(TREE T)
{
TREE p=T;
while(1)
{
p=p->lchild;
printf("%d ", p->d);
{
p=p->rchild;
printf("%d ", p->d);
}
p=p->rchild;
if(p==T)
break;
}
}

int main()
{
TREE T=NULL;
build_tree(T);
print_tree(T);//递归中序遍历
printf("\n");
pre=T;
pre->rchild=T;
pre->Rtag=0;//保证只有一个结点的情况
print_inorThr_tree(T);
return 0;
}

//后序线索
#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int d;
struct tree* lchild;
struct tree* rchild;
struct tree* rrchild;
int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
int d;
scanf("%d", &d);
if(d!=-1)
{
T=(TREE)malloc(sizeof(tree));
T->d=d;
T->lchild=T->rchild=NULL;
build_tree(T->lchild);
build_tree(T->rchild);
}
}

TREE pre;

{
if(p)
{

if(!p->lchild)
{
p->lchild=pre;
}
if(!pre->rchild )
{
pre->rchild=p;
} else {
pre->rrchild=p;
}
pre=p;
}
}

void print_postThr_tree(TREE T)
{
TREE p=T;
p=p->lchild;
while(1)
{
printf("%d ", p->d);
if(p==T)
break;
p=p->rchild;
else
p=p->rrchild;
}
}

void print_tree(TREE T)
{
if(T)
{
print_tree(T->lchild);
print_tree(T->rchild);
printf("%d ", T->d);
}
}

int main()
{
TREE T=NULL;
build_tree(T);
print_tree(T);//递归后序遍历
printf("\n");
pre=T;
pre->rchild=T;
print_postThr_tree(T);
return 0;
}

0 0

0 0
【C++】二叉树的遍历：前序、中序、后序、层序
【C++】二叉树的遍历：前序、中序、后序、层序
0 0
【小白学算法】8.二叉树的遍历，前序、中序和后序
【小白学算法】8.二叉树的遍历，前序、中序和后序
0 0

0 0

424 0

616 0
+关注