数据结构——二叉树-阿里云开发者社区

1 基本定义

①二叉树是n（n>=0）个结点的有限集，当n=0时，二叉树为空。当n>0时，二叉树是由一个根节点及至多两颗子树组成，且左右子树都是二叉树。

不同于树，二叉树中的结点要区分左子树和右子树，即使只有一颗子树，左单子树不同于右单子树。

②树的一些基本术语：

结点：包含了数据元素及若干个指向其子树的分支。

结点的度：结点的子树数目或分支个数。

树的度：在树中取各结点的度的最大值。

结点的路径：从根结点到该结点所经分支和结点构成的结点的路径。

结点的层次：设根结点的层次为1，则其子树的根结点层次为2，第L层结点的子树的根结点层次为L。

树的深度：树中结点（该结点必为叶子结点）的最大层次。

无序树：子树之间不存在次序关系（子树能够调换）

有序树：子树之间存在次序关系（子树不能调换）

③几种特殊形态的二叉树

满二叉树：一棵深度为k的二叉树，若每一层上的结点树都达到最大则称其为满二叉树。

完全二叉树：一棵具有n个结点且深度为k的二叉树，若前k-1层的结点树都达到最大，剩余的结点在第k层中从左到右连续分布则称其为完全二叉树。

拟满二叉树：一棵具有n个结点且深度为k的二叉树，若前k-1层的结点树都达到最大，剩余的结点在第k层中随机分布则称其为完全二叉树。

正则二叉树：在一棵二叉树中，如果只存在度为0和度为2的结点，则称其为正则二叉树。

平衡二叉树：在一棵二叉树中，若任一子树均满足：|左子树的深度 - 右子树的深度| <= 1，则称其为平衡二叉树。

2 二叉树的存储结构

2.1 二叉树的顺序存储结构

const int MAXSIZE = 100;
template<class ElemType> 
struct SqBiTree
{
	ElemType* base;
	int nodeNum; //二叉树中结点树
};

①为了能够在存储结构中表达结点之间的逻辑关系，必须将二叉树的结点按照一定的规律安排在顺序存储单元中。

②二叉树的顺序存储结构对于具有n个结点的普通二叉树而言，为保证既存储数据，又表达数据元素之间的关系，必须为其分配2^n - 1个顺序存储单元，空间复杂度为O(2^n)。因此顺序存储结构对于普通二叉树而言并不理想，因此二叉树大多采用链式存储结构。

2.2 二叉树的链式存储结构

2.2.1 分类

①二叉链表：二叉树的结点包含数据元素及指向其左、右子树的分支。C++模板方式定义如下：

template<class T>
struct BTnode
{
	T data;
	BTnode<T> *Lchild, *Rchild;
};

②三叉链表：在二叉链表的基础上增设了一个双亲指针域

③静态二叉树表：在结点包括游标域的结构类型向量中用游标代替指针，同样可以表示二叉链表和三叉链表。静态二叉树表常用于数据对象中的元素个数是限定的情况，或用于不支持指针的高级语言中。

2.2.2 二叉链表类的定义

//BinaryTree.h
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <stack>
#include <queue>
#include "BTnode.h"
using namespace std;

template<class T>
class BinaryTree
{
public:
	BinaryTree():m_root(NULL){}

	BinaryTree(const BinaryTree &rhs)
	{
		m_root = _Copy(rhs.m_root);
	}

	BinaryTree& operator=(const BinaryTree& rhs)
	{
		if (&rhs == this)
		{
			return *this;
		}
		_Destroy(m_root);
		m_root = _Copy(rhs.m_root);
		return *this;
	}

	~BinaryTree()
	{
		_Destroy(m_root);
	}

	void Create1(T ch[], const T&);

	void Create2(T ch1[], T ch2[], int);

	void Clear()
	{
		_Destroy(m_root);
	}

	bool IsEmpty() const
	{
		return m_root == NULL;
	}

	BTnode<T>* Root() const
	{
		return m_root;
	}

	BTnode<T>* Locate(T& e)
	{
		return _Locate(m_root, e);
	}

	int Depth()
	{
		return _Depth(m_root);
	}

	BTnode<T>* Parent(BTnode<T>* p)
	{
		return _Parent(m_root, p);
	}

	BTnode<T>* LeftChild(BTnode<T>* p)
	{
		return p->Lchild;
	}

	BTnode<T>* RightChild(BTnode<T>* p)
	{
		return p->Rchild;
	}

	BTnode<T>* LeftSibling(BTnode<T>* p);

	BTnode<T>* RightSibling(BTnode<T>* p);

	void PreorderTraverse(void (*visit)(const T&));

	void PreorderTraverseNonRecursive(void (*visit)(const T&));

	void InorderTraverse(void (*visit)(const T&));

	void InorderTraverseNonRecursive(void (*visit)(const T&));

	void PostorderTraverse(void (*visit)(const T&));

	void PostorderTraverseNonRecursive(void (*visit)(const T&));

	void LevelTraverse(void (*visit)(const T&));

	bool InsertChild(BTnode<T>* p, const int&, BinaryTree<char>&);

	void DeleteChild(BTnode<T>*p, int);

private:
	BTnode<T> *m_root;
	BTnode<T>* _Copy(BTnode<T>*);
	void _Create1(BTnode<T>* &, T ch[], const T&, int&);
	void _Create2(BTnode<T>* &, T ch1[], T ch2[], int, int, int&);
	void _Destroy(BTnode<T>* &);
	int _Depth(BTnode<T>*);
	BTnode<T>* _Locate(BTnode<T>*, const T&);
	BTnode<T>* _Parent(BTnode<T>*, BTnode<T>*);
	void _PreorderTraverse(BTnode<T>* R, void (*visit)(const T& e));
	void _InorderTraverse(BTnode<T>*, void (*visit)(const T&));
	void _PostorderTraverse(BTnode<T>*, void (*visit)(const T&));
};

template<class T> void BinaryTree<T>::_PreorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
	if (R)
	{
		visit(R->data);
		_PreorderTraverse(R->Lchild,visit);
		_PreorderTraverse(R->Rchild,visit);
	}
}

template<class T> void BinaryTree<T>::PreorderTraverse(void (*visit)(const T& e))
{
	_PreorderTraverse(m_root, visit);
}

template<class T> void BinaryTree<T>::_InorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
	if (R)
	{
		_InorderTraverse(R->Lchild,visit);
		visit(R->data);
		_InorderTraverse(R->Rchild,visit);
	}
}

template<class T> void BinaryTree<T>::InorderTraverse(void (*visit)(const T& e))
{
	_InorderTraverse(m_root,visit);
}

template<class T> void BinaryTree<T>::_PostorderTraverse(BTnode<T>* R, void (*visit)(const T& e))
{
	if (R)
	{
		_PostorderTraverse(R->Lchild,visit);
		_PostorderTraverse(R->Rchild,visit);
		visit(R->data);
	}
}

template<class T> void BinaryTree<T>::PostorderTraverse(void (*visit)(const T& e))
{
	_PostorderTraverse(m_root,visit);
}

template<class T> void BinaryTree<T>::_Create1(BTnode<T>* &R, T ch[], const T& c, int& i)
{
	if (ch[i] == c) //c is a special character which indicates a null pointer
	{
		R = NULL;
	}
	else
	{
		R = new BTnode<T>;
		R->data = ch[i];
		_Create1(R->Lchild,ch,c,++i);
		_Create1(R->Rchild,ch,c,++i);
	}
}

template<class T> void BinaryTree<T>::Create1(T ch[], const T& c)
{
	int i = 0;
	_Create1(m_root,ch,c,i);
}

template<class T> void BinaryTree<T>::_Destroy(BTnode<T>* &R)
{
	if (R)
	{
		_Destroy(R->Lchild);
		_Destroy(R->Rchild);
		delete R;
	}
	R = NULL;
}

template<class T> int BinaryTree<T>::_Depth(BTnode<T>* R)
{
	if (!R)
	{
		return 0;
	}
	int h1,h2;
	h1 = _Depth(R->Lchild);
	h2 = _Depth(R->Rchild);
	return h1 > h2 ? h1 + 1 : h2 + 1;
}

//中序遍历二叉树--非递归算法
template<class T> void BinaryTree<T>::InorderTraverseNonRecursive(void (*visit)(const T& e))
{
	stack<BTnode<T>*> S;
	S.push(m_root);
	while (!S.empty())
	{
		BTnode<T>* p = S.top();
		while (p)
		{
			p = p->Lchild;
			S.push(p); //向左走到尽头
		}
		S.pop();

		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p->data);
			S.push(p->Rchild);
		}
	}
}

//层次遍历二叉树--非递归算法
template<class T> void BinaryTree<T>::LevelTraverse(void (*visit)(const T& e))
{
	queue<BTnode<T>*> Q;
	if (m_root)
	{
		Q.push(m_root);
	}
	while (!Q.empty())
	{
		BTnode<T>* p = Q.front();
		Q.pop();
		visit(p->data);
		if (p->Lchild)
		{
			Q.push(p->Lchild);
		}
		if (p->Rchild)
		{
			Q.push(p->Rchild);
		}
	}
}

//返回左兄弟指针
template<class T> BTnode<T>* BinaryTree<T>::LeftSibling(BTnode<T>* p)
{
	BTnode<T>* father = Parent(p);
	if (father && father->Rchild == p)
	{
		return father->Lchild;
	}
	return NULL;
}

template<class T> BTnode<T>* BinaryTree<T>::RightSibling(BTnode<T>* p)
{
	BTnode<T>* father = Parent(p);
	if (father && father->Lchild == p)
	{
		return father->Rchild;
	}
	return NULL;
}

template<class T> BTnode<T>* BinaryTree<T>::_Copy(BTnode<T>* R)
{
	if (R == NULL)
	{
		return NULL;
	}
	BTnode<T>* p = new BTnode<T>;
	p->data = R->data;
	p->Lchild = _Copy(R->Lchild);
	p->Rchild = _Copy(R->Rchild);
	return p;
}

//返回二叉树中元素之为e的结点的指针
template<class T> BTnode<T>* BinaryTree<T>::_Locate(BTnode<T>* bt, const T& e)
{
	if (!bt || bt->data == e)
	{
		return bt;
	}
	BTnode<T>* p = _Locate(bt->Lchild, e);
	if (p)
	{
		return p;
	}
	p = _Locate(bt->Rchild, e);
	return p;
}

template<class T> BTnode<T>* BinaryTree<T>::_Parent(BTnode<T>* R, BTnode<T>* p)
{
	if (R == NULL || R == p)
	{
		return NULL;
	}
	if (R->Lchild == p || R->Rchild == p)
	{
		return R;
	}
    BTnode<T>* q = _Parent(R->Lchild, p);
	if (q)
	{
		return q;
	}
	q = _Parent(R->Rchild, p);
	return q;
}

template<class T> bool BinaryTree<T>::InsertChild(BTnode<T>* p, const int& LR, BinaryTree<char>& r)
{
	BTnode<T> *q,*s;
	if (p)
	{
		q = r.Root(); //取根节点
		s = _Copy(q); //对象复制
		if (LR == 0)
		{
			s->Rchild = p->Lchild;
			p->Lchild = s;
		}
		else
		{
			s->Rchild = p->Rchild;
			p->Rchild = s;
		}
		return true;
	}
	return false;
}

template<class T> void BinaryTree<T>::DeleteChild(BTnode<T>*p, int which)
{
	if (which == 0)
	{
		_Destroy(p->Lchild);
	}
	else
	{
		_Destroy(p->Rchild);
	}
}
#endif

2.3 二叉树的遍历

二叉树的遍历分为先序遍历、中序遍历和后序遍历，其区别主要在于遍历根节点的顺序。

3 线索二叉树

通过模板形式定义的结点结构为：

enum PointerTag{Link=0,Thread=1};
template<class T>
struct BiThrnode
{
	T data;
	BiThrnode<T>* Lchild;
	BiThrnode<T>* Rchild;
	PointerTag Ltag,Rtag;
};

对中序线索二叉树进行遍历的函数如下：

template<class T> void BinaryThrTree<T>::Traverse_InorderBiThrTree(void (*visit)(const T& e))
{
	BiThrnode<T>* p;
	p = m_T->lchild;
	while (p != m_T)
	{
		while (p->Ltag == Link)
		{
			p = p->Lchild;
		}
		visit(p->data);
		while (p->Rtag == Thread && p->Rchild != m_T)
		{
			p = p->Rchild;
			visit(p->data);
		}
		p = p->Rchild;
	}
}

中序线索化二叉树的两个关联函数描述如下：

template<class T>
void BinaryThrTree<T>::_InorderThreading(BinaryTree<T>* &T)
{
	BiThrnode<T>* pre;
	BiThrnode<T>* Thrt = new BiThrnode<T>;
	Thrt->Ltag = Link;
	Thrt->Rtag = Thread;
	Thrt->Rchild = Thrt;
	if (!T)
	{
		Thrt->Lchild = Thrt;
	}
	else
	{
		Thrt->Lchild = T;
		pre = Thrt;
		_Threading(T,pre);
		pre->Rchild = Thrt;
		pre->Rtag = Thread;
		Thrt->Rchild = pre;
	}
	T = Thrt;
}

template<class T> 
void BinaryThrTree<T>::_Threading(BiThrnode<T>* &p, BiThrnode<T>* &pre)
{
	if (p)
	{
		_Threading(p->Lchild, pre);
		if (!p->Lchild)
		{
			p->Ltag = Thread;
			p->Lchild = pre;
		}
		if (!pre->Rchild)
		{
			pre->Rtag = Thread;
			pre->Rchild = p;
		}
		pre = p;
		_Threading(p->Rchild, pre);
	}
}

数据结构——二叉树

1 基本定义

2 二叉树的存储结构

2.1 二叉树的顺序存储结构

2.2 二叉树的链式存储结构

2.2.1 分类

2.2.2 二叉链表类的定义

2.3 二叉树的遍历

3 线索二叉树

热门文章

最新文章

相关课程

相关电子书