【数据结构】·【二叉树】

搞懂递归过程，结构基本和单链表结构类似，多了个link域。其他的（计算高，返回结点）都差不多也就不敲了，实现前序建立二叉树，中序遍历。

#include<iostream>
#include<stdlib.h>
using namespace std;

template<class T>
struct BinTreeNode{
	T data;
	BinTreeNode<T> *leftChild,*rightChild;
	BinTreeNode(T& item){
		data=item;
		leftChild=NULL;
		rightChild=NULL;
	}
	BinTreeNode(){}
};

template<class T>
class BinaryTree{
public:
	BinTreeNode<T> *root;
	T RefValue;

	BinaryTree(){}
	BinaryTree(T value){
		RefValue=value;
	}
	~BinaryTree(){
		destroy(root);
	}
	
	void CreatBinTree(istream& in,BinTreeNode<T> *& subTree);
	void destroy(BinTreeNode<T> *& subTree);
	void inOrder(ostream& out,BinTreeNode<T> *& subTree);//中序遍历
	void visit(BinTreeNode<T>* p){
		cout<<p->data<<endl;
	}
	friend istream& operator >>(istream& is,BinaryTree<T>& Tree){
		Tree.CreatBinTree(is,Tree.root);
		return is;
	}
	friend ostream& operator <<(ostream& os,BinaryTree<T>& Tree){    //重载<<输出二叉树
		os<<"二叉树的中序遍历n";
		Tree.inOrder(os,Tree.root);
		os<<endl;
		return os;
	}	
};


template<class T>
void BinaryTree<T>::CreatBinTree(istream& in,BinTreeNode<T> *& subTree){   
	T item;
	if(!in.eof()){
		in>>item;
		if(item!=RefValue){
			subTree =new BinTreeNode<T>(item);
			if(subTree == NULL){
				cerr<<"存储分配错误！"<<endl;
				exit(1);
			}
			CreatBinTree(in,subTree->leftChild);
			CreatBinTree(in,subTree->rightChild);
		}
		else
			subTree=NULL;
	}
}


template<class T>
void BinaryTree<T>::destroy(BinTreeNode<T> *& subTree){
	if(subTree!=NULL){
		destroy(subTree->leftChild);
		destroy(subTree->rightChild);
		delete subTree;
	}
}

template<class T>
void BinaryTree<T>::inOrder(ostream& out,BinTreeNode<T> *& subTree){
	if(subTree!=NULL){		
		inOrder(out,subTree->leftChild);
		out<<subTree->data<<' ';
		inOrder(out,subTree->rightChild);
	}	
}

void main(){
	BinaryTree<char> tree;
	tree.RefValue='#';
	
	cin>>tree;
	cout<<tree;
	
}

二叉树原型：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!