数据结构 树
被文科折磨的百忙之中抽空学习(麻了，我还是个工科生吗)，学习完之后一堆文科小组作业等着我……(主打一个裸考四级，乐)
树型结构：逻辑结构 概念：树是存储一对多关系的数据的逻辑结构，在树中，用节点存储数据
节点分类: 1.根节点(无前驱节点) 2.叶子节点(无子节点) 3.内部节点(有些教材把根节点归为内部节点)
父子关系和兄弟关系(一般理解为广义兄弟关系)
树：度/阶—表示节点分了多少个叉
节点的度：该节点孩子节点的数目/分叉的数目 树的度：max(所有节点的度)，如果树的度为n，称为n叉树
树的高度和深度：在数值上一样(方向不一样，从上往下或从下往上) 结点的深度：注意方向即可
方便操作根节点，在之前增加一个空节点(与链表头节点类似) 方便操作叶子节点，在其之后增加一个空节点
存储结构:
存一棵树：1.节点数据 2.数据之间的关系–父子
1.双亲(父亲)表示法：方便找父亲，不方便找孩子 1.顺序存储方式存数据：–数组 2.在存数据的同时，把每个数据的父亲所在下标存一下
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class Node
{
public:
T data;//存储数据
int fi;//father_i,fi == -1,认为是根节点
};
template<class T>
class Tree
{
public:
int size;
Node<T>* pN;//指针开辟数组，存储节点
public:
Tree(T k, int sz = 1)
{
//加入根节点
pN = new Node<T>[sz];
pN[0].data = k;
pN[0].fi = -1;
size = 1;
}
int Find(T fx)
{
for (int i = 0; i < size; i++)
{
if (pN[i].data == fx)
{
return i;
}
}
return -1;
}
void insert(T x, T fx)
{
pN[size].data = x;
int fx_i = Find(fx);
if (fx_i == -1)
{
cout << x << "的父亲不存在" << endl;
return;
}
pN[size].fi = fx_i;
size++;
}
void Find_Ch(T x)
{
int x_i = Find(x);//查找该数据对应坐标，通过坐标找到该节点孩子节点
int sum(0);
for (int i = 0; i < size; i++)
{
if (pN[i].fi == x_i)
{
sum++;
cout << pN[i].data << ' ';
}
}
if (sum == 0)
{
cout << x << "没有孩子节点" << endl;
}
}
void Find_Fa(T x)
{
int x_i = Find(x);
int fa_i = pN[x_i].fi;
if (fa_i == -1)
{
cout << "该节点是根节点，没有父亲节点" << endl;
}
else
{
cout << pN[fa_i].data << ' ' << endl;
}
}
};
//一般的树不考虑删除
int main()
{
int n(0);
cin >> n;
Tree<int> t(100, n);
t.insert(12, 100);
t.insert(13, 100);
t.Find_Ch(100);
t.Find_Fa(13);
cout << t.Find(100) << endl;
return 0;
}
2.孩子表示法： 1.顺序存储方式存数据：–数组 2.链表来存每个节点孩子的数据
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class ch_Node
{
public:
T data;
ch_Node<T>* next;
};
template<class T>
class ch_Link //孩子链表
{
public:
ch_Link()
{
head = new ch_Node<T>;
if (head == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
head->next = nullptr;
}
}
public:
ch_Node<T>* head;
};
template<class T>
class Tree_Node //树的节点
{
public:
T data;
ch_Link<T> cl;
};
template<class T>
class Tree //树
{
public:
Tree(T k, int sz = 1)
{
size = 0;
nd = new Tree_Node<T>[sz];
nd[0].data = k;
size++;
}
int Find(T x)
{
for (int i = 0; i < size; i++)
{
if (nd[i].data == x)
{
return i;
}
}
return -1;
}
void insert(T x, T fx)
{
nd[size].data = x; //放入新节点数据
nd[size].cl.head->next = nullptr;
int fx_i = Find(fx);//建立fx与x父子关系
if (fx_i == -1)
{
cout << "为根节点，无法建立" << endl;
}
else
{
ch_Node<T>* s = new ch_Node<T>;
s->data = x;
//头插法
s->next = nd[fx_i].cl.head->next;
nd[fx_i].cl.head->next = s;
size++;
}
}
void Find_Ch(T x)
{
int x_i = Find(x);
ch_Node<T>* p = nd[x_i].cl.head->next;
if (p == nullptr)
{
cout << x << "没有孩子" << endl;
return;
}
while (p != nullptr)
{
cout << p->data << ' ';
p = p->next;
}
cout << endl;
}
void Find_Fa(T x)
{
ch_Node<T>* p = nullptr;
int flag(0); //用于标记根节点
for (int i = 0; i < size; i++)
{
p = nd[i].cl.head->next;
while (p != nullptr && p->data != x)
{
p = p->next;
}
if (p != nullptr && p->data == x)
{
cout << nd[i].data << ' ' << endl;
flag = 1;
break;
}
}
if (flag == 0)
{
cout << x << "是根节点" << endl;
}
}
public:
Tree_Node<T>* nd;
int size;
};
int main()
{
Tree<int> t(100, 1000);
t.insert(2, 100);
t.insert(3, 100);
t.insert(4, 100);
t.insert(5, 100);
t.Find_Ch(100);
t.Find_Fa(100);
return 0;
}
3.孩子兄弟表示法—二叉链表
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class Tree_Node
{
public:
T data;
Tree_Node<T>* first_child; //指向第一个孩子
Tree_Node<T>* bro; //指向右边第一个亲兄弟
};
template<class T>
class Tree
{
public:
Tree(T root)
{
Tree_Link = new Tree_Node<T>;
if (Tree_Link == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
Tree_Link->bro = nullptr;
Tree_Link->data = root;
Tree_Link->first_child = nullptr;
}
}
//查找，通过递归实现
Tree_Node<T>* Find(Tree_Node<T>* nd, T fx)
{
//递归出口
if (nd == nullptr || nd->data == fx)
{
return nd;
}
if (nd->first_child != nullptr)
{
Tree_Node<T>* ans = Find(nd->first_child, fx);
if (ans != nullptr && ans->data == fx)
{
return ans;
}
}
if (nd->bro != nullptr)
{
Tree_Node<T>* ans = Find(nd->bro, fx);
if (ans != nullptr && ans->data == fx)
{
return ans;
}
}
return nullptr;//fx不存在
}
void Insert(T x, T fx)
{
Tree_Node<T>* t = Find(Tree_Link, fx);
if (t == nullptr)
{
cout << "父亲节点不存在" << endl;
return;
}
else
{
Tree_Node<T>* s = new Tree_Node<T>;
if (s == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
s->data = x;
//进行头插（比尾插简单一些）
//如果插入的为长子
if (t->first_child == nullptr)
{
t->first_child = s;
s->first_child = nullptr;
s->bro = nullptr;
}
else //插入的不是长子
{
Tree_Node<T>* fir = t->first_child;
s->bro = fir->bro;
fir->bro = s;
s->first_child = nullptr;
}
}
}
}
public:
Tree_Node<T>* Tree_Link; //根指针
};
int main()
{
Tree<int> t(100);
t.Insert(12, 100);
t.Insert(16, 100);
t.Insert(15, 100);
t.Insert(14, 100);
t.Insert(13, 100);
t.Insert(200, 15);
t.Insert(201, 15);
t.Insert(202, 15);
t.Insert(203, 15);
t.Insert(204, 15);
t.Insert(205, 15);
Tree_Node<int>* p = t.Find(t.Tree_Link, 15);
Tree_Node<int>* fir = p->first_child;
if (fir != nullptr)
{
p = fir;
while (p != nullptr)
{
cout << p->data << ' ' << endl;
p = p->bro;
}
}
return 0;
}
二叉树
两种特殊二叉树 1.满二叉树：深度为k，并且节点个数为(2^k)-1的二叉树 2.完全二叉树；对满二叉树，从下向上，从右向左依次删掉若干个节点，剩下的树就是完全二叉树 性质：默认根节点是第一层 1.在二叉树的第i层，最多有2^(i - 1)个节点
2.深度为k的二叉树，最多有(2^k)-1个节点（等比求和）
3.在一棵二叉树中，叶子节点的数目比度为2的节点数目多一个
4.具有n个节点的完全二叉树的深/高度为(logn) + 1, 其中logn向下取整
5.对于一棵完全二叉树，进行编号，编号规则为：根节点为1，然后从上到下，从左到右。除根节点外，节点i的父亲节点编号为i/2(向下取整)。除叶子节点外，节点i的左孩子节点编号为2i，右节点为2i+1
补充性质：任何一棵二叉树都可以加NULL节点，从而补成一棵满(或完全)二叉树(结合性质5得到一个存二叉树的方式–顺序存储，基于数组)
二叉树的操作
1.建树--插入数据
2.遍历（两类四种）：沿着某条路径，对树中的节点都遍历一次且仅遍历一次。
1.层次遍历--广度优先遍历
遍历顺序：从上往下，依次输出每一层节点（左->右）
2.深度优先遍历：先序遍历(根，左，右)，中序遍历(左，根，右)，后序遍历(左，右，根)
3.线索化
背景：
1.n个节点二叉树，以二叉链表存储，一共2n个指针域，n-1个真正存储了指针，n+1为空，极大浪费空间
2.某一节点的中序遍历序列的前驱与后继是谁
3.如何快速得到某节点中序遍历序列中的前驱与后继
具体操作：
1.如果一个节点其左孩子指针域为空，那么将该指针域指向其前驱节点
2.如果一个节点其右孩子指针域为空，那么将该指针域指向其后继节点
历时两周，终于把二叉树学习完了，不过这只是开始，紧接着来到的是排序二叉树，二叉平衡树……
二叉树具体实现如下（包括了广度遍历，深度遍历（递归与非递归实现），线索化，查找中序遍历前驱与后继等操作）
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//链栈，用于实现非递归深度优先遍历
template<class T>
class stack_Node
{
public:
T data;
stack_Node<T>* next;
};
template<class T>
class m_stack
{
public:
stack_Node<T>* head;
public:
m_stack()
{
head = new stack_Node<T>;
if (head == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
head->next = nullptr;
}
}
void m_push(T k)
{
stack_Node<T>* s = new stack_Node<T>;
s->next = head->next;
s->data = k;
head->next = s;
}
T m_pop()
{
if (m_empty())
{
cout << "栈空" << endl;
}
else
{
//p指向要删除的首元节点
stack_Node<T>* p = head->next;
T k = p->data;
head->next = p->next;
delete p;
p = nullptr;
return k;
}
}
bool m_empty()
{
if (head->next == nullptr)
return true;
else
return false;
}
void get_top()
{
if (m_empty())
{
cout << "栈空" << endl;
}
else
{
cout << head->next->data << endl;
}
}
};
//链式队列，用于实现广度优先遍历
template<class T>
class q_Node
{
public:
T data;
q_Node<T>* next;
};
template<class T>
class Link_queue
{
public:
q_Node<T>* head;//指向头节点的指针
q_Node<T>* rear;//指向队尾元素所在节点的指针
public:
Link_queue()
{
head = new q_Node<T>;
rear = head;
if (head == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
head->next = nullptr;
rear->next = nullptr;
}
}
bool m_Empty()
{
if (head->next == nullptr)
{
return true;
}
return false;
}
void En_queue(T k)
{
q_Node<T>* s = new q_Node<T>;
if (s == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//新节点插入队尾
s->data = k;
s->next = nullptr;
rear->next = s;
rear = s;
}
}
T Del_queue()
{
//出队时需要注意是否是首元节点出队
T x(0);//保存出队元素
//判空
//1.head->next == nullptr
//2.head == rear
if (m_Empty())
{
cout << "队空" << endl;
}
else
{
q_Node<T>* p = head->next;
x = head->next->data;
head->next = head->next->next;
if (head->next == nullptr)//删除唯一节点时避免队尾指针成为野指针
{
rear = head;
}
delete p;
p = nullptr;
return x;
}
}
};
template<class T>
class Binary_Tree_Node
{
public:
T data;
Binary_Tree_Node<T>* left;
Binary_Tree_Node<T>* right;
int lflag;
int rflag;//标记左右指针指向的是孩子节点（0），还是前驱后继 （1）
public:
Binary_Tree_Node()
{
lflag = 0;
rflag = 0;
}
};
template<class T>
class Binary_Tree
{
public:
Binary_Tree(T k)
{
root = new Binary_Tree_Node<T>;
if (root == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
root->data = k;
root->left = nullptr;
root->right = nullptr;
pre_in_thread = nullptr;
}
}
Binary_Tree_Node<T>* Find(Binary_Tree_Node<T>* ro, T fx)
{
//运用递归实现,与先前孩子兄弟表示法查找方法相同
if (ro == nullptr || ro->data == fx)
{
return ro;
}
//在线索化之后进行额外判断，判断是真孩子还是前驱后继
if (ro->left != nullptr && ro->lflag == 0)
{
Binary_Tree_Node<T>* f = Find(ro->left, fx);
if (f != nullptr && f->data == fx)
{
return f;
}
}
//在线索化之后进行额外判断，判断是真孩子还是前驱后继
if (ro->right != nullptr && ro->rflag == 0)
{
Binary_Tree_Node<T>* f = Find(ro->right, fx);
if (f != nullptr && f->data == fx)
{
return f;
}
}
return nullptr;//fx不存在
}
void Right_Insert(T x, T fx)
{
Binary_Tree_Node<T>* f = Find(root, fx);
if (f != nullptr)
{
Binary_Tree_Node<T>* s = new Binary_Tree_Node<T>;
s->data = x;
s->left = nullptr;
s->right = nullptr;
f->right = s;
}
}
void Left_Insert(T x, T fx)
{
Binary_Tree_Node<T>* f = Find(root, fx);
if (f != nullptr)
{
Binary_Tree_Node<T>* s = new Binary_Tree_Node<T>;
s->data = x;
s->left = nullptr;
s->right = nullptr;
f->left = s;
}
}
//二叉树的遍历
//层次遍历--广度优先遍历
void Level_Order()
{
Binary_Tree_Node<T>* x = nullptr;
Link_queue<Binary_Tree_Node<T>*> m_queue;
//判断树非空
if (root == nullptr)
{
cout << "树空" << endl;
return;
}
//根节点入队
m_queue.En_queue(root);//入队数据与入队节点不同
while (!m_queue.m_Empty())
{
x = m_queue.Del_queue();
cout << x->data << ' ';
if (x->left != nullptr)
{
m_queue.En_queue(x->left);
}
if (x->right != nullptr)
{
m_queue.En_queue(x->right);
}
}
}
//深度优先遍历(均以递归实现)
//先序遍历
void pre_Order(Binary_Tree_Node<T>* ro)
{
//出口，ro == nullptr
//1.输出根节点数据
//2.判断根左非空，递归调用，传入ro->left
//3.判断根右非空，递归调用，传入ro->right
if (ro == nullptr)
{
return;
}
cout << ro->data << ' ';
if (ro->left != nullptr)
{
pre_Order(ro->left);
}
if (ro->right != nullptr)
{
pre_Order(ro->right);
}
}
//中序遍历（改变输出根节点数据顺序）
void mid_Order(Binary_Tree_Node<T>* ro)
{
if (ro == nullptr)
{
return;
}
if (ro->left != nullptr)
{
mid_Order(ro->left);
}
cout << ro->data << ' ';
if (ro->right != nullptr)
{
mid_Order(ro->right);
}
}
//后序遍历（改变输出根节点数据顺序）
void last_Order(Binary_Tree_Node<T>* ro)
{
if (ro == nullptr)
{
return;
}
if (ro->left != nullptr)
{
last_Order(ro->left);
}
if (ro->right != nullptr)
{
last_Order(ro->right);
}
cout << ro->data << ' ';
}
//深度优先遍历（非递归实现,基于链栈）
//先序遍历
void pre_Order_non_recursion()
{
m_stack<Binary_Tree_Node<T>*> s;
if (root == nullptr)
{
cout << "树空" << endl;
return;
}
s.m_push(root);
while (!s.m_empty())
{
Binary_Tree_Node<T>* nd = s.m_pop();
cout << nd->data << ' ';
if (nd->right != nullptr)
{
s.m_push(nd->right);
}
if (nd->left != nullptr)
{
s.m_push(nd->left);
}
}
}
//中序遍历
void mid_Order_non_recursion()
{
m_stack<Binary_Tree_Node<T>*> s;
//用node从根节点开始遍历
if (root == nullptr)
{
return;
}
Binary_Tree_Node<T>* node = root;
Binary_Tree_Node<T>* nd = nullptr;//存储出栈元素
while (!s.m_empty() || node != nullptr)
{
if (node != nullptr)
{
s.m_push(node);
node = node->left;
}
else
{
nd = s.m_pop();
cout << nd->data << ' ';
node = nd->right;
}
}
}
//后序遍历
void last_Order_non_recursion()
{
m_stack<Binary_Tree_Node<T>*> s;
if (root == nullptr)
{
return;
}
Binary_Tree_Node<T>* node = root;
Binary_Tree_Node<T>* nd = nullptr;//存储栈顶元素
Binary_Tree_Node<T>* pre = nullptr;
//需要知道右子树是否被遍历了，所以创建pre
while (!s.m_empty() || node != nullptr)
{
if (node != nullptr)
{
s.m_push(node);
node = node->left;
}
else
{
nd = s.head->next->data;
if (nd->right != nullptr && pre != nd->right)
{
//如果栈顶元素右孩子存在并且没有被访问，遍历右孩子
node = nd->right;
}
else
{
//访问栈顶
nd = s.m_pop();
cout << nd->data << ' ';
pre = nd;
node = nullptr;
}
}
}
}
//线索化，使用递归遍历操作
void visit_thread(Binary_Tree_Node<T>* ro)
{
if (ro->left == nullptr)
{
ro->left = pre_in_thread;
ro->lflag = 1;//加上标记
}
//先判断前驱是否为空
if (pre_in_thread != nullptr && pre_in_thread->right == nullptr)
{
//前驱与后继两两对应，为其前驱加上后继
pre_in_thread->right = ro;
pre_in_thread->rflag = 1;
}
pre_in_thread = ro;
}
//1.如果一个节点其左孩子指针域为空，那么将该指针域指向其前驱节点
//2.如果一个节点其右孩子指针域为空，那么将该指针域指向其后继节点
void mid_threading(Binary_Tree_Node<T>* ro)
{
if (ro == nullptr)
{
return;
}
if (ro->left != nullptr && ro->lflag == 0)
{
mid_threading(ro->left);
}
visit_thread(ro);
if (ro->right != nullptr && ro->rflag == 0)
{
mid_threading(ro->right);
}
}
//避免前序线索化与后续线索化出现死循环，递归时通过lflag与rflag进行判断
//中序遍历不会出现上述情况，但为了格式统一和严谨，也加上
void pre_threading(Binary_Tree_Node<T>* ro)
{
//出口，ro == nullptr
//1.进行线索化
//2.判断根左非空，递归调用，传入ro->left
//3.判断根右非空，递归调用，传入ro->right
if (ro == nullptr)
{
return;
}
visit_thread(ro);
if (ro->left != nullptr && ro->lflag == 0)
{
pre_threading(ro->left);
}
if (ro->right != nullptr && ro->rflag == 0)
{
pre_threading(ro->right);
}
}
void last_threading(Binary_Tree_Node<T>* ro)
{
if (ro == nullptr)
{
return;
}
if (ro->left != nullptr && ro->lflag == 0)
{
last_threading(ro->left);
}
if (ro->right != nullptr && ro->rflag == 0)
{
last_threading(ro->right);
}
visit_thread(ro);
}
//只需要掌握找中序遍历的前驱与后继
//因为先序与后序遍历通过线索化找前驱与后继时效率无明显提升且过于复杂
//某一节点前驱为其左子树最靠右节点
Binary_Tree_Node<T>* Find_mid_pre(T k)
{
Binary_Tree_Node<T>* x = Find(root, k);
if (x != nullptr)
{
if (x->lflag == 1)
{
return x->left;
}
else
{
//找左子树最靠右节点
Binary_Tree_Node<T>* p = x->left;
while (p->right != nullptr && p->rflag == 0)
{
p = p->right;
}
return p;
}
}
}
//某一节点后继为其右子树最靠左节点
Binary_Tree_Node<T>* Find_mid_last(T k)
{
Binary_Tree_Node<T>* x = Find(root, k);
if (x != nullptr)
{
if (x->rflag == 1)
{
return x->right;
}
else
{
//找右子树最靠左节点
Binary_Tree_Node<T>* p = x->right;
while (p->left != nullptr && p->lflag == 0)
{
p = p->left;
}
return p;
}
}
}
public:
//根节点
Binary_Tree_Node<T>* root;
//用于记录线索化时遍历至某一节点的前驱节点
Binary_Tree_Node<T>* pre_in_thread;
};
int main()
{
Binary_Tree<char> tree('A');
/*tree.Left_Insert(15, 100);
tree.Left_Insert(19, 15);
cout << tree.root->data << endl;
cout << tree.root->left->data << endl;
cout << tree.root->left->left->data << endl;*/
tree.Left_Insert('B', 'A');
tree.Right_Insert('C', 'B');
tree.Left_Insert('D', 'C');
tree.Right_Insert('E', 'A');
tree.Right_Insert('F', 'E');
tree.Left_Insert('G', 'F');
tree.Right_Insert('K', 'G');
tree.Left_Insert('H', 'G');
tree.Level_Order();
cout << endl;
tree.pre_Order(tree.root);
cout << endl;
tree.mid_Order(tree.root);
cout << endl;
tree.last_Order(tree.root);
cout << endl;
tree.pre_Order_non_recursion();
cout << endl;
tree.mid_Order_non_recursion();
cout << endl;
tree.last_Order_non_recursion();
cout << endl;
cout << endl;
cout << endl;
tree.mid_threading(tree.root);
Binary_Tree_Node<char>* ans1;
Binary_Tree_Node<char>* ans2;
ans1 = tree.Find_mid_pre('A');
ans2 = tree.Find_mid_last('A');
cout << ans1->data << ' ';
cout << ans2->data << ' ';
return 0;
}