线索二叉树

1.算法描述

就是简单的线索二叉树的建立，遍历，查找等基本操作，具体什么是线索二叉树，百度一下！

 

2.算法说明

具体说明有四点：如下图

注：尤其要注意第4点，我在写的时候就没注意这个问题，结果遍历的时候出现了无限循环，找了半天才找到！主要是建立二叉树判断的惯性思维，故而容易出现错误！

 

3.代码实现

头文件

 

#ifndef BITHRTREE_H
#define BITHRTREE_H

enum flag{CHILD, THREAD};//枚举类型，枚举常量Child=0，Thread=1
template<class T>
struct Node{						//二叉线索树的结点结构
	Node<T> *rchild, *lchild;
	int lflag, rflag;
	T data;
};


template<class T>
class BiThrTree{
	public:
		BiThrTree();
		~BiThrTree();
		Node<T>* getRoot( );            //获取根结点
    Node<T>* next(Node<T>* p);   		//查找结点p的中序后继结点
    void inOrder(Node<T>* root);    //中序遍历线索链表
		Node<T>* inPreNode(Node<T>* p); //查找结点p的中序前驱结点
		Node<T>* searchNode(T x);				//查找结点x
		
	private:
		Node<T>* root;        					//指向线索链表的头指针
    void creatThrTree(Node<T>* &root);    		//创建二叉树
    void biThrTree(Node<T>* &root, Node<T>* &pre);  //二叉树的线索化(中序线索二叉树)
    void release(Node<T>* root);    //析构函数调用
};

#endif

 

 bithrtree.cpp

标//<-------------notice------------>就是容易出错的地方！！

 

#include <iostream>
#include "bithrtree.h"
using namespace std;

template<class T>
BiThrTree<T>::BiThrTree(){
	Node<T>* pre = NULL;
	creatThrTree(root);
	biThrTree(root, pre);
}

template<class T>
BiThrTree<T>::~BiThrTree(){
	release(root);
}
		
//获取根结点
template<class T>
Node<T>* BiThrTree<T>::getRoot( ){
	return root;
}  

//查找结点p的中序后继结点   
template<class T>      
Node<T>* BiThrTree<T>::next(Node<T>* p){
	Node<T>* t;
	//如果有右子树，则后继就是右子树的第一个结点最左节点，如果第一个结点没有左子树，则就是右子树第一个结点
	if(p->rflag == CHILD){ //<-------------notice------------> 
		t = p->rchild;
		while(t->lflag == CHILD){//即存在左子树.注：不能使用t->lchild判断，因为二叉树已经线索化，故而也不为空
			t = t->lchild;
		}
		return t;
	}else{
		return p->rchild;
	}
}

//中序遍历线索链表
template<class T>  		
void BiThrTree<T>::inOrder(Node<T>* root){
	if(root){
		//先找到最左的结点
		while(root->lflag == CHILD){//不能是root->lchild<-------------notice------------> 
			root = root->lchild;
		}
		//开始中序遍历
		do{
			cout<<root->data<<" ";
			root = next(root);
		}while(root);
	}
}    

//查找结点p的中序前驱结点
template<class T>
Node<T>* BiThrTree<T>::inPreNode(Node<T>* p){
	Node<T>* t;
	if(p->lflag == THREAD){//<-------------notice------------> 
		return p->lchild;
	}else{
		//如果p有左孩子，那么左孩子的最右结点就是其前驱
		t = p->lchild;
		while(t->rflag == CHILD){//有右孩子(不要用t->rchild)<-------------notice------------> 
			t = t->rchild;
		}
		return t;
	}
}

//查找结点x 
template<class T>
Node<T>* BiThrTree<T>::searchNode(T x){
	Node<T>* t = NULL;
	if(root){
		//先找到最左的结点
		while(root->lflag == CHILD){//<-------------notice------------> 
			root = root->lchild;
		}
		//开始中序遍历
		do{
			if(root->data == x){ 
				t = root;
				break;
			}
			root = next(root);
		}while(root);
	}
	return t;
}		

//创建二叉树
template<class T>
void BiThrTree<T>::creatThrTree(Node<T>* &root){
	T ch;
	cout<<"请输入创建一棵二叉树的结点数据"<<endl;
	cin>>ch;
	if(ch == "#") root = NULL;
	else{
		root = new Node<T>;
		root->data = ch;
		creatThrTree(root->lchild);
		creatThrTree(root->rchild);
	}
}   

//二叉树的线索化(中序线索二叉树)
template<class T> 		
void BiThrTree<T>::biThrTree(Node<T>* &root, Node<T>* &pre){
	if(root){
		biThrTree(root->lchild, pre);
		
		//<--------------------------notice-------------------------> 
		//左孩子处理（lflag和前驱）
		if(!root->lchild){
			root->lflag =  THREAD;
			root->lchild = pre;
		}else{
			root->lflag = CHILD;
		}
		//右孩子处理(rflag不能处理后序，因为还没遍历到)
		if(!root->rchild){
			root->rflag = THREAD;
		}else{
			root->rflag = CHILD;
		}
		//pre的后续（rflag之前已经处理，如果设置为了索引，设置右索引为root）
		if(pre){
			if(pre->rflag == THREAD) pre->rchild = root;
		}
		//<--------------------------notice------------------------->
		
		//记录前驱
		pre = root;
		biThrTree(root->rchild, pre);
	}
}

//析构函数调用
template<class T>
void BiThrTree<T>::release(Node<T>* root){
	if(root){
		release(root->lchild);
		release(root->rchild);
		delete root;
	}
}

 

 

 

 main.cpp

 

#include <iostream>
#include <string>
#include "bithrtree.cpp"
using namespace std;

int main(){
	BiThrTree<string> bt;
	Node<string>* t = bt.getRoot();
	
	cout<<"------中序遍历-------"<<endl;
	bt.inOrder(t);
	cout<<endl;
	
	Node<string>* r;
	cout<<"查找结点b:";
	r = bt.searchNode("b");
	if(r) cout<<r->data<<endl;
	else cout<<"无"<<endl;
	
	cout<<"b的前驱:";
	r = bt.inPreNode(r);
	if(r) cout<<r->data<<endl;
	else cout<<"无"<<endl;
		
	cout<<"a的前驱:";
	r = bt.searchNode("a");
	r = bt.inPreNode(r);
	if(r) cout<<r->data<<endl;
	else cout<<"无"<<endl;
		
	cout<<"d的前驱:";
	r = bt.searchNode("d");
	r = bt.inPreNode(r);
	if(r) cout<<r->data<<endl;
	else cout<<"无"<<endl;
		
	return 0;
}

 

 4.总结

基本上只要明白了二叉树的基本原理，线索二叉树就非常的简单，就多了一个线索化的过程，简化了搜索前序和后继结点的时间，提高了效率！

如果有什么不对的地方，欢迎指正！