二叉树的操作

目录

链式存储结构

先序遍历二叉树

递归算法

非递归算法

中序遍历二叉树

递归算法

非递归算法

后序遍历二叉树

递归算法

非递归算法

层次遍历二叉树

线索树

用土方法找到中序前驱

中序线索化

先序线索化

线索二叉树找后继

线索二叉树找前驱

线索二叉树的遍历

---

链式存储结构

struct ElemType{
	int value;
};
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//定义一颗空树
BiTree root=NULL;
//插入根节点
root=(BiTNode)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;
//插入新节点
BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;//作为根节点的左孩子

先序遍历二叉树

递归算法

若二叉树为空，则遍历结束：否则

1. 访问根节点
2. 先序遍历左子树（递归调用本算法）
3. 先序遍历右子树

//先序遍历的递归算法
void PreorderTraverse(BTNode *T){
	if(T!=NULL){
		visit(T->data);//访问根节点
		PreorderTraverse(T->Lchild);
		PreorderTraverse(T->Rchild);
	}
}

非递归算法

设T是指向二叉树根节点的指针变量，非递归算法是：

若二叉树为空，则返回：否则，令p=T;

1. 访问p所指向的节点
2. q=p->Rchild,若q不为空，则q进栈
3. p=p->Lchild,若p不为空，转（1）否则转（4）
4. 退回到p，转（1），直到栈空为止。

#define MAX_NODE 50
void PreorderTraverse(BTNode *T){
	BTNode *Stack[MAX_NODE],*p=T,*q;
	int top=0;
	if(T==NULL){
		printf("Binary Tree is Empty!\n");
	}
	else{
		do{
			visit(p->data);
			q=p->Rchild;
			if(q!=NULL)
				stack[++top]=q;
			p=p->Lchild;
			if(p==NULL){
				p=stack[top];
				top--;
			}
		}while(p!=NULL);
	}
}

中序遍历二叉树

递归算法

若二叉树为空，则遍历结束；否则：

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

void InorderTraverse(BTNode *T){
	if(T!=NULL){
		InorderTraverse(T->Lchild);
		visit(T->data);
		InorderTraverse(T->Rchild);
	}
}

非递归算法

设T是指向二叉树根节点的指针变量，非递归算法是：

若二叉树为空，则返回；否则令p=T;

1. 若p不为空，p进栈，p=p->Lchild,一直循环；
2. 否则（p为空），退栈到p，访问p所指向的节点
3. p=p->Rchild,转（1）

#define MAX_NODE 50
void InorderTraverse(BTNode *T){
	BTNode *stack[MAX_NODE],*p=T;
	int top=0,bool=1;
	if(T==NULL)
		printf("Binary Tree is Empty!\n");
	else{
		do{
			while(p!=NULL){
				stack[++top]=p;
				p=p->Lchild;
			}
			if(top==0){
				bool=0;
			}
			else{
				p=stack[top];
				top--;
				vist(p->data);
				p=p->Rchild;
			}
		}while(bool!=0);
	}
}

后序遍历二叉树

递归算法

void InorderTraverse(BTNode *T){
	if(T!=NULL){
		InorderTraverse(T->Lchild);
        InorderTraverse(T->Rchild);
		visit(T->data);
	}
}

非递归算法

#define MAX_NODE 50
void PostorderTraverse(BTNode *T){
	BTNode *S1[MAX_NODE],*p=T;
	int S2[MAX_NODE],top=0,bool=1;
	if(T==NULL)
		printf("Binary Tree is Empty!\n");
	else{
		do{
			while(p!=NULL){
				S1[++top]=p;
				S2[top]=0;
				p=p->Lchild;
			}
			if(top==0)
				bool=0;
			else if(S2[top]==0){
				p=S1[top]->Rchild;
				S2[top]=1;
			}
			else{
				p=S1[top];
				top--;
				visit(p->data);
				p=NULL;
			}while(bool!=0);
		}
	}
}

层次遍历二叉树

层次遍历二叉树，是从根节点开始遍历，按层次次序“”“自上而下，从左到右”访问树中各个节点。为保证是按层次遍历，必须设置一个队列，初始化时为空。设T是指向根节点的指针变量，层次遍历费递归算法是：

1. 初始化一个辅助队列
2. 根节点入队
3. 若队列非空，则队头节点出队，访问该节点，并将其左右孩子插入队尾；’
4. 重复3直至队列为空

#define MAX_NODE 50
void LevelorderTraverse(BTNode *T){
	BTNode *Queue[MAX_NODE],*p=T;
	int front=0,rear=0;
	if(p!=NULL){
		Queue[++rear]=p;
		while(front
			p=Queue[++front];
			visit(p->data);
			if(p->Lchild!=NULL)
				Queue[++rear]=p->Lchild;
			if(p->Rchild!=NULL)
				Queue[++rear]=p->Rchild;
		}
	}
}

线索树

遍历二叉树是按照一定的规则将树中的节点排列成一个线性序列，即对非线性结构的线性操作。如何找到遍历过程中动态得到的每个节点的直接前驱和直接后继？如何保存这些信息。

设一颗二叉树有n个节点，则有n-1条边，而n个节点共有2n个指针域，显然有n+1个空闲指针域未用，则可以利用这些空闲指针域来存储节点的直接前驱和直接后继。

若节点有左孩子，则Lchild指向左孩子，否则指向其直接前驱；

若节点有右孩子，则Rchild指向右孩子，否则直线其直接后继；

为避免混淆，对节点结构加以改进，增加两个标志域，

Lchild  Ltag  data  Rchild  Rtag

Ltag=0:Lchild指示节点的左孩子

        =1：Lchild指示节点的前驱

用这种节点结构构成的二叉树的存储结构；叫做线索链表；指向节点前驱和后继的指针叫做线索；按照某种层次遍历，加上线索二叉树称之为线索二叉树；

//线索二叉树的节点结构与示例
typedef struct BiThrNode{
	ElemType data;
	struct BiThrNode *Lchild,*Rchild;
	int Ltag,Rtag;
}ThreadNode,*ThreadTree;

用土方法找到中序前驱

void InOrder(BiTree T){
	if(T!=NULL){
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}
//访问节点q
void visit(BiTNode *q){
	if(q==p)//当前访问的刚好是p节点
		final=pre;
	else
		pre=q;//pre指向当前访问的节点
}
//辅助全局变量，用于查找p的前驱
BiTNode *p;//p指向目标节点
BiTNode *pre=NULL; //指向当前访问节点的前驱
BiTNode *final=NULL;//用于记录最终结果

中序线索化

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
	if(T!=NULL){
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
}
void visit(ThreadNode *q){
	if(q->lchild==NULL){
		q->lchild=pre;
		q->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){
		pre->rchild=q;//建立前驱节点的后继线索
		pre->rtag=1;
	}
	pre=q;
}
ThreadNode *pre=NULL;
//中序线索化二叉树
void CreateInThread(ThreadTree T){
	pre=NULL;
	if(T!=NULL){
		InThread(T);
		if(pre->rchild==NUll){
			pre->rtag=1;//处理遍历的最后一个节点
		}
	}
}

先序线索化

void InThread(ThreadTree T){
	if(T!=NULL){
		visit(T);
		if(T->ltag==0)//lchild不是前驱线索
			InThread(T->lchild);
		InThread(T->rchild);
	}
}

线索二叉树找后继

//中序线索二叉树找中序后继
//找到以P为根的子树中，第一个被中序遍历的节点
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag==0)
		p=p->lchild;
	return p;
}
//在中序线索二叉树中找到节点p的后继节点
ThreadNode *Nextnode(ThreadNode *p){
	//右子树中最左下节点
	if(p->rtag==0)
		return Firstnode(p->rchild);
	else
		return p->rchild;//rtag==1直接返回后继线索
}
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
		visit(p);
}

线索二叉树找前驱

//找到以P为根的子树中，最后一个被中序遍历的节点
ThreadNode *Lastnode(ThreadNode *p){
	while(p->rtag==0)
		p=p->rchild;
		return p;
}
//在中序线索二叉树中找到节点p的前驱节点
ThreadNode *Prenode(ThreadNode *p){
	//左子树中最右下节点
	if(p->ltag==0)
		return Lastnode(p->lchild);
	else
		return p->lchild;//ltag==1直接返回前驱线索
}
//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
	for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
		visit(p);	
}

线索二叉树的遍历

//先序二叉树的先序遍历
void preorder_Thread_bt(BiThrNode *T){
	BiThrNode *p=T;
	while(p!=NULL){
		visit(p->data);
		if(p->Ltag==0)
			p=p->Lchild;
		else
			p=p->Rchild;
	}
}
//中序线索二叉树的中序遍历
void inorder_Thread_bt(BiThrNode *T){
	BiThrNode *p;
	while(T!=NULL){
		p=T;
		while(p->Ltag==0)
			p=p->Lchild;
		while(p!=NULL){
			visit(p->data);
			if(p->Rtag==1)
				p=p->Rchild;
		else{
			p=p->Rchild;
			while(p->Ltag==0){
				p=p->Lchild;
			}
		}
 
		}
		
	}
}