实验三 二叉树的物理实现（左子右兄弟-顺序表）_左子右兄弟表示法

• 说明
• 基于顺序表的左子/右兄弟结点表示法
• 参考资料

一、说明

1、树的存储结构一般有父结点表示法（双亲表示法，一般是顺序表），子结点表示法（链表+顺序表），左子/右兄弟结点表示法（链表+顺序表）；

2、在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）（来源于百度百科）；

3、左子结点/右兄弟结点表示法本质上是用二叉树来替换树，使用这种方法能把任意树替换为二叉树。如下图：

4、结点M的深度就是从根结点到M的路径长度。数的高度是等于最深结点的深度加1.任何深度为d的结点的层数都为d。根结点的层数为0，深度也为0（深度从0开始计数）；

5、因为BIT一般为树状数组（Binary Indexed Tree）的简写，因此将二叉树（Binary Tree）相关命名为BinNode、BinTree等；

6、左儿子右兄弟结点表示法的中序遍历经查阅部分资料尚未找到正确方法，若有大牛知晓烦请告知；

7、调用遍历函数前，需要预处理，详见代码；

8、以下代码仅供参考。

 

二、基于顺序表的左子/右兄弟结点表示法

1、BinNode.h

#include<iostream>
using namespace std;
#ifndef _BinNode
#define _BinNode
namespace wangzhe
{
	template<typename E>
	class BinNode
	{
		private:
		    E it;//数据域 
		    int l;//最左儿子结点下标 
		    int r;//右邻兄弟结点下标 
		public:
			BinNode()
			{
				l=r=-1;
			}
			E& element()
			{
				return it;
			}
			void setElement(const E& e)
		        {
		    	        it=e;
			}
			int left() const
			{
				return l;
			}
			void setLeft(int b)
	    	        {
	    		        l=b;
			}
	    	        int right() const
	    	        {
	    		        return r;
			}
	    	        void setRight(int b)
	    	        {
	    		        r=b;
			}
	    	        bool isLeaf()
	    	        {
	    		        return r==-1;
			}
	};
}
#endif

2、BinTree.h

#include<iostream>
using namespace std;
#include"BinNode.h"
#ifndef _BinTree
#define _BinTree
namespace wangzhe
{
	template<typename E>
	class BinTree
	{
		private:
			int size;//能存储最大的结点个数 
		        BinNode<E>* T;//存储树结点的数组
			int *D;//存储各结点的深度
			int height;//树的高度 
		public:
			BinTree(int sz);//构造函数 
			~BinTree();//析构函数
			void createBinTree();//按给定方法输入一棵二叉树(层序) 
                        void clear();//销毁一颗二叉树 
			void Root();//返回根节点
			void setRoot(E e);//设置根节点 
			void Depthhelp(int u,int d);//求出各结点的深度 ，预处理 
			bool isEmpty();//判断二叉树是否为空 
			void preorder(int u);//前序遍历
			//void inorder(int u);//中序遍历
			void postorder(int u);//后序遍历
			void levelorder(int u);//层次遍历
			int BinTreeDepth();//二叉树高度
			int count(int u);//二叉树结点数 
	};	
}
#endif

3、BinTree.cpp

#include<iostream>
#include<queue> 
#include<algorithm> 
using namespace std;
#include"BinTree.h"
namespace wangzhe
{
	template<typename E>
        BinTree<E>::BinTree(int sz)
	{ 
	        T=new BinNode<E>[sz];
	        D=new int[sz]; 
		for(int i=0;i<sz;i++)//一开始都没有子结点和兄弟结点	
		{
			D[i]=-1;
		}
		size=sz;
		height=0; 
	}	
	
	template<typename E>
        BinTree<E>::~BinTree()
	{
		clear();
	}	
	
	template<typename E>
	void BinTree<E>::createBinTree() 
	{
		if(D[0]==-1)
		{
			cout<<"该树无根结点，为空树\n"; 
		    return;	
		} 
		int cnt=0;
		E p,c;//父结点数据,子结点数据 
		queue< BinNode<E>* > que;
		que.push(&T[0]);
		
		while(cin>>p>>c)
		{
			if(p=='#'&&c=='#') break;
			cnt++;
			if(cnt+1>size)  
			{
				cout<<"结点数超限\n"; break;
			}
 
			while(que.front()->element()!=p&&!que.empty()) {que.pop();}
			if(que.empty()) 
			{
				cout<<"结点不匹配\n";
			        break;//不能连成树 
			}
			
			if(que.front()->left()==-1)//最左 
			{
				T[cnt].setElement(c);
				que.front()->setLeft(cnt);
				que.push(&T[cnt]);
			}
			else//右邻 
			{
				T[cnt].setElement(c);
				int x=que.front()->left();
				while(T[x].right()!=-1) x=T[x].right();
				T[x].setRight(cnt);
				que.push(&T[cnt]);
			}
		}	
	}
	
	template<typename E>
	void BinTree<E>::clear() 
	{
		delete [] T;
	}
	
	template<typename E>
	void BinTree<E>::setRoot(E e)
	{
		T[0].setElement(e);
		D[0]=0;
	}
	
	template<typename E>
	void BinTree<E>::Depthhelp(int u,int d)
	{
		D[u]=d;
	        if(T[u].left()!=-1) Depthhelp(T[u].left(),d+1);
	        if(T[u].right()!=-1) Depthhelp(T[u].right(),d);
	        height=max(height,d);
	}
	
	template<typename E>
	bool BinTree<E>::isEmpty()
	{
		return D[0]==-1;
	}
	
	template<typename E>
	void BinTree<E>::preorder(int u)
	{
		if(u==-1) return;
		cout<<T[u].element()<<' ';
		preorder(T[u].left());
		preorder(T[u].right());
	}
	
	template<typename E>
	void BinTree<E>::postorder(int u)
	{
		if(u==-1) return;
		postorder(T[u].left());
		cout<<T[u].element()<<' ';
		postorder(T[u].right());
	}
	
	template<typename E>
	void BinTree<E>::levelorder(int u)
	{
		int n=count(0);
		for(int i=0;i<n;i++)
		cout<<T[i].element()<<' ';
	}
	
	template<typename E>
	int BinTree<E>::BinTreeDepth()//高度 要+1
	{
		return height+1;
	}
	
	template<typename E>
	int BinTree<E>::count(int u)
	{
		if(u==-1) return 0;
		return 1+count(T[u].left())+count(T[u].right());
	}
}

4、main.cpp

#include <iostream>
using namespace std; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#include"BinTree.h"
#include"BinTree.cpp"
using namespace wangzhe;
int main(int argc, char** argv) 
{
	for(int i=1;i<=50;i++) cout<<'*';
        cout<<"\n实验三：二叉树的物理实现(顺序表、左子右兄弟)\n";
	for(int i=1;i<=50;i++) cout<<'*';
	cout<<"\n请输入根节点数据：\n";
	char r;
	cin>>r;
	BinTree<char> Tree(101);
	Tree.setRoot(r);
	cout<<"请以层序依次输入各子结点数据（以# #作为结束标志）：";
	cout<<"\n（数据类型为单个字符，如输入A B表示父结点数据是A，有一个子结点数据是B）\n" ;
	Tree.createBinTree(); 
	Tree.Depthhelp(0,0); //预处理 
	cout<<"\n这棵二叉树前序遍历的结果为：\n"; 
	Tree.preorder(0); 
	cout<<"\n这棵二叉树后序遍历的结果为：\n" ; 
	Tree.postorder(0); 
	cout<<"\n这棵二叉树层次遍历的结果为：\n" ;
	Tree.levelorder(0); 
	cout<<"\n这棵二叉树的高度是：\n" ; 
	cout<<Tree.BinTreeDepth();
	cout<<"\n这棵二叉树的结点个数是：\n" ; 
	cout<<Tree.count(0)<<endl; 
	return 0;
	/*A 
	A B 
	A C 
	B D 
	B E 
	C G 
	C H 
	# # */
}

5、运行结果

 

三、参考资料

1、姬小野_有根树的表达_左子右兄弟表示法

2、zhou2214_树的左孩子 右兄弟表示法的建立过程 （后序遍历）