二叉查找树转双链表（c++）
需求就是一个二叉树查找树 ，要转成按顺序排列的双向链表
思路差不多就是：中序可以按顺序输出；左儿子指针指向相邻小的，右儿子指针指向相邻大的；相邻由中序控制,左右儿子改动的时候寄存在pre(前驱)和root(当前)下
关键代码
定义模版类及head pre指针
template<class T> //模版结构体
struct TreeNode
{
T data; //节点的内容
TreeNode <T> *Lchild, *Rchild,*pParent; //节点的左子树和右子树
//可选择参数的默认构造函数
TreeNode(T nodeValue = T(), TreeNode<T> *leftNode = NULL, TreeNode<T> *rightNode = NULL, TreeNode<T> *parentNode = NULL)
:data(nodeValue),Lchild(leftNode),Rchild(rightNode),pParent(parentNode){}
};
TreeNode<int> * pHead =NULL;//存放头指针
TreeNode<int> * previous = NULL;//存放前驱
核心转换代码
template<class T>
void Tranverse(TreeNode<T> * root)//记前序
{
if (root){
Tranverse(root->Lchild);//很明显的中序遍历阿！
if (previous){
if (!pHead){//这个if可以不写啊 只是为了记录头结点而已
pHead = previous;
}
previous->Rchild = root;//前驱的右指针指向root
root->Lchild = previous;//root的左指针指向前驱
}
previous = root;//前驱跑到下一个更新
Tranverse(root->Rchild);
}
}
调用代码,我才懒得写insert代码啊，rootNode从哪里来的我也不管啊
Tranverse(rootNode);
while (pHead != NULL){
cout << pHead->data << endl;
pHead = pHead->Rchild;
}
代码见这里
在二叉查找树里查找范围内数据(c++)
二叉查找树对于范围查找效率比普通线性查找效率高，Point仍旧是中序按序输出。
思路：这次换一个c语言方式类typedef定义二叉树模版，以二叉按次序找到下限第一个，然后其后的数据与最大最小值比较，在范围内就输出。因此，在二叉查找树中序输出中中，加两个判断条件
- 进入左子树需要根节点比最小值大
- 进入右子树需要根节点比最大值小
类模版定义
typedef int KeyType;
typedef struct TreeNode
{
KeyType key; //关键字
struct TreeNode * left; //左孩子指针
struct TreeNode * right; //右孩子指针
struct TreeNode * parent; //指向父节点指针
}TreeNode, *PNode;
关键代码 以范围搜索
set<KeyType> searchRange(KeyType min, KeyType max, set<KeyType> &vt, TreeNode *root){
if (!root) return vt ;
if (min < root->key)
searchRange(min, max, vt,root->left);
if (min <= root->key && max >= root->key){
vt.insert(root->key);
}
if (max>root->key)
searchRange(min, max, vt,root->right);
return vt;
}
调用代码
set<int> ss = set<int>();
//很多地方都会把set带进函数迭代传递
ss = searchRange(0, 3, ss, root);
cout << "vv.size() "<<ss.size()<<endl<<"范围内包含节点有:"<<endl;
for each (int item in ss)
{
cout << item<<" ";
}
代码见这里
输出(平衡)二叉树所有和为某值的路径
需求：一条路径就是从根到叶子所有节点，路径数就是叶子数。要输出所有满足路径上所有节点和为某值的路径。
思路：为了保证效率，不能每次从头遍历到每个叶子才输出一次。
- 使用栈压入根到当前节点的路径所有制，以便求和
- 栈和超过值可以不继续寻找当前路径的儿子
- 找一个儿子就在栈压入一个数值，跳回一个根就弹出一个儿子的值
当然，我很无聊，试一试平衡二叉(AVL).平衡二叉防止了直接建立查找二叉时候的随机，保证了时间复杂式始终在log(n).但建立AVL时候的插入删除代价也相对较大。
AVL模版类的声明，多了一个height（高度）属性。
template <class T>
class AVLTreeNode{
public:
T key; // 关键字(键值)
int height; // 高度
AVLTreeNode *left; // 左孩子
AVLTreeNode *right; // 右孩子
//构造函数
AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r) :
key(value), height(0), left(l), right(r) {}
};
AVLtree类中包含了函数声明和一个AVLTreeNode<T> *mRoot;作为根节点；一个public的函数void SearchPath(const T value);给外部调用；一个private的函数void SearchPath(AVLTreeNode<T>* root, T* seq, T top, T sumCount, const T value);作为自迭代的函数，传入当前节点指针，当前线性表指针，栈顶指针(栈压入的数目)，当前和以及目标值。
关键代码，使用的是栈，但其实就是个顺序表，系统自动建立内存空间，每次进栈自增。
公有函数
template<class T>
void AVLTree<T>::SearchPath(const T value){
T * seq = new int[0];
T sumCount = 0;//当前累积值
T top = 0;
return SearchPath(mRoot, seq, top, sumCount, value);
}
私有函数
//遍历次序无所谓的 反正要遍历所有叶子
template<class T>
void AVLTree<T>::SearchPath(AVLTreeNode<T>* root, T* seq, T top, T sumCount, const T value)//按值传递回溯不用恢复参数值和栈顶
{
seq[top++] = root->key;//入栈
sumCount += root->key;//累加和
//if(sumCount > value) return;//当值为正数时可加上这句话
if (root->left == NULL && root->right == NULL){//为叶子节点
if (sumCount == value)
for (int i = 0; i<top; i++)
cout << seq[i] << " ";
}
else{
if (root->left)
SearchPath(root->left, seq, top, sumCount, value);
if (root->right)
SearchPath(root->right, seq, top, sumCount, value);
}
}
调用代码
AVLTree<int>* tree = new AVLTree<int>();
int const value = 16;//目标和
tree->SearchPath(value);
代码见这里
求树高的几种方式
首先定义一波树结构属性名字
typedef struct TreeNode{
char data;
struct TreeNode *lchild, *rchild;
}TreeNode, *BiTree;
后序遍历，栈求高，最大栈长度为树高
思路：进左右子则入栈，返回根节点则出栈。每次左右子树检查完毕就比较一次栈长度是否大于最大高度
int BT_high(BiTree T){
BiTree p = T, r = NULL;
int max = 0;//记录最大树高
stack<BiTree> s;//声明一个堆 存放树根节点
while (p || !s.empty()){//节点非空且堆栈非空
if (p != NULL){
s.push(p);//入栈
p = p->lchild;
}
else{
p = s.top();
if (p->rchild != NULL && p->rchild != r)
//判断是否从右子树返回根
p = p->rchild;
else{//左右子树都算完了 比较一下
if (s.size()>max) max = s.size();//最大层次即为高度
r = p;
s.pop();//出栈
p = NULL;
}
}
}
return max;
}
层次遍历 层高即树高
层次遍历服用队列或堆栈效果更佳！
层次遍历-单数组
思路：按层将树输入到数组，下标记下本层元素头尾，从头遍历到尾加入它们的儿子，不断循环
int BT_level_depth(BiTree T)
{
if (!T) return 0;
BiTree p = T, Q[100];//队列
int front = -1, rear = -1, last = 0, level = 0;
//定义首指针 尾指针 上层尾元素 当前高度
Q[++rear] = p;//入队列
while (front<rear){
p = Q[++front];//先设置本次循环的根
if (p->lchild)//加入根的左儿子 同时移动尾
Q[++rear] = p->lchild;
if (p->rchild)//加入根的右儿子 同时移动尾
Q[++rear] = p->rchild;
if (front == last){//当头指针遍历完本层所有元素
last = rear;
level++;//层次+1
}
}
return level;
}
层次遍历-双端队列
思路：按层将树输入到双端队列，一个队列记录上一层所有节点，另一个队列加入所有另一个队列的儿子，不断交替。
int BT_level_depth222(BiTree T)
{
int max = 0;
deque<TreeNode*> q_first, q_second;
q_first.push_back(T);
while (!q_first.empty()) {
while (!q_first.empty()) {
TreeNode *temp = q_first.front();
q_first.pop_front();
cout << (int)temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
max++;
q_first.swap(q_second);
}
return max;
}
递归求树高
后序递归带深度求高
思路:后序遍历所有节点，递归调用并检查当前节点是否为最大值。
int max1 = 0;//树高
int BT_depth1(BiTree T, int depth)
{
if (T)
{
if (T->lchild)
BT_depth1(T->lchild, depth + 1);
if (T->rchild)
BT_depth1(T->rchild, depth + 1);
}
if (depth>max1)
max1 = depth;
return depth;
}
左右子树递归求树高
思路： 求左右子树的高度，分别又把左右子树当做根求他们的子树。每次迭代返回当前左右子树高的那一个。
int Height(BiTree T)
{
if (T == NULL) return 0;
else
{
int m = Height(T->lchild);
int n = Height(T->rchild);
return (m > n) ? (m + 1) : (n + 1);
}
}
代码见这里