二叉树
二叉树:二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子
满二叉树:高度为N的满二叉树有2^N - 1个节点的二叉树。
完全二叉树: 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树
二叉树的存储结构
数组表示存储
链表存储表示:
数组表示法用于完全二叉树的存储非常有效,但表示一般的二叉树则不是很理想。此外,在一棵树中进行插入和删除时,为了反映节点的层次变化,可能需要移动许多节点,降低了算法效率,二使用连接表示,可以克服这些缺点。
根据二叉树的定义,可以设计出二叉树的节点结构。二叉树的每一个节点有三个域:数据域_data,左子女节点指针_leftChild,右子女节点指针_rightChild。这中链表称为二叉链表。使用这种结构,可以很方便的根据左右孩子指针找到他的左右孩子。但要找到他的双亲很难。为了找到双亲节点,可以在节点中在增加一个双亲指针域_parent,他被称为三叉链表结构。
楼主主要实现的是二叉链表结构
节点的定义
//节点结构
template<class T>
struct BinaryTreeNode
{
//构造函数
BinaryTreeNode(const T& data)
:_data(data)
,_leftChild(NULL)
,_rightChild(NULL)
{}
public:
T _data;//数据域
BinaryTreeNode* _leftChild;//左孩子指针
BinaryTreeNode* _rightChild;//右孩子指针
};
二叉树的实现
//二叉树类
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
//构造函数
BinaryTree(const T* a, size_t size, const T& invalid)
{
assert(a);
size_t index = 0;
_root = _CreateTree(a, size, invalid,index);
}
//拷贝构造
BinaryTree(const BinaryTree<T>& t)
{
_root = _Copy(t._root);
}
//赋值运算符的重载
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(_root, t._root);
return *this;
}
//析构函数
~BinaryTree()
{
_Destory(_root);
}
public:
//前序遍历
void PrevOrder()
{
_PrevOrder(_root);
cout << endl;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//后序遍历
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
//层次遍历
void LevelOrder()
{
_LevelOrder(_root);
cout << endl;
}
//求二叉树的节点个数
size_t Size()
{
return _Size(_root);
}
//求二叉树的深度
size_t Depth()
{
return _Depth(_root);
}
//求二叉树的叶子节点的个数
size_t LeafSize()
{
return _LeafSize(_root);
}
protected:
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
//index要传引用,需要更改index的值
{
Node* root = NULL;
//判断数组是否越界和输入的值是否合法
if (index < size&&a[index] != invalid)
{
root = new Node(a[index]);//创建根节点
root->_leftChild = _CreateTree(a, size, invalid, ++index);//递归创建左子树
root->_rightChild = _CreateTree(a, size, invalid, ++index);//递归创建右子树
}
return root;//返回根节点
}
void _PrevOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
cout << root->_data << " ";//访问根节点
_PrevOrder(root->_leftChild);//递归访问左子树
_PrevOrder(root->_rightChild);//递归访问右子树
}
void _InOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
_InOrder(root->_leftChild);//访问左子树
cout << root->_data << " ";//递归访问根节点
_InOrder(root->_rightChild);//递归访问右子树
}
void _PostOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
_PostOrder(root->_leftChild);//访问左子树
_PostOrder(root->_rightChild);//递归访问右子树
cout << root->_data << " ";//递归访问根节点
}
//层次遍历
void _LevelOrder(Node* root)
{
if (root == NULL)
{
return;
}
queue<Node*> q;
q.push(root);//根节点入队
while (!q.empty())//当队列不为空
{
if (q.front()->_leftChild)
{
q.push(q.front()->_leftChild);
}
if (q.front()->_rightChild)
{
q.push(q.front()->_rightChild);
}
cout << q.front()->_data << " ";
q.pop();
}
}
size_t _Size(Node* root)
{
size_t count = 0;
if (root == NULL)
{
return count;//树为空
}
count++;//根节点
count += _Size(root->_leftChild);//计算左子树大小
count+= _Size(root->_rightChild);//计算右子树大小
return count;
}
//返回左右子树深度较大的
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_leftChild);
size_t RightDepth= _Depth(root->_rightChild);
if (LeftDepth > RightDepth)
{
return ++LeftDepth;
}
else
{
return ++RightDepth;
}
}
size_t _LeafSize(Node*root)
{
if (root == NULL)
{
return 0;
}
if (root->_leftChild == NULL && root->_rightChild == NULL)
{
return 1;
}
return _LeafSize(root->_leftChild)+ _LeafSize(root->_rightChild);
}
Node* _Copy(Node* root)
{
if (root == NULL)
{
return NULL;
}
Node* newRoot = new Node(root->_data);
newRoot->_leftChild = _Copy(root->_leftChild);
newRoot->_rightChild = _Copy(root->_rightChild);
return newRoot;
}
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
//删除叶结点
if (root->_leftChild == NULL&&root->_rightChild == NULL)
{
delete root;
root = NULL;
return;
}
_Destory(root->_leftChild);//递归删除左子树
_Destory(root->_rightChild);//递归删除右子树
delete root;
}
private:
BinaryTreeNode<T>* _root;//根节点
};
测试代码
#include"BinaryTree.h"
void TestBinary()
{
/*int a1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };
BinaryTree<int> t1(a1, 10, '#');
cout << "先序遍历:";
t1.PrevOrder();
cout << "中序遍历:";
t1.InOrder();
cout << "后序遍历:";
t1.PostOrder();
cout << "层次遍历:";
t1.LevelOrder();
cout << "size:" << t1.Size() << endl;
cout << "depth:" << t1.Depth() << endl;
cout << "leafSize:" << t1.LeafSize() << endl;*/
int a2[15] = { 1,2,'#',3,'#','#',4,5,'#',6 ,'#' ,7,'#' ,'#' ,8 };
int a[] = { 1,2,'#','#',3 };
BinaryTree<int> t1(a, 5, '#');
BinaryTree<int> t2;
t2 = t1;
cout << "先序遍历:";
t2.PrevOrder();
cout << "中序遍历:";
t2.InOrder();
cout << "后序遍历:";
t2.PostOrder();
cout << "层次遍历:";
t2.LevelOrder();
cout << "size:" << t2.Size() << endl;
cout << "depth:" << t2.Depth() << endl;
cout << "leafSize:" << t2.LeafSize() << endl;
}
int main()
{
TestBinary();
getchar();
return 0;
}
测试结果
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。