大师兄的数据结构学习笔记(四）:树结构
大师兄的数据结构学习笔记(六）:树的应用
一、什么是二叉树(Binary Tree)
1. 二叉树的定义
- 二叉树
是一个有穷的结点集合，这个集合可以为空。
- 若不为空，则它由根结点和左子树
和右子树
的两个不相交的二叉树组成。
- 可以将二叉树理解为一个有左右之分的度为二的树。
2. 二叉树的五种基本形态
1) 空二叉树(什么都没有,nothing)
2) 只有一个根结点的二叉树(左右子树为空)
3) 右子树为空的二叉树(右腿断了)
4) 左子树为空的二叉树(左腿断了)
5) 左右子树都非空的的二叉树(既有左子树又有右子树,)
3. 特殊二叉树
1) 斜二叉树(Skewed Binary Tree)
- 所有的子树都是左子树或右子树。
相当于链表。
2) 完全二叉树(Full Binary Tree)
- 除了叶结点，每个结点都有两个子树。
叶结点都靠左对齐。
3) 完美二叉树(Perfect Binary Tree)
- 除了叶结点，每个结点都有两个子树。
叶结点全在同一层。
4. 二叉树的重要性质
- 二叉树第
层的最大结点数为
。
- 深度为
的二叉树的最大结点总数为
。
- 任何非空二叉树
表示叶结点的个数、
是度为2的非叶结点个数，那么两者满足关系
。
二、实现二叉树
1. 二叉树的抽象数据类型
- 操作集:
- 重要操作:
1)
Boolean IsEmpty(BinTree BT)判别BT是否为空。
2)void Traversal(BinTree BT)按顺序遍历每个结点。
3)BinTree CreatBinTree()创建二叉树。
2. 二叉树的遍历方法
| 名称 | 顺序 |
|---|---|
| 先序(Pre Order Traversal) | 根->左子树->右子树 |
| 中序(In Order Traversal) | 左子树->根->右子树 |
| 后序(Post Order Traversal) | 左子树->右子树->根 |
| 层次遍历(Level Order Traversal) | 从上到下，从左到右 |
3. 二叉树的存储结构
3.1 顺序存储结构
- 完全二叉树按从上至下、从左到右的顺序存储n个结点的完全二叉树的结点父子关系。
- 非完全二叉树可以通过补充空结点的方式成为完全二叉树。
- 非根结点(序号
)的父结点的序号是
。
- 结点(序号为
(若
,否则没有左儿子)。
- 结点(序号为
(若
,否则没有左儿子)。
3.2 链表存储结构
-
用左右两个指针表示左右子树。
#ifndef BTREE_H
#define BTREE_H
template<typename T>
struct BinTreeNode
{
T data; //存储的数据
BinTreeNode<T>* leftChild, * rightChild; //左右子树
BinTreeNode() :leftChild(nullptr), rightChild(nullptr) {} //构造函数
BinTreeNode(T x, BinTreeNode<T>* l = nullptr,
BinTreeNode<T>* r = nullptr):data(x),leftChild(l),rightChild(r) {} //带参数的构造函数
};
template<typename T>
class BinaryTree
{
public:
BinaryTree() :root(nullptr) {}; //构造函数
BinaryTree(T value) :RefValue(value), root(nullptr) {}; //指定结束标识的构造函数
~BinaryTree() { Destroy(root); } //析构函数
void CreatBinTree(); //创建二叉树
bool IsEmpty(); //判断是否为空树
void PreOrder() { PreOrder(root); } //先序遍历
void InOrder() { InOrder(root); } //中序遍历
void PostOrder() { PostOrder(root); } //后序遍历
void LevelOrder() { LevelOrder(root); }; //层次遍历
private:
BinTreeNode<typename T> *root; //根节点
T RefValue; //停止信号
void PreOrder(BinTreeNode<typename T>*& subTree); //先序遍历
void InOrder(BinTreeNode<typename T>*& subTree); //中序遍历
void PostOrder(BinTreeNode<typename T>*& subTree); //后序遍历
void LevelOrder(BinTreeNode<typename T>*& subTree); //层次遍历
void Destroy(BinTreeNode<typename T>*& subTree); //销毁树
};
#endif
#include <iostream>
#include <stack>
#include <queue>
#include"BTree.h"
using namespace std;
template<typename T>
bool BinaryTree<T>::IsEmpty()
{
//判断是否为空树
if (root == nullptr)
{
return true;
}
return false;
}
template<typename T>
void BinaryTree<T>::Destroy(BinTreeNode<typename T>*& subTree)
{
// 销毁树
if (subTree != nullptr)
{
Destroy(subTree->leftChild);
Destroy(subTree->rightChild);
delete subTree;
subTree = nullptr;
}
}
template<typename T>
void BinaryTree<T>::CreatBinTree()
{
stack < BinTreeNode<T>* > S;
root = nullptr;
BinTreeNode<T>* p, * t; // p用来记住当前创建的结点，t用来记住栈顶元素
int k = 1; //左右标记
T ch;
cin >> ch;
while (ch != RefValue)
{
switch (ch)
{
case '(':
S.push(p);
k = 1;
break;
case ')':
S.pop();
break;
case ',':
k = 2;
break;
default:
p = new BinTreeNode<T>(ch);//构造结点
if (IsEmpty())
{
root = p;
}
else if (k == 1)
{
t = S.top();
t->leftChild = p;
}
else
{
t = S.top();
t->rightChild = p;
}
}
cin >> ch;
}
}
template<typename T>
void BinaryTree<T>::PreOrder(BinTreeNode<typename T>*& subTree)
{
//先序遍历
if (subTree != nullptr)
{
cout << subTree->data << " ";
PreOrder(subTree->leftChild);
PreOrder(subTree->rightChild);
}
}
template<typename T>
void BinaryTree<T>::InOrder(BinTreeNode<typename T>*& subTree)
{
//中序遍历
if (subTree != nullptr)
{
PreOrder(subTree->leftChild);
cout << subTree->data << " ";
PreOrder(subTree->rightChild);
}
}
template<typename T>
void BinaryTree<T>::PostOrder(BinTreeNode<typename T>*& subTree)
{
//中序遍历
if (subTree != nullptr)
{
PreOrder(subTree->leftChild);
PreOrder(subTree->rightChild);
cout << subTree->data << " ";
}
}
template<typename T>
void BinaryTree<T>::LevelOrder(BinTreeNode<typename T>*& subTree)
{
//层次遍历
queue<BinTreeNode<T>*> Q;
Q.push(nullptr); //空树信号
while (subTree != nullptr)
{
cout << subTree->data << " ";
Q.pop();
if (subTree->leftChild != nullptr)
{
Q.push(subTree->leftChild);
}
if (subTree->rightChild != nullptr)
{
Q.push(subTree->rightChild);
}
}
cout << endl;
}
网友评论