树：层次关系
Tree ：n个节点构成的有限集合；
n=0时；称为空树；
对于非空树，具备特质有：
- 树中有一个根的特殊节点，用r解释；
- 子树；
树与非树？ - 子树是不想交的；
- 除了根节点外，每个结点点有且仅有一个父节点；
- 一棵N个结点的树有N-1条边；
基本术语
1、 结点的度 结点的子树个数
2、树的度：树的所有结点最大的度数
3、叶结点：度为1的结点；
4、父节点：有子树的结点是其子树的根节点的父节点
5、子节点；
6、兄弟结点：同一父节点的各结点是彼此的兄弟结点；
7、路径和路径长度；
8、祖先结点；
9、子孙节点；
11、结点的层次；
12、树的深度；
实现方法
image.png
二叉树：度为2；
特殊二叉树
- 斜二叉树
- 完美二叉树/满二叉树
- 完全二叉树（不完整）
重要性质
二叉树第i层最大结点 2^（n-1）
深度为k的二叉树最大结点总数为2^n-1
非空二叉树 n0为叶节点的个数 n2为度为2的非叶节点个数 满足n0=n2+1；
常用的遍历方法：
先序--根，左子树，右子树
中序--左子树，根，右子树
后续--左子树，右子树，根
层次遍历--从上到下，从左到右
二叉树的存储结构
顺序存储结构
-完全二叉树
：从上到下、从左到右顺序存储n个节点的完全二叉树的节点父子关系。
- 父根节点 父节点[i/2]
- 左孩子节点 2i
- 右孩子节点2i+1
一般二叉树也可以采取这种结构，但会造成空间浪费。
链表存储
template <typename DataType>
struct TreeNode
{
DataType data; //存储的数据
TreeNode *left; //指向左子树根节点
TreeNode *right; //指向右子树根节点
//TreeNode * parent; //指向父节点，如果需要的话
TreeNode(DataType inData): data(inData), right(nullptr), left(nullptr) {}
};
image.png
遍历
//遍历
//先序遍历
template <typename DataType>
void Traverse(TreeNode<DataType> * inNode){
if (inNode == nullptr){
return;
}
//cout<<inNode->data<<endl;//如果在这里访问即为先序访问
Traverse(inNode->left);
//cout<<inNode->data<<endl;//如果在这里访问即为中序访问
Traverse(inNode->right);
//cout<<inNode->data<<endl;//如果在这里访问即为后序访问
return；
}
二叉树的非递归算法
先序遍历的非递归：使用堆栈
template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
stack<TreeNode<DataType>*> nodeStack;
TreeNode<DataType> *cycleNode = inNode;
while(inNode != nullptr||!nodeStack.empty()){
//不断访问某一节点的左子节点并压栈知道最左子节点
while(cycleNode != nullptr){
//遇到节点先输出
cout<<cycleNode->data<<endl;
nodeStack.push(cycleNode);
cycleNode = cycleNode->left;
}
//此时所有的左子树都压入栈中
//弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
if（！inNode.empty()）{
cycleNode = nodeStack.top();
cycleNode = cycleNode->right;
nodeStack.pop();
}
}
}
中序遍历：先访问左子节点，在访问根节点，再访问右子节点。
template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> * inNode){
stack<TreeNode<DataType>*> nodeStack;
TreeNode<DataType> *cycleNode = inNode;
while(inNode != nullptr||!nodeStack.empty()){
//不断访问某一节点的左子节点并压栈知道最左子节点
while(cycleNode != nullptr){
nodeStack.push(cycleNode);
cycleNode = cycleNode->left;
}
//此时所有的左子树都压入栈中
//弹出最后一个节点 访问该节点的右子节点并作为下一步作为下一轮遍历节点
if（！inNode.empty()）{
cycleNode = nodeStack.top();
//在此处访问即为中序遍历，时机为压入右子节点之前
//cout << cycleNode->data << endl;
cycleNode = cycleNode->right;
nodeStack.pop();
}
}
}
由于辅助压栈，我们并没有将null压入栈中，如果发现左子节点为null则在保存右子节点地址后直接弹出该节点，并使用右子节点作为下一论访问起始节点，如果右子节点为null则表示该节点左右子树均遍历完毕，则继续弹出直至出现第一个右子树不为空的节点，重复递归。
压栈图中，在前序遍历时，只要遇到节点（压栈过程）就直接输出就可以保证根节点首先被输出，而中序遍历由于需要在左子树输出完毕后才能输出，因此只要保证在压栈返回时（出栈时）且准备遍历右子树时输出即可。
后序遍历 非递归实现
template <typename DataType>
void NonRecursiveTraverse(TreeNode<DataType> *inNode){
stack<TreeNode<DataType> *>nodeStack;
TreeNode<DataType> *cycleNode = inNode;
TreeNode<DataType> *hasNode = nullptr;
while(inNode != nullptr || !nodeStack.empty()){
//不断访问某一节点的左子节点并压栈直到最左子节点
while(cycleNode != nullptr){
nodeStack.push(cycleNode);
cycleNode = cycleNode->left;
}
//此时所有的子节点都已经压入栈中。
//弹出最后一个节点，访问该节点的右子节点并作为下一轮遍历根节点
if(!nodeStack.empty()){
cycleNode = nodeStack.top();
//此时判别是否已经加载右子树
//如果为空则和中序遍历一样
if(cycleNode->right == nullptr){
hascycle = cycleNode;
cout<< cycleNode->data<<endl;
nodeStack.pop();
}
else if(hascycle == cycleNOde->right){
hascycle = cycleNode;
cout<<cycleNode->data<<endl;
nodeStack.pop();
}
cycleNode = nullptr;
if(!nodeStack.empty() && ndoeStack.top->right!=nullptr)) {
cycleNode = nodeStack.top()->right;
}
}
}
}
层序遍历
二叉树遍历的核心问题：二维结构的线性化
- 从节点访问其左、右儿子
- 需要一个存储结构保存暂时不访问的结点
- 存储结构：堆栈、队列
队列实现：遍历从根节点开始，首先将根节点入队，然后开始执行循环：结点出队，访问该结点，将左右儿子入队
void LevelOrderTraversal ( BinTree BT){
Queue Q;BinTree T;
//如果是空树直接返回
if(!BT)
return ;
//创建并初始化队列Q
Q = CreatQueue(Maxsize);
AddQ(Q,BT);
while( !IsEmptyQ(Q)){
T = DeleteQ(Q);
cout <<T->data<<endl;
if(T->left)
AddQ(Q,T->left);
if(T->right)
AddQ(Q,T->right)
}
}
如果有两个遍历序列确定二叉树
必须要有中序遍历
如果已知先序和中序；
- 根据先序遍历序列第一个节点确定根节点；
- 根绝根节点在中序遍历序列中分割出左右两个子序列
- 对左子树和右子树分别递归分为左子树和右子树
二叉查找树的定义与实现
静态查找：二分查找
动态查找：二叉搜索树；
也称为二叉排序树，或者二叉查找树；
- 分空左子树的所有键值小于其根节点的键值。
- 分空右子树的所有键值大于其根节点的键值。
- 左右子树都是二叉搜索树。
对于二叉树ADT，一般需要提供以下操作：
- 清空二叉查找树：MakeEmpty
- 查找某个节点：Find
- 删除某个节点：DeleteElement
- 查找最大值：FindMax
- 查找最小值：FindMin
- 插入一个节点：InsertElement
二叉查找树的平均深度为O(log(N))，不过如果插入元素序列递增或者递减，二叉查找树将退化成单链表。
二叉查找树的实现
二叉树的基本结构定义：
template <typename DataType>
struct Node
{
DataType data;
Node *left;
Node *right;
Node(DataType inData): data(inData), left(nullptr), right(nullptr) {}
};
template <typename DataType>
class BinarySearchTree
{
public:
BinarySearchTree(): root(nullptr) {}
~BinarySearchTree();
void MakeEmpty(); //清空二叉查找树
void MakeEmptyNon(); //非递归清空二叉树
Node<DataType> * Find(DataType inElement); //查找某个元素
Node<DataType> * FindNon(DataType inElement); //非递归查找
void DeleteElement(DataType inElement); //删除一个节点
Node<DataType> * FindMax(); //查找最大元素
Node<DataType> * FindMaxNon(); //非递归查找最大元素
Node<DataType> * FindMin(); //查找最小元素
Node<DataType> * FindMinNon(); //非递归查找最小元素
Node<DataType> * InsertElementNon(DataType inElement); //非递归插入一个元素
private:
void MakeEmptyCore(Node<DataType> *inNode);
Node<DataType> *FindCore(Node<DataType> *inNode, DataType inElement);
//删除一个节点
Node<DataType> * DeleteElementCore(Node<DataType> *inNode, DataType inElement);
Node<DataType> *FindMaxCore(Node<DataType> *inNode);
Node<DataType> *FindMinCore(Node<DataType> *inNode);
Node<DataType> *root;
};
二叉查找树的基本数据成员为
递归清空核心函数：
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
if (inNode == nullptr) {
return;
}
MakeEmptyCore(inNode->left);
MakeEmptyCore(inNode->right);
delete inNode;
}
递归清空核心函数
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyCore(Node<DataType> *inNode)
{
if (inNode == nullptr) {
return;
}
MakeEmptyCore(inNode->left);
MakeEmptyCore(inNode->right);
delete inNode;
}
递归清空入口函数，调用清空核心函数
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmpty()
{
MakeEmptyCore(root); root = nullptr;
}
非递归清空函数，采用某种非递归遍历函数思想即可
template <typename DataType>
void BinarySearchTree<DataType>::MakeEmptyNon()
{
stack<Node<DataType> *> nodeStack;
Node<DataType> *cycleIter = root;
while (cycleIter != nullptr || !nodeStack.empty()) {
while (cycleIter != nullptr) {
nodeStack.push(cycleIter);
cycleIter = cycleIter->left;
}
if (!nodeStack.empty()) {
Node<DataType> * tmp = nodeStack.top();
cycleIter = tmp->right;
delete tmp; nodeStack.pop();
}
}
root = nullptr;
}
递归查找某个元素
template <typename DataType>
Node<DataType> *BinarySearchTree<DataType>::FindCore(Node<DataType> *inNode, DataType inElement)
{
if (inNode == nullptr) {
return nullptr;
}
if (inNode->data == inElement) {
return inNode;
}
else if (inNode->data > inElement){
return FindCore(inNode->left, inElement);
}
else {
return FindCore(inNode->right, inElement);
}
return nullptr;
}
非递归查找
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindNon(DataType inElement)
{
Node<DataType> *cycleIter = root;
while (cycleIter != nullptr) {
if (cycleIter->data == inElement) {
return cycleIter;
}
else if (cycleIter->data > inElement){
cycleIter = cycleIter->left;
}
else {
cycleIter = cycleIter->right;
}
}
return nullptr;
}
递归删除节点函数核心函数
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
if (inNode == nullptr) {
return nullptr;
}
else if (inNode->data > inElement) {
inNode->left = DeleteElementCore(inNode->left, inElement);
}
else if (inNode->data < inElement) {
inNode->right = DeleteElementCore(inNode->right, inElement);
}
else {
if (inNode->left != nullptr && inNode->right != nullptr) {
Node<DataType> *tmp = FindMinCore(inNode->right);
inNode->data = tmp->data;
inNode->right = DeleteElementCore(inNode->right, inNode->data);
}
else {
Node<DataType> *tmp = inNode;
if (inNode->left == nullptr) {
inNode = inNode->right;
}
else {
inNode = inNode->left;
}
delete tmp;
}
}
return inNode;
}
递归查找最大元素核心函数
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxCore(Node<DataType> *inNode)
{
if (inNode == nullptr) {
return nullptr;
}
else if (inNode->right == nullptr) {
return inNode;
}
else {
return FindMaxCore(inNode->right);
}
}
递归查找最大元素
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMax()
{
if (root == nullptr) {
return nullptr;
}
return FindMaxCore(root);
}
非递归查找最大元素
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::FindMaxNon()
{
if (root == nullptr) {
return nullptr;
}
Node<DataType> *pre = root;
Node<DataType> *cycleIter = pre->right;
while (cycleIter != nullptr) {
pre = cycleIter;
cycleIter = pre->right;
}
return pre;
}
递归删除节点函数核心元素
template <typename DataType>
Node<DataType> * BinarySearchTree<DataType>::DeleteElementCore(Node<DataType> *inNode, DataType inElement)
{
if (inNode == nullptr) {
return nullptr;
}
else if (inNode->data > inElement) {
inNode->left = DeleteElementCore(inNode->left, inElement);
}
else if (inNode->data < inElement) {
inNode->right = DeleteElementCore(inNode->right, inElement);
}
else {
if (inNode->left != nullptr && inNode->right != nullptr) {
Node<DataType> *tmp = FindMinCore(inNode->right);
inNode->data = tmp->data;
inNode->right = DeleteElementCore(inNode->right, inNode->data);
}
else {
Node<DataType> *tmp = inNode;
if (inNode->left == nullptr) {
inNode = inNode->right;
}
else {
inNode = inNode->left;
}
delete tmp;
}
}
return inNode;
}
