?
1.顺序存储
?
根节点位序为0。剩下的结点，假设位序为i，如果左孩子存在，左孩子为2i+1。
如果右孩子存在，右孩子为2i+2。其父节点都为（i-1）/2。
如果结点不存在，可以用一个数来标记。
缺点是容易造成空间浪费，一般用于完全二叉树，或者接近完全二叉树的二叉树存储。
?2.链式存储结构
链式存储有两种链表结点，一种是二叉链表结点，另一种是三叉链表结点。
二叉链表结点仅存储左右孩子的指针和该结点的数据。
而三叉链表结点多加了一个指向双亲结点的指针。
这两个结点当然也可以用于顺序存储。
仅谈二叉链表：
1.深度优先遍历?
（1）前序遍历（DLR即data、left、right）
? ? ? ? 可以看出，当该结点不为空，先遍历该结点，然后遍历左节点，再遍历右节点，最后结束。
? ? ? ? 否则返回，直到所有节点完成遍历。
（2）中序遍历（LDR）
????????可以看出，当该结点不为空，先遍历该结点的左节点，然后遍历该节点，再遍历该节点的右? ? ? ? ? ? 节点，最后结束。
? ? ? ? 否则返回，直到所有节点完成遍历。
（3）后序遍历（LRD）
????????可以看出，当该结点不为空，先遍历该结点的左节点，然后遍历该节点的右节点，然后遍历? ? ? ? ? ? 该节点，最后结束。
? ? ? ? 否则返回，直到所有节点完成遍历。
记忆的话，就是该结点遍历顺序在哪，就是什么序遍历。并且按照左节点在右节点之前的遍历。
2.广度优先遍历
????????层序遍历：
????????
? ? ? ? ?即先从上到下，从左到右，如图中数字顺序遍历。
#pragma once
#include<stack>
#include<queue>
#include<iostream>
template<class T>
class binary_tree
{
public:
struct node
{
T data;
node* left;
node* right;
node() = default;
node(const T& d, node* const l = nullptr, node* const r = nullptr)
{
data = d; left = l; right = r;
}
};
node* root;
binary_tree():root(nullptr){}
~binary_tree() { p_clear(root); }
unsigned size() { return p_size(root); }
unsigned height() { return p_height(root); }
unsigned leaf_num() { return p_leaf_num(root); }
void preorder0() { p_preorder0(root); }
void preorder1() { p_preorder1(root); }
void inorder0() { p_inorder0(root); }
void inorder1() { p_inorder1(root); }
void postorder0() { p_postorder0(root); }
void postorder1() { p_postorder1(root); }
void levelorder() { p_levelorder(root); }
private:
//名字前面有个p表示私有private
unsigned p_size(node* root);//求结点数
void p_clear(node* root);//删除所有结点
unsigned p_height(node* root);//求二叉树高度
unsigned p_leaf_num(node* root);//求二叉树叶子结点个数
//1表示递归方式，0表示非递归方式
void p_preorder0(node* root);//前序遍历
void p_preorder1(node* root);
void p_inorder0(node* root);//中序遍历
void p_inorder1(node* root);
void p_postorder0(node* root);
void p_postorder1(node* root);//后序遍历
void p_levelorder(node* root);
};
template<class T>
unsigned binary_tree<T>::p_size(node* root)
{
//如果当前结点为空，返回0
if (!root)
return 0;
//如果非空，结点数等于1（表示当前结点）+左子树结点数+右子树结点数
return 1 + p_size(root->left) + p_size(root->right);
}
template<class T>
void binary_tree<T>::p_clear(node* root)
{
if (!root)//结点为空就返回
return;
else
{
node* p = root;
p_clear(p->left);//删除左子树
p_clear(p->right);//删除右子树
delete p;//删除当前结点
}
}
template<class T>
unsigned binary_tree<T>::p_height(node* root)
{
if (!root)
return 0;
unsigned left_height = p_height(root->left);//左子树长度
unsigned right_height = p_height(root->right);//右子树长度
return 1 + (left_height >= right_height ? left_height : right_height);
}
template<class T>
unsigned binary_tree<T>::p_leaf_num(node* root)
{
//如果是叶子结点，返回1
if (!root->left&&!root->right)
return 1;
//如果不是的话，返回左子树叶子结点+右子树叶子结点
return p_leaf_num(root->left) + p_leaf_num(root->right);
}
template<class T>
void binary_tree<T>::p_preorder0(node* root)
{
if (!root)
return;
//不递归，采用栈结构
std::stack<node*> obj;
/*两种方法
* Node* p=root;
* while(!obj.empty()||p)
* {
* if(p)//存在即先遍历当前结点，将当前压入栈，留待以后访问右节点，然后遍历左节点
* {
* std::cout<<p->data<<" ";
* obj.push(p);
* p=p->left;
* }
* else//左节点访问到头，访问上一个结点的右节点，
* {
* p=obj.top();
* obj.pop();
* p=p->right;
* }
* }
*/
//优化一下
obj.push(root);
while (!obj.empty())
{
auto p = obj.top();
obj.pop();
std::cout << p->data << " ";
//先压右结点，后压左节点，保证下一次访问该结点的左节点
if(p->left)
obj.push(p->right);
if(p->right)
obj.push(p->left);
}
return;
}
template<class T>
void binary_tree<T>::p_preorder1(node* root)
{
if (!root)
return;
std::cout << root->data << " ";
p_preorder1(root->left);//访问左节点
p_preorder1(root->right);//访问右节点
}
template<class T>
void binary_tree<T>::p_inorder0(node* root)
{
if (!root)
return;
std::stack<node*> obj;
auto p = root;
while (!obj.empty() || p)
{
if (p)//将该结点压入栈内，留待以后遍历
{
obj.push(p);
p = p->left;
}
else
{
p = obj.top();
obj.pop();
std::cout << p->data << " ";
p = p->right;
}
}
}
template<class T>
void binary_tree<T>::p_inorder1(node* root)
{
if (root->left)//有左孩子
p_inorder1(root->left);
std::cout << root->data << " ";
if (root->right)
p_inorder1(root->right);
}
template<class T>
void binary_tree<T>::p_postorder0(node* root)
{
enum child_type{Left,Right};
struct elem
{
node* pointer;
child_type flag;
};
std::stack<elem> obj;
auto p = root;
elem q;
while (!obj.empty() || p)
{
if (p)
{
q.pointer = p;
q.flag = Left;
obj.push(q);
p = p->left;
}
else
{
q = obj.top();
obj.pop();
p = q.pointer;
if (q.flag==Left)//从左边回来且有右孩子
{
q.flag = Right;
obj.push(q);
p = p->right;
}
else
{
std::cout << p->data << " ";
p = nullptr;
}
}
}
}
template<class T>
void binary_tree<T>::p_postorder1(node* root)
{
if (root->left)
p_postorder1(root->left);
if (root->right)
p_postorder1(root->right);
std::cout << root->data << " ";
}
template<class T>
void binary_tree<T>::p_levelorder(node* root)
{
std::queue<node*> obj;
obj.push(root);
while (!obj.empty())
{
int sum = obj.size();
while (sum--)
{
auto p = obj.front();
obj.pop();
std::cout << p->data << " ";
if (p->left)
obj.push(p->left);
if (p->right)
obj.push(p->right);
}
}
}
