数据结构(十四)——二叉树-创新互联
数据结构(十四)——二叉树
一、二叉树简介
1、二叉树简介
二叉树是由n(n>=0)个结点组成的有序集合,集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的五种形态:
2、二叉树的存储结构模型
树的另一种表示法:孩子兄弟表示法
A、每个结点都有一个指向其第一个孩子的指针
B、每个结点都有一个指向其第一个右兄弟的指针
孩子兄弟表示法的特性:
A、能够表示任意的树形结构
B、每个结点包含一个数据成员和两个指针成员
C、孩子结点指针和兄弟结点指针构成树杈
3、满二叉树
如果二叉树中所有分支结点的度数都为2,并且叶子结点都在统一层次上,则二叉树为满二叉树。
4、完全二叉树
如果一棵具有n个结点的高度为k的二叉树,树的每个结点都与高度为k的满二叉树中编号为1——n的结点一一对应,则二叉树为完全二叉树。
完全二叉树的特性:
A、同样结点数的二叉树,完全二叉树的高度最小
B、完全二叉树的叶子结点仅出现在最下边两层,并且最底层的叶子结点一定出现在左边,倒数第二层的叶子结点一定出现在右边。
C、完全二叉树中度为1的结点只有左孩子。
5、二叉树的特性
A、在二叉树的第i层上最多有2^(i-1)个结点(i>=1)。
B、高度为k的二叉树,最多有2^k-1个结点(k>=0)。
C、对任何一棵二叉树,如果其叶结点有n个,度为2的非叶子结点有m个,则
n = m + 1。
D、具有n个结点的完全二叉树的高度为logn + 1
E、对于有n个结点的完全二叉树,按层次对结点进行编号(从上到下,从左到右),对于任意编号为i的结点:
二、二叉树的操作
1、二叉树的存储结构实现
二叉树结点包含四个固定的成员:结点的数据域、指向父结点的指针域、指向左子结点的指针域、指向右子结点的指针域。结点的数据域、指向父结点的指针域从TreeNode模板类继承而来。
二叉树结点的实现:
template
class BTreeNode:public TreeNode
{
public:
BTreeNode* m_left;//左子结点
BTreeNode* m_right;//右子结点
BTreeNode()
{
m_left = NULL;
m_right = NULL;
}
//工厂方法,创建堆空间的结点
static BTreeNode* NewNode()
{
BTreeNode* ret = new BTreeNode();
if(ret != NULL)
{
//堆空间的结点标识为true
ret->m_flag = true;
}
return ret;
}
};
2、二叉树的结点查找
A、基于数据元素的查找
定义基于数据元素查找的函数
virtual BTreeNode* find(BTreeNode* node, const T& value)const
{
BTreeNode* ret = NULL;
//如果根节点node
if(node != NULL)
{
if(node->value == value)
{
ret = node;
}
else
{
//查找左子树
if(ret == NULL)
{
ret = find(node->m_left, value);
}
//如果左子树没有找到,ret返回NULL,查找右子树
if(ret == NULL)
{
ret = find(node->m_right, value);
}
}
}
return ret;
}
BTreeNode* find(const T& value)const
{
return find(root(), value);
}
B、基于结点的查找
定义基于结点查找的函数
virtual BTreeNode* find(BTreeNode* node, BTreeNode* obj)const
{
BTreeNode* ret = NULL;
if(node != NULL)
{
//根节点node为目标结点
if(node == obj)
{
ret = node;
}
else
{
//查找左子树
if(ret == NULL)
{
ret = find(node->m_left, obj);
}
//如果左子树没有找到,ret返回NULL,继续查找右子树
if(ret == NULL)
{
ret = find(node->m_right, obj);
}
}
}
return ret;
}
BTreeNode* find(TreeNode* node)const
{
return find(root(), dynamic_cast*>(node));
}
3、二叉树的结点插入
根据插入的位置定义二叉树结点的位置枚举类型:
enum BTNodePos
{
Any,
Left,
Right
};
在node结点的pos位置插入newnode结点的功能函数如下:
virtual bool insert(BTreeNode* newnode, BTreeNode* node, BTNodePos pos)
{
bool ret = true;
//插入的位置为Any
if(pos == Any)
{
//如果没有左子结点,插入结点作为左子结点
if(node->m_left == NULL)
{
node->m_left = newnode;
}
//如果有左子结点,没有右子结点,插入结点作为右子结点
else if(node->m_right == NULL)
{
node->m_right = newnode;
}
//如果node结点的左右子结点不为空,插入失败
else
{
ret = false;
}
}
else if(pos == Left)
{
//如果指定插入左子结点,如果没有左子结点,插入结点
if(node->m_left == NULL)
{
node->m_left = newnode;
}
else
{
ret = false;
}
}
else if(pos == Right)
{
//如果指定插入右子结点,如果没有右子结点,插入结点
if(node->m_right == NULL)
{
node->m_right = newnode;
}
else
{
ret = false;
}
}
else
{
ret = false;
}
return ret;
}
A、插入新结点
//插入结点,无位置要求
bool insert(TreeNode* node)
{
return insert(dynamic_cast*>(node), Any);
}
//插入结点,指定插入位置
virtual bool insert(BTreeNode* node, BTNodePos pos)
{
bool ret = true;
if(node != NULL)
{
if(this->m_root == NULL)
{
node->parent = NULL;
this->m_root = node;
}
else
{
BTreeNode* np = find(node->parent);
if(np != NULL)
{
ret = insert(dynamic_cast*>(node), np, pos);
}
else
{
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
}
}
}
else
{
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
}
return ret;
}
B、插入数据元素
//插入数据,指定插入位置和父结点
virtual bool insert(const T& value, TreeNode* parent, BTNodePos pos)
{
bool ret = true;
BTreeNode* node = BTreeNode::NewNode();
if(node != NULL)
{
node->parent = parent;
node->value = value;
ret = insert(node, pos);
if(!ret)
{
delete node;
}
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
return ret;
}
//插入数据,指定父结点
bool insert(const T& value, TreeNode* parent)
{
return insert(value, parent, Any);
}
4、二叉树的结点删除
删除功能函数的定义:
virtual void remove(BTreeNode* node, BTree* ret)
{
ret = new BTree();
if(ret == NULL)
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
else
{
if(node == root())
{
this->m_root = NULL;
}
else
{
BTreeNode* parent = dynamic_cast*>(node->parent);
if(parent->m_left == node)
{
parent->m_left = NULL;
}
else if(parent->m_right == node)
{
parent->m_right = NULL;
}
node->parent = NULL;
}
ret->m_root = node;
}
}
A、基于数据元素值删除
//根据数据元素删除结点
SharedPointer< Tree > remove(const T& value)
{
BTree* ret = NULL;
BTreeNode* node = find(value);
if(node == NULL)
{
THROW_EXCEPTION(InvalidParameterException, "No value...");
}
else
{
remove(node, ret);
}
return ret;
}
B、基于结点删除
//根据结点删除结点
SharedPointer< Tree > remove(TreeNode* node)
{
BTree* ret = NULL;
node = find(node);
if(node != NULL)
{
remove(dynamic_cast*>(node), ret);
}
else
{
THROW_EXCEPTION(InvalidParameterException, "No node...");
}
return ret;
}
5、二叉树的清空
将二叉树中所有在堆空间分配的结点销毁。
清除node结点为根节点的二叉树的功能函数:
virtual void free(BTreeNode* node)
{
if(node != NULL)
{
free(node->m_left);
free(node->m_right);
}
//如果结点在堆空间分配
if(node->flag())
{
delete node;
}
}
//清空树
void clear()
{
free(root());
this->m_root = NULL;
}
6、二叉树的属性操作
A、树中结点的数量
定义计算某个结点为根结点的树的结点的数量
int count(BTreeNode* node) const
{
int ret = 0;
if(node != NULL)
{
ret = count(node->m_left) + count(node->m_right) + 1;
}
return ret;
}
//树的结点数目访问函数
int count()const
{
return count(root());
}
B、树的高度
获取node结点为根结点的二叉树的高度的功能函数:
int height(BTreeNode* node) const
{
int ret = 0;
if(node != NULL)
{
int l = height(node->m_left);
int r = height(node->m_right);
ret = ((l > r)?l:r) + 1;
}
return ret;
}
//树的高度访问函数
int height()const
{
return height(root());
}
C、树的度
获取node为根结点的二叉树的度的功能函数:
int degree(BTreeNode* node) const
{
int ret = 0;
if(node != NULL)
{
//根结点的度数
ret = (!!node->m_left + !!node->m_right);
//左子树的度
if(ret < 2)
{
int l = degree(node->m_left);
if(ret < l)
{
ret = l;
}
}
//右子树的度数
if(ret < 2)
{
int r = degree(node->m_left);
if(ret < r)
{
ret = r;
}
}
}
return ret;
}
//树的度访问函数
int degree()const
{
return degree(root());
}
7、二叉树的层次遍历
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问依次,且仅被访问一次。
根据游标思想,提供一组遍历的先关函数,按层次访问二叉树中的数据元素。
引入一个队列,辅助遍历二叉树。
LinkedQueue
层次遍历的过程如下:
//将根结点压入队列
bool begin()
{
bool ret = (root() != NULL);
if(ret)
{
//清空队列
m_queue.clear();
//根节点加入队列
m_queue.add(root());
}
return ret;
}
//判断队列是否为空
bool end()
{
return (m_queue.length() == 0);
}
//队头元素弹出,将队头元素的孩子压入队列中
bool next()
{
bool ret = (m_queue.length() > 0);
if(ret)
{
BTreeNode* node = m_queue.front();
m_queue.remove();//队头元素出队
//将队头元素的子结点入队
if(node->m_left != NULL)
{
m_queue.add(node->m_left);
}
if(node->m_right != NULL)
{
m_queue.add(node->m_right);
}
}
return ret;
}
//访问队头元素指向的数据元素
T current()
{
if(!end())
{
return m_queue.front()->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current Node...");
}
}
8、二叉树的克隆
定义克隆node结点为根结点的二叉树的功能函数:
BTreeNode* clone(BTreeNode* node)
{
BTreeNode * ret = NULL;
if(node != NULL)
{
ret = BTreeNode::NewNode();
if(ret != NULL)
{
ret->value = node->value;
//左子树
ret->m_left = clone(node->m_left);
//右子树
ret->m_right = clone(node->m_right);
//如果左子树不为空,设置左子树的父结点
if(ret->m_left != NULL)
{
ret->m_left->parent = ret;
}
//如果右子树不为空,设置右子树父结点
if(ret->m_right != NULL)
{
ret->m_right->parent = ret;
}
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
}
return ret;
}
SharedPointer> clone()const
{
BTree* ret = new BTree();
if(ret != NULL)
{
ret->m_root = clone(root());
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
return ret;
}
9、二叉树的比较
判断两棵二叉树中的数据元素是否对应相等
定义二叉树相等比较的功能函数:
bool equal(BTreeNode* l, BTreeNode* r)const
{
bool ret = true;
//二叉树自比较
if(l == r)
{
ret = true;
}
//两棵二叉树都不为空
else if(l != NULL && r != NULL)
{
ret = (l->value == r->value) && (equal(l->m_left, r->m_left)) && (l->m_right, r->m_right);
}
//有一棵二叉树为空,一棵二叉树不为空
else
{
ret = false;
}
return ret;
}
bool operator ==(const BTree& tree)const
{
return equal(root(), tree.root());
}
bool operator !=(const BTree& tree)const
{
return !(*this == tree);//使用==比较
}
10、二叉树的相加
将当前二叉树与参数btree二叉树中对应的数据元素相加,返回一棵在堆空间创建的新的二叉树。
二叉树相加实例如下:
定义将两棵二叉树相加的功能函数:
BTreeNode* add(BTreeNode* l, BTreeNode* r)const
{
BTreeNode* ret = NULL;
//二叉树l为空
if(l == NULL && r != NULL)
{
ret = clone(r);
}
//二叉树r为空
else if(l != NULL && r == NULL)
{
ret = clone(l);
}
//二叉树l和二叉树r不为空
else if(l != NULL && r != NULL)
{
ret = BTreeNode::NewNode();
if(ret != NULL)
{
//根节点数据元素相加
ret->value = l->value + r->value;
//左子树相加
ret->m_left = add(l->m_left, r->m_left);
//右子树相加
ret->m_right = add(l->m_right, r->m_right);
//左子树不为空,设置左子树的父结点为当前结点
if(ret->m_left != NULL)
{
ret->m_left->parent = ret;
}
//右子树不为空,设置右子树的父结点为当前结点
if(ret->m_right != NULL)
{
ret->m_right->parent = ret;
}
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
}
return ret;
}
SharedPointer> add(const BTree& other)const
{
BTree* ret = new BTree();
if(ret != NULL)
{
ret->m_root = add(root(), other.root());
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memoty...");
}
return ret;
}
三、二叉树的典型遍历方式
二叉树有先序、中序、后序三种遍历方式,三种遍历方法的不同主要是取决于根节点的遍历顺序。
1、前序遍历
如果二叉树为空,则无操作,直接返回。
如果二叉树非空,则执行以下操作:
A、访问根结点;
B、先序遍历左子树;
C、先序遍历右子树。
先序遍历实现代码:
void preOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
if(node != NULL)
{
queue.add(node);
preOrderTraversal(node->m_left, queue);
preOrderTraversal(node->m_right, queue);
}
}
先序遍历二叉树示例:
2、中序遍历
如果二叉树为空,则无操作,直接返回。
如果二叉树非空,则执行以下操作:
A、中序遍历左子树;
B、访问根结点;
C、中序遍历右子树。
中序遍历实现代码:
void inOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
if(node != NULL)
{
inOrderTraversal(node->m_left, queue);
queue.add(node);
inOrderTraversal(node->m_right, queue);
}
}
中序遍历二叉树示例:
3、后序遍历
如果二叉树为空,则无操作,直接返回。
如果二叉树非空,则执行以下操作:
A、后序遍历左子树;
B、后序遍历右子树;
C、访问根结点。
后序遍历实现代码:
void postOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
if(node != NULL)
{
postOrderTraversal(node->m_left, queue);
postOrderTraversal(node->m_right, queue);
queue.add(node);
}
}
后序遍历二叉树示例:
4、遍历算法的封装
定义遍历方式的枚举类型:
enum BTTraversal
{
PreOder,
InOder,
PostOder
};
根据参数order选择遍历的方式,返回数组保存了二叉树遍历结点
SharedPointer> traversal(BTTraversal order)
{
DynamicArray* ret = NULL;
LinkedQueue*> queue;//保存遍历二叉树的结点
switch (order)
{
case PreOder:
preOrderTraversal(root(), queue);
break;
case InOder:
inOrderTraversal(root(), queue);
break;
case PostOder:
postOrderTraversal(root(), queue);
break;
default:
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
break;
}
ret = new DynamicArray(queue.length());
if(ret != NULL)
{
for(int i = 0; i < ret->length(); i++, queue.remove())
{
ret->set(i, queue.front()->value);
}
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
return ret;
}
四、线索化二叉树
1、线索化二叉树简介
线索化二叉树是将二叉树转换为双向链表的过程(将非线性的二叉树转换为线性的链表)。
二叉树的线索化能够反映某种二叉树的遍历次序(结点的先后访问次序)。
线索化二叉树的过程:
二叉树线索化的实现:
通过某种遍历方式遍历二叉树,根据遍历次序将二叉树结点依次存储到辅助队列中,最后将辅助队列中保存的结点依次出队并连接(连接时,原二叉树结点的m_left指针作为双向链表结点的m_prev指针,指向结点的前驱;原二叉树结点的m_right结点作为双向链表结点的m_next指针,指向结点的后继),成为双向链表。
void traversal(BTTraversal order, LinkedQueue*>& queue)
{
switch (order)
{
case PreOrder:
preOrderTraversal(root(), queue);
break;
case InOrder:
inOrderTraversal(root(), queue);
break;
case PostOrder:
postOrderTraversal(root(), queue);
break;
case LevelOrder:
levelOrderTraversal(root(), queue);
break;
default:
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
break;
}
}
2、层次遍历算法
增加层次遍历方式LevelOrder到遍历方式枚举类型中。
enum BTTraversal
{
PreOrder,//先序遍历
InOrder,//中序遍历
PostOrder,//后序遍历
LevelOrder//层次遍历
};
层次遍历算法:
A、将根结点入队
B、访问队头元素指向的二叉树结点
C、将队头元素出队,队头元素的孩子入队
D、判断队列是否为空,如果非空,继续B;如果为空,结束。
层次遍历二叉树的实例如下:
//层次遍历
void levelOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
if(node != NULL)
{
//辅助队列
LinkedQueue*> temp;
//根结点压入队列
temp.add(node);
while(temp.length() > 0)
{
BTreeNode* n = temp.front();
//如果左孩子不为空,将左孩子结点入队
if(n->m_left != NULL)
{
temp.add(n->m_left);
}
//如果右孩子不为空,将右孩子结点入队
if(n->m_right != NULL)
{
temp.add(n->m_right);
}
//将队列的队头元素出队
temp.remove();
//将队列的队头元素入队输出队列
queue.add(n);
}
}
}
3、队列中结点的连接
将队列中的所有结点连接成为一个线性的双向链表
void connect(LinkedQueue*>& queue)
{
BTreeNode* ret = NULL;
if(queue.length() > 0)
{
//返回队列的队头元素指向的结点作为双向链表的首结点
ret = queue.front();
//双向链表的首结点的前驱设置为空
ret->m_left = NULL;
//创建一个游标结点,指向队列队头
BTreeNode* slider = queue.front();
//将队头元素出队
queue.remove();
while(queue.length() > 0)
{
//当前游标结点的后继指向队头元素
slider->m_right = queue.front();
//当前队头元素的前驱指向当前游标结点
queue.front()->m_left = slider;
//将当前游标结点移动到队头元素
slider = queue.front();
//将当前队头元素出队,继续处理新的队头元素
queue.remove();
}
//双向链表的尾结点的后继为空
slider->m_right = NULL;
}
}
4、线索化二叉树的实现
线索化二叉树函数接口的设计:
BTreeNode
A、根据参数order选择线索化的方式(先序、中序、后序、层次)
B、返回值是线索化二叉树后指向链表首结点的指针
C、线索化二叉树后,原有的二叉树被破坏,二叉树的所有结点根据遍历次序组建为一个线性的双向链表,对应的二叉树应为空。
线索化二叉树的流程:
BTreeNode* thread(BTTraversal order)
{
BTreeNode* ret = NULL;
LinkedQueue*>* queue;
//遍历二叉树,并按遍历次序将结点保存到队列
traversal(order, queue);
//连接队列中的结点成为双向链表
ret = connect(queue);
//将二叉树的根节点置空
this->m_root = NULL;
//将游标遍历的辅助队列清空
m_queue.clear();
//返回双向链表的首结点
return ret;
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:数据结构(十四)——二叉树-创新互联
浏览地址:http://scyanting.com/article/dojogj.html