@TOC
1.树的基础知识
| 名称 | 定义 |
|---|---|
| 根节点 | A1为根节点 |
| 树的结点 | 树中的数据元素(例：A1、A2、A5等) |
| 结点的度 | 结点子树的个数(例：A1的度为3) |
| 树的度 | 结点的度中最大的为树的度(例：树的度为3) |
| 叶子结点 | 度为0的结点(例：A3、A4) |
| 分支结点 | 度大于0的结点(例：A1,A2) |
| 双亲结点 | 有直接关系的上一层结点(例：A1是A2、A3、A4的双亲) |
| 孩子结点 | 有直接关系的下一层结点例:A2、A3、A4是A1的孩子 |
| 祖先结点 | 从结点的双亲结点到根结点的所有结点 (例：A1、A2为A5的祖先) |
| 子孙结点 | 由该结点所引出的所有结点(例：A2~A7为A1的子孙) |
| 兄弟结点 | 具有同一个双亲结点的的所有结点(例：A2、A3、A4互为兄弟) |
| 堂兄弟结点 | 它们的双亲结点互为兄弟结点的结点(例：A6和A7互为堂兄弟) |
| 结点的深度和高度 | 深度：从上往下数；高度：从下往上数 (例：A1的深度为1，高度为3) |
| 树的深度和高度 | 结点的层数，高度等于深度(例：树的深度为3，高度为3) |
| 路径 | 从某个结点沿着树的层级关系到达另一个结点之间的路线 |
| 路径长度 | 路径上的结点个数 -1 |
2.树的存储
1.树的顺序存储结构
第一行为序号，第二行为存储结点名称，第三行为双亲结点的序号。
typedef struct{
string data;
int pIdx;
}TNode;
TNode tree[maxSize];
tree[0].data="A1";
tree[0].pIdx=-1;
复制代码化简之后的存储方式:双亲存储结构
把A1,A2,A3等的名字改成了0、1、2等，让第一行代表了序号和名称，第二行代表了双亲结点的序号和名称。
int tree[maxSize];
tree[0]=-1;
tree[1]=0;
tree[2]=0;
tree[3]=0;
tree[4]=1;
tree[5]=1;
复制代码2.树的链式存储结构
使用TNode存储所有结点，Branch存储相应TNode的子节点。
typedef struct Branch{
int cIdx;
Branch* next;
}Branch;
typedef struct TNode
{
int data;
Branch* first;
}TNode;
复制代码3.二叉树
1.二叉树的概念
1.二叉树的条件
条件：?
1.每个结点最多两颗子树。
2.子树有左右次序之分。
2.二叉树的所有形态
3.满二叉树
满二叉树：除了最底层以外，所有结点都有左右两个结点。
4.完全二叉树
条件?：
1.叶子结点只能出现在最下层和次最下层。
2.且最下层的叶子结点集中在树的左部。
(b)为非完全二叉树的原因，因为它不满足完全二叉树的第二个条件，结点7没有集中在左侧。
满二叉树是一种特殊的完全二叉树。
2.二叉树的主要性质
性质一?：一颗非空二叉树的第i层上最多有2^i-1^个结点(i≥1)。
结点最多的时候就是为满二叉树的时候，如图所示：
性质二?：一颗深度为K的二叉树中，最多具有2^k^-1给结点。
树的深度等于高度，所有高度为K，当为满二叉树的时候，结点最多。
性质三?：对于一颗非空的二叉树，若叶子结点数为n0，度数为2的结点数为n2,则有n0=n2+1。
证明：
设n为二叉树的结点总数，n1为二叉树中度为1的结点数，所以有 ：
n=n0+n1+n2
设二叉树的分支为B，那么有：
B=n-1
因为分支都由度为1和度为2的结点发出，度为1分支为1，度为2分支为2，所以有:
B=n1+2n2
所以可到
n0=n2+1
性质四?：具有n个结点的完全二叉树的深度k为[logn]+1（向下取整）。
证明：
由性质二可到
2^k-1^-1<n≤2^k^-1（n之所以取不到2^k-1^-1，是因为条件深度为k，否则的话深度就为k-1了）
化为：
2^k-1^≤n<2^k^ (因为n为整数，变一下等号位置就可以完成+1的效果)
对不等式取对数
k-1≤logn<k
因为k为整数，所以k=[logn]+1,向下取整
3.二叉树的存储结构
1.顺序存储结构
==可以通过父结点的位置来求出左右孩子结位置==。当时前提必须是完全二叉树，当不是完全二叉树的时候，我不能通过这种方法来求位置。
当不是完全二叉树怎么办？?
我们可以采用补全的办法，可以把左边的图补成右边的图。
补充之后的存储情况如下：
我们可以看到有很多内存的浪费，所以不建议使用顺序存储结构来存储非完全二叉树，于是我们就有了下方的链式存储结构。
2.链式存储结构
由三个域组成：数据域和两个指针域。
lichild:用来存储左孩子所在的链结点存储地址。
rchild:用来存储右孩子所在的链结点存储地址。
data:用来存储数据。
template<class T>
struct BTNode
{
T data;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
, lchild(NULL)
, rchild(NULL)
{}
};
复制代码3.树、森林和二叉树的互相转换
1.树转化为二叉树?
变化规则：
第一步：连接兄弟结点。例如图中红色线条。
第二步：只保留父节点到它的孩子结点的一条关系线，一般保留最左部的线条。
关于A6不和A7连接，因为A6和A7不为兄弟结点。
变化之后的二叉树：
我可以看到黑线的全部变为左节点，红线的全变为右结点。（画的有点丑）
2.二叉树转换为树?
是树转换为二叉树的逆过程。
1.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
2.去线。删除原二叉树中所有结点与其右孩子结点的连线。
3.森林转换为二叉树?
第一步：把树转换为二叉树。
第二步：把二叉树树的根节点连接起来。
4.二叉树转森林?
第一步：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
第二步：把分离之后的二叉树转化为树。
4.二叉树、树和森林的遍历
遍历：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
1.二叉树广度优先遍历?
广度优先遍历：从上往下，从左往右的逐层访问，而且每个结点只访问一次。
遍历顺序为A1 A2 A3 A4 A5 A6 A7
2.二叉树深度优先遍历(先序、中序、后序)?
定义：
先序遍历：1.访问根结点，2.先序遍历根结点的左子树，3.先序遍历根结点的右子树。
中序遍历：1.中序遍历根结点的左子树，2.访问根结点，3.中序遍历根结点的右子树。
后序遍历：1.后序遍历根节点的左子树，2.后序遍历根节点的右子树，3.访问根节点。
1.根据到达次数来实现遍历?
如图可到：
每个结点都会到达三次,没有子节点的用空结点补全。例如：C的第一次到达是由B到C，第二次到达是由左空结点到达，第三次由右空结点到达。
先序遍历：ABCDEFGH
中序遍历：CBEDFAHG
后续遍历：CEFDBHGA
方法：
先序遍历：第一次来到某个结点时访问，所得序列为先序遍历序列。
中序遍历：第二次来到某个结点时访问，所得序列为中序遍历序列。
后序遍历：第三次来到某个结点时访问，所得序列为后序遍历序列。
2.根据形状来实现遍历?
方法：
先序遍历：根据到达叉图形的先后顺序，所得序列为先序遍历序列。
中序遍历：根据到达五角星的先后顺序，所得序列为中序遍历序列。
后序遍历：根据到达三角形的先后顺序，所得序列为后序遍历序列。
先序遍历：ABDFECGHI
中序遍历：DBEFAGHCI
后续遍历：DEFBHGICA
3.树的广度优先遍历?
性质比较简单，和二叉树的广度优先遍历类似，可参考二叉树。
遍历顺序为A1 A2 A3 A4 A5 A6 A7
4.树的深度优先遍历?
定义：
先序遍历：先访问根结点，然后先序遍历所有子树。
后序遍历：先后序遍历所有子树，最后访问根结点。
因为树与二叉树的区别是：它的子结点个数是不定的，所以我们不能确定中序遍历，只能确定先序和后序遍历。
方法：
先序遍历：第一次来到某个结点时访问，所得序列为先序遍历序列。
后序遍历：最后一次来到某个结点时访问，所得序列为后序遍历序列。
例如：我的箭头的入口是从A1的左边开始的。我以A2为例，A2的第一次来到是从A1到A2，最后一次来到是从A6到A2。
先序遍历：A1 A2 A5 A6 A3 A4
后序遍历：A5 A6 A2 A3 A4 A1
树转换为二叉树之后的遍历情况：
树的先序遍历等于转换后二叉树的先序遍历
树的后序遍历等于转换后二叉树的中序遍历
5.森林的深度优先遍历?
定义：
先序遍历：从左至右先序遍历森林的每一课树。
后序遍历：从左至右后序遍历森林的每一棵树。
先序遍历：A1 A2 A3 A5 A6 A4 A7 A8 A9 A10 A11 A12 A13
后序遍历：A2 A5 A6 A3 A4 A1 A8 A9 A10 A7 A12 A13 A11
森林转化为二叉树之后的遍历情况：
森林的先序遍历等于转换后二叉树的先序遍历
森林的后序遍历等于转换后二叉树的中序遍历
5.二叉树遍历c++代码实现
参考博客地址：用C++语言创建一棵二叉树及实现二叉树的各种操作
1.链式存储结构
由三个域组成：数据域和两个指针域。
lichild:用来存储左孩子所在的链结点存储地址。
rchild:用来存储右孩子所在的链结点存储地址。
data:用来存储数据。
template<class T>
struct BTNode
{
T data;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
, lchild(NULL)
, rchild(NULL)
{}
};
复制代码2.二叉树数据初始化
template<class T> class binary_tree
{
public:
//构造方法
binary_tree(T* a, size_t n, const T&invalid)
{
size_t index = 0; //初始化根节点地址为0
_root = _create_tree(a, n, invalid, index);
}
//创建一棵二叉树
BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index)
{
BTNode<T>* root = NULL;
if (a[index] != invalid)
{
root = new BTNode<T>(a[index]);
root->lchild = _create_tree(a, n, invalid, ++index);
root->rchild = _create_tree(a, n, invalid, ++index);
}
return root;
}
}
复制代码
把图中元素存入二叉树的方法：
‘^’这个表示为空
int array[] = { 1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'};
binary_tree<int> t(array, sizeof(array) / sizeof(int), '^');
复制代码如果不知道怎么初始化的数据怎么填写？
可以看一下这张图：
存在一个弊端，因为’^’的ASCII码为94,当输入结点数据为94会出现问题，所有尽量不要输入94这个数据。
3.深度优先遍历（递归）
1.先序遍历(递归)
//先序遍历
void prev_order()
{
_prev_order(_root);
cout << endl;
}
void _prev_order(BTNode<T>* root)
{
//先序遍历：根结点->左子树->右子树
if (root == NULL)
return;
cout << root->data << " "; //输出遍历到数据
_prev_order(root->lchild);
_prev_order(root->rchild);
}
复制代码输出为：
2.中序遍历(递归)
void in_order()
{
_in_order(_root);
cout << endl;
}
void _in_order(BTNode<T>* root)
{
//中序遍历：左子树->根节点->右子树
if (root == NULL)return;
_in_order(root->lchild);
cout << root->data << " "; //输出遍历到的数据
_in_order(root->rchild);
}
复制代码输出为：
3.后序遍历(递归)
void post_order()
{
_post_order(_root);
cout << endl;
}
void _post_order(BTNode<T>* root)
{
//后序遍历：左子树->右子树->根节点
if (root == NULL)return;
_post_order(root->lchild);
_post_order(root->rchild);
cout << root->data << " ";
}
复制代码输出为：
4.深度优先遍历（非递归）（使用容器：栈）
1.先序遍历(非递归)
思路：
1.建立一个自定义的顺序栈Stack；
2.先从根结点开始扫描；
3.获取到根结点的左右结点，先入栈右结点，后入栈左结点。
4.出栈栈顶结点，然后获取它的左右结点，然后入栈，入栈顺序右先左后；循环根据出栈的元素进行同样操作。
5.所有元素扫描完成。
简洁整体总体来说：就是根据如图路径，从根结点开始出栈，就把它的左右子结点入栈(入栈顺序为先右后左)，结点为空时不入栈。直到遍历完成为止。
void prev_order_no_rt()
{
BTNode<T> *root=_root;
_prev_order_no_rt(root);
cout << endl;
}
void _prev_order_no_rt(BTNode<T>* bt)
{
if(bt!=NULL)
{
BTNode<T> *Stack[maxSize];
int top=-1;
BTNode<T> *p=NULL;
//入栈根结点
Stack[++top]=bt;
while(top!=-1)
{
//出栈栈顶元素
p=Stack[top--];
cout<<p->data<<" ";
//先入栈右结点
if(p->rchild!=NULL)
Stack[++top]=p->rchild;
//后入栈左结点
if(p->lchild!=NULL)
Stack[++top]=p->lchild;
}
}
}
复制代码输出为：
2.后序遍历(非递归)
实现思路：
通过先序遍历来推出后序遍历。
证明：
后序遍历：先左结点，然后右结点，最后根结点；
逆后序遍历：先根结点，然后右结点，最后左结点；
先序遍历：先根结点，然后左结点，最后右结点；
我们对比先序遍历和逆后序遍历的区别：发现只有左右结点的顺序不同；所以我们前面在进行非递归的前序遍历的时候，入栈的顺序为先右结点，后左结点，所以我们进行逆后序遍历的时候只需要把入栈顺序调换一下，变为先左结点，后右结点入栈。
如图：我们可以看到先序遍历推出的结果和逆后序遍历相同，把逆后序遍历倒过来看就是后序遍历。
逆后序遍历怎么转变为后序遍历呢？
只需要使用一个栈来入栈逆后序遍历，出栈则为后序遍历。
void post_order_no_r()
{
_post_order_no_r(_root);
cout<<endl;
}
void _post_order_no_r(BTNode<T> *bt)
{
if(bt!=NULL)
{
//用于实现逆后序遍历数据
BTNode<T> *Stack1[maxSize];int top1=-1;
//用于实现后序遍历数据
BTNode<T> *Stack2[maxSize];int top2=-1;
BTNode<T> *p=NULL;
Stack1[++top1]=bt;
while(top1!=-1)
{
p=Stack1[top1--];
//入栈逆后序遍历数据
Stack2[++top2]=p;
//入栈左结点
if(p->lchild!=NULL)
Stack1[++top1]=p->lchild;
//入栈右结点
if(p->rchild!=NULL)
Stack1[++top1]=p->rchild;
}
while(top2!=-1)
{
//出栈
p=Stack2[top2--];
cout<<p->data<<" ";
}
}
}
复制代码输出为：
3.中序遍历(非递归)
总体来说：延如图路径，当遇到结点不空时，结点入栈；当遇到结点为空时，则出栈。
代码：
void in_order_no_r()
{
_in_order_no_r(_root);
cout<<endl;
}
void _in_order_no_r(BTNode<T>* bt)
{
if(bt!=NULL)
{
BTNode<T> *Stack[maxSize];int top=-1;
BTNode<T> *p=NULL;
p=bt;
while(top!=-1||p!=NULL)
{
while(p!=NULL)
{
Stack[++top]=p;
p=p->lchild;
}
if(top!=-1)
{
p=Stack[top--];
cout<<p->data<<" ";
p=p->rchild;
}
}
}
}
复制代码输出为：
5.层次遍历（使用容器：队列）
层次遍历：就是从左至右，从上至下的一层一层的遍历。
条件：自定义一个顺序队列。
如果对队列不是很了解的，可以去看一下这篇博客栈和队列，不过你也可以使用系统自带的容器queue，不过我们毕竟是学数据结构，还是使用自定义的才能锻炼我们。
思路：
首先根结点入队，然后根结点出队，把它左右结点依次入队(左先右后)；然后出队队顶元素，把它的左右结点入队，如果没有左右结点，则继续出队；循环进行，直到把遍历完成。
void level(){
_level(_root);
cout<<endl;
}
void _level(BTNode<T>* bt)
{
if(bt!=NULL)
{
//front用于出队，rear用于入队
int front,rear;
//自定义循环顺序队列
BTNode<T> *Queue[maxSize];
front=rear=0;
BTNode<T> *p;
//入队根结点
rear=(rear+1)%maxSize;
Queue[rear]=bt;
while(front!=rear)
{
//出队队顶元素
front=(front+1)%maxSize;
p=Queue[front];
cout<<p->data<<" ";
if(p->lchild!=NULL)
{
//左子结点不为NULL，入队
rear=(rear+1)%maxSize;
Queue[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
//右子结点不为NULL，入队
rear=(rear+1)%maxSize;
Queue[rear]=p->rchild;
}
}
}
}
复制代码输出为：
6.二叉树整体代码
#include<iostream>
using namespace std;
#define maxSize 10
template<class T>
struct BTNode
{
T data;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
, lchild(NULL)
, rchild(NULL)
{}
};
template<class T> class binary_tree
{
typedef BTNode<T> node;
public:
binary_tree(T* a, size_t n, const T&invalid)
{
size_t index = 0;
_root = _create_tree(a, n, invalid, index);
}
//创建一棵二叉树
BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index)
{
BTNode<T>* root = NULL;
if (a[index] != invalid)
{
root = new BTNode<T>(a[index]);
root->lchild = _create_tree(a, n, invalid, ++index);
root->rchild = _create_tree(a, n, invalid, ++index);
}
return root;
}
//前序遍历
void prev_order()
{
_prev_order(_root);
cout << endl;
}
void _prev_order(BTNode<T>*root)
{
if (root == NULL)
return;
cout << root->data << " ";
_prev_order(root->lchild);
_prev_order(root->rchild);
}
//非递归的前序遍历
void prev_order_no_rt()
{
BTNode<T> *root=_root;
_prev_order_no_rt(root);
cout << endl;
}
void _prev_order_no_rt(BTNode<T>* bt)
{
if(bt!=NULL)
{
BTNode<T> *Stack[maxSize];
int top=-1;
BTNode<T> *p=NULL;
Stack[++top]=bt;
while(top!=-1)
{
p=Stack[top--];
cout<<p->data<<" ";
if(p->rchild!=NULL)
Stack[++top]=p->rchild;
if(p->lchild!=NULL)
Stack[++top]=p->lchild;
}
}
}
//中序遍历
void in_order()
{
_in_order(_root);
cout << endl;
}
void _in_order(BTNode<T>* root)
{
//中序遍历：左子树->根节点->右子树
if (root == NULL)return;
_in_order(root->lchild);
cout << root->data << " ";
_in_order(root->rchild);
}
//非递归的中序遍历
void in_order_no_r()
{
_in_order_no_r(_root);
cout<<endl;
}
void _in_order_no_r(BTNode<T>* bt)
{
if(bt!=NULL)
{
BTNode<T> *Stack[maxSize];int top=-1;
BTNode<T> *p=NULL;
p=bt;
while(top!=-1||p!=NULL)
{
while(p!=NULL)
{
Stack[++top]=p;
p=p->lchild;
}
if(top!=-1)
{
p=Stack[top--];
cout<<p->data<<" ";
p=p->rchild;
}
}
}
}
//后序遍历
void post_order()
{
_post_order(_root);
cout << endl;
}
void _post_order(BTNode<T>* root)
{
//后序遍历：左子树->右子树->根节点
if (root == NULL)return;
_post_order(root->lchild);
_post_order(root->rchild);
cout << root->data << " ";
}
//非递归的后序遍历
void post_order_no_r()
{
_post_order_no_r(_root);
cout<<endl;
}
void _post_order_no_r(BTNode<T> *bt)
{
if(bt!=NULL)
{
BTNode<T> *Stack1[maxSize];int top1=-1;
BTNode<T> *Stack2[maxSize];int top2=-1;
BTNode<T> *p=NULL;
Stack1[++top1]=bt;
while(top1!=-1)
{
p=Stack1[top1--];
Stack2[++top2]=p;
if(p->lchild!=NULL)
Stack1[++top1]=p->lchild;
if(p->rchild!=NULL)
Stack1[++top1]=p->rchild;
}
while(top2!=-1)
{
p=Stack2[top2--];
cout<<p->data<<" ";
}
}
}
//层次遍历
void level(){
_level(_root);
cout<<endl;
}
void _level(BTNode<T>* bt)
{
if(bt!=NULL)
{
int front,rear;
BTNode<T> *Queue[maxSize];
front=rear=0;
BTNode<T> *p;
rear=(rear+1)%maxSize;
Queue[rear]=bt;
while(front!=rear)
{
front=(front+1)%maxSize;
p=Queue[front];
cout<<p->data<<" ";
if(p->lchild!=NULL)
{
rear=(rear+1)%maxSize;
Queue[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
rear=(rear+1)%maxSize;
Queue[rear]=p->rchild;
}
}
}
}
protected:
node *_root;
};
//测试部分
void test_binary_tree()
{
int array[] = { 1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'};
binary_tree<int> t(array, sizeof(array) / sizeof(int), '^');
t.prev_order();
t.in_order();
t.post_order();
t.prev_order_no_rt();
t.post_order_no_r();
t.in_order_no_r();
t.level();
}
int main(void)
{
test_binary_tree();
system("pause");
}
复制代码6.线索二叉树
1.先序线索二叉树
思路：
沿类似于上图中的先序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。
关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（+）加号的看出路径，可以得到先序遍历的顺序为：
1 2 4 5 3 6 8 7
我们以图中结点4为例子：
==4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从先序遍历的顺序看出，4的前驱结点为2，4的后继结点为5，其他同理可得，所以得到如图的连线。==
我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。
rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。
data:用来存储数据。
和我们使用的是先序遍历的递归很像。顺序为：
根结点->左子树->右子树
代码如下：
void _preThread(BTNode<T> *p,BTNode<T> *&pre)
{
if(p!=NULL)
{
//当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
//当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
//根结点
pre=p;
//左子树
if(p->lTag==0)
_preThread(p->lchild,pre);
//右子树
if(p->rTag==0)
_preThread(p->rchild,pre);
}
}
复制代码虽然我们实现了先序线索二叉树 ，但是要使用它来遍历打印出数据。
思路：
首先指向根结点，然后根结点的，左子结点，左子结点的左子结点….不为空的话，就沿路打印出所到结点；然后当左结点为空时，指向它的右子结点（部分右子结点是他的后继结点）；然后继续判断左结点是否为空，这样循环就可以打印出我们想要的数据了。
打印路径：如图红色线条
因为我们没有用前驱结点，我就把它删掉了。后面的后序遍历我们就只使用前驱结点，没使用后继结点。
代码表示：
//线索二叉树前序遍历
void preThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root=_root;
_preThread(root,p);
while(root!=NULL)
{
while(!root->lTag)
{
cout<<root->data<<" ";
root=root->lchild;
}
cout<<root->data<<" ";
root=root->rchild;
}
cout<<endl;
}
复制代码整体代码：
#include<iostream>
using namespace std;
#define maxSize 10
template<class T>
struct BTNode
{
T data;
T lTag;
T rTag;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
,lTag(0)
,rTag(0)
, lchild(NULL)
, rchild(NULL)
{}
};
template<class T> class binary_tree
{
typedef BTNode<T> node;
public:
binary_tree(T* a, size_t n, const T&invalid)
{
size_t index = 0;
_root = _create_tree(a, n, invalid, index);
}
//创建一棵二叉树
BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index)
{
BTNode<T>* root = NULL;
if (a[index] != invalid)
{
root = new BTNode<T>(a[index]);
root->lchild = _create_tree(a, n, invalid, ++index);
root->rchild = _create_tree(a, n, invalid, ++index);
}
return root;
}
//线索二叉树前序遍历
void preThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root=_root;
_preThread(root,p);
while(root!=NULL)
{
while(!root->lTag)
{
cout<<root->data<<" ";
root=root->lchild;
}
cout<<root->data<<" ";
root=root->rchild;
}
cout<<endl;
}
void _preThread(BTNode<T> *p,BTNode<T> *&pre)
{
if(p!=NULL)
{
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
pre=p;
if(p->lTag==0)
_preThread(p->lchild,pre);
if(p->rTag==0)
_preThread(p->rchild,pre);
}
}
protected:
node *_root;
};
//测试部分
void test_binary_tree()
{
int array[] = { 1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'};
binary_tree<int> t(array, sizeof(array) / sizeof(int), '^');
t.preThread();
}
int main(void)
{
test_binary_tree();
system("pause");
}
复制代码2.后序线索二叉树
因为和前序二叉树有点像，所以就先说明后序线索二叉树。
思路：
沿类似于上图中的后序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。
关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（-）负号的看出路径，可以得到后序遍历的顺序为：
4 5 2 8 6 7 3 1
我们以图中结点4为例子：
==4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从后序遍历的顺序看出，4的没有前驱结点，4的后继结点为5，其他同理可得，所以得到如图的连线。==
我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。
rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。
data:用来存储数据。
和我们前面的先序线索二叉树非常类似，只是代码的顺序不同，因为这个是左子树->右子树->根结点
代码如下：
void _postThread(BTNode<T> *p,BTNode<T> *&pre)
{
if(p!=NULL)
{
//左子树
_postThread(p->lchild,pre);
//右子树
_postThread(p->rchild,pre);
//当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
//当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
//根结点
pre=p;
}
}
复制代码虽然我们实现了后序线索二叉树 ，但是要使用它来遍历打印出数据。
思路：
因为我们和先序遍历一样的方向，难以达到我们想要的效果，如果我们从与它相反的路径来看的话，我们所想要解决问题是不是就很明确，和我们先序遍历的解决方法和类似，不过打印出的数据是逆后序遍历，所以我们需要一个自定义栈来存储逆后序遍历，出栈则为后序遍历。
打印路径：如图红色线条
因为我们没有用后继驱结点，我就把它删掉了。
代码表示：
void postThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root2=_root;
BTNode<T> *stack[maxSize];
int top=-1;
_postThread(root2,p);
while(root2!=NULL)
{
while(!root2->rTag)
{
stack[++top]=root2;
root2=root2->rchild;
}
stack[++top]=root2;
root2=root2->lchild;
}
while(top!=-1)
{
p=stack[top--];
cout<<p->data<<" ";
}
cout<<endl;
}
复制代码整体代码：
#include<iostream>
using namespace std;
#define maxSize 10
template<class T>
struct BTNode
{
T data;
T lTag;
T rTag;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
,lTag(0)
,rTag(0)
, lchild(NULL)
, rchild(NULL)
{}
};
template<class T> class binary_tree
{
typedef BTNode<T> node;
public:
binary_tree(T* a, size_t n, const T&invalid)
{
size_t index = 0;
_root = _create_tree(a, n, invalid, index);
}
//创建一棵二叉树
BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index)
{
BTNode<T>* root = NULL;
if (a[index] != invalid)
{
root = new BTNode<T>(a[index]);
root->lchild = _create_tree(a, n, invalid, ++index);
root->rchild = _create_tree(a, n, invalid, ++index);
}
return root;
}
//线索二叉树后序遍历
void postThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root2=_root;
BTNode<T> *stack[maxSize];
int top=-1;
_postThread(root2,p);
while(root2!=NULL)
{
while(!root2->rTag)
{
stack[++top]=root2;
root2=root2->rchild;
}
stack[++top]=root2;
root2=root2->lchild;
}
while(top!=-1)
{
p=stack[top--];
cout<<p->data<<" ";
}
cout<<endl;
}
void _postThread(BTNode<T> *p,BTNode<T> *&pre)
{
if(p!=NULL)
{
_postThread(p->lchild,pre);
_postThread(p->rchild,pre);
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
pre=p;
}
}
protected:
node *_root;
};
//测试部分
void test_binary_tree()
{
int array[] = { 1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'};
binary_tree<int> t2(array, sizeof(array) / sizeof(int), '^');
t2.postThread();
}
int main(void)
{
test_binary_tree();
system("pause");
}
复制代码3.中序线索二叉树
思路：
沿类似于上图中的中序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。
关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（=）等于号的看出路径，可以得到中序遍历的顺序为：
4 2 5 1 8 6 3 7
我们以图中结点4为例子：
==4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从后序遍历的顺序看出，4的没有前驱结点，4的后继结点为2，其他同理可得，所以得到如图的连线。==
我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。
rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。
data:用来存储数据。
和我们中序遍历的递归非常类似，顺序为：
左子树->根结点->右子树
代码：
void _inThread(BTNode<T> *&p,BTNode<T> *&pre)
{
if(p!=NULL)
{
//左子树
_inThread(p->lchild,pre);
//当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
//当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
//根结点
pre=p;
//右子树
_inThread(p->rchild,pre);
}
}
复制代码虽然我们实现了中序线索二叉树 ，但是要使用它来遍历打印出数据。
图中：
==蓝色箭头+红色箭头为路径，其中红色箭头的起点为打印结点==。
思路：
沿如图入口处进入，如果遇到存在结点且左子结点不空，使用它的左子结点等于当前结点，当结点的左子结点为空时，我们打印出当前结点；然后判断右子结点是否为空，当为空时，使结点的后继结点等于当前结点，当不为空时，使结点的右子结点等于当前结点，然后继续 判断当前结点存在结点且左子结点不空，让左子结点等于当前结点；然后循环进行。
看代码可能更轻易看懂：
void inThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root1=_root;
_inThread(root1,p);
while(root1!=NULL&&root1->lTag==0)
{
root1=root1->lchild;
}
while(root1!=NULL)
{
cout<<root1->data<<" ";
if(root1->rTag==1){
root1=root1->rchild;
}else{
root1=root1->rchild;
while(root1!=NULL&&root1->lTag==0)
{
root1=root1->lchild;
}
}
}
cout<<endl;
}
复制代码整体代码：
#include<iostream>
using namespace std;
#define maxSize 10
template<class T>
struct BTNode
{
T data;
T lTag;
T rTag;
BTNode<T>* lchild;
BTNode<T>* rchild;
BTNode(const T& x)
:data(x)
,lTag(0)
,rTag(0)
, lchild(NULL)
, rchild(NULL)
{}
};
template<class T> class binary_tree
{
typedef BTNode<T> node;
public:
binary_tree(T* a, size_t n, const T&invalid)
{
size_t index = 0;
_root = _create_tree(a, n, invalid, index);
}
//创建一棵二叉树
BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index)
{
BTNode<T>* root = NULL;
if (a[index] != invalid)
{
root = new BTNode<T>(a[index]);
root->lchild = _create_tree(a, n, invalid, ++index);
root->rchild = _create_tree(a, n, invalid, ++index);
}
return root;
}
//线索二叉树中序遍历
void inThread()
{
BTNode<T> *p=NULL;
BTNode<T> *root1=_root;
_inThread(root1,p);
while(root1!=NULL&&root1->lTag==0)
{
root1=root1->lchild;
}
while(root1!=NULL)
{
cout<<root1->data<<" ";
if(root1->rTag==1){
root1=root1->rchild;
}else{
root1=root1->rchild;
while(root1!=NULL&&root1->lTag==0)
{
root1=root1->lchild;
}
}
}
cout<<endl;
}
void _inThread(BTNode<T> *&p,BTNode<T> *&pre)
{
if(p!=NULL)
{
_inThread(p->lchild,pre);
if(p->lchild==NULL)
{
p->lchild=pre;
p->lTag=1;
}
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=p;
pre->rTag=1;
}
pre=p;
_inThread(p->rchild,pre);
}
}
protected:
node *_root;
};
//测试部分
void test_binary_tree()
{
int array[] = { 1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'};
binary_tree<int> t1(array, sizeof(array) / sizeof(int), '^');
t1.inThread();
}
int main(void)
{
test_binary_tree();
system("pause");
}
复制代码4.代码打印结果：
7.哈夫曼树
8.重建二叉树
1.先序、中序确定二叉树
BTNode* CreateBT(char pre[],char in[],int L1,int R1,int L2,int R2)
{
if(L1>R1)
return NULL;
BTNode *s=new BTNode();
s->lchild=s->rchild=NULL;
s->data=pre[L1];
int i;
for(i=L2;i<=R2;++i)
if(in[i]==pre[L1])
break;
s->lchild=CreateBT(pre,in,L1+1,L1+i-L2,L2,i-1);
s->rchild=CreateBT(pre,in,L1+i-L2+1,R1,i+1,R2);
return s;
}
复制代码2.后序、中序确定二叉树
BTNode *CreateBT2(char post[],char in[],int L1,int R1,int L2,int R2)
{
if(L1>R1)
return NULL;
BTNode *s=new BTNode();
s->lchild=s->rchild=NULL;
s->data=post[R1];
int i;
for(i=L2;i<=R2;++i)
if(in[i]==post[R1])
break;
s->lchild=CreateBT2(post,in,L1,L1+i-L2+1,L2,i-1);
s->rchild=CreateBT2(post,in,L1+i-L2,R1-1,i+1,R2);
return s;
}
复制代码3.层次序列和中序序列确定二叉树
BTNode *CreateBT3(char level[],char in[],int n,int L,int R)
{
if(L>R)
return NULL;
BTNode *s=new BTNode();
s->lchild=s->rchild=NULL;
s->data=level[0];
int i=search(in,level[0],L,R);
int LN=i-L; char LLevel[LN];
int RN=R-i; char RLevel[RN];
getSubLevel(LLevel,level,in,n,L,i-1);
getSubLevel(RLevel,level,in,n,i+1,R);
s->lchild=CreateBT3(LLevel,in,LN,L,i-1);
s->rchild=CreateBT3(RLevel,in,RN,i+1,R);
}
int search(char arr[],char key,int L,int R)
{
int idx;
for(idx=L;idx<=R;++idx)
if(arr[idx]==key)
return idx;
return -1;
}
void getSubLevel(char subLevel[],char level[],char in[],int n,int L,int R)
{
int k=0;
for(int i=0;i<n;++i)
if(search(in,level[i],L,R)!=-1)
subLevel[k++]=level[i];
}
复制代码学习通视频：天勤考研
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
