数据结构——二叉树

简介:

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);
	}
}


转载:http://blog.csdn.net/foreverling/article/details/43229285

目录
相关文章
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
107 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
26 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
28 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
28 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
26 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解