1.问题描述：
根据给定的二叉树前序中序遍历结果，重建出这颗二叉树。例如：前序遍历结果：1，2，3，4，5，6。中序遍历结果：3，2，4，1，6，5。
2.问题分析：
我们知道，前序遍历的顺序是：当前结点，左子树，右子树。那么，前序遍历的第一个数字就是根节点。而中序遍历的顺序是：左子树，当前结点，右子树。所以，对于中序序列来说，根节点的左右分别就是左子树的结点和右子树的结点。故，我的做法是：用前序的第一个数建立根节点，从中序中找到前序序列的第一个数的下标，得到中序和前序左子树和右子树的结点序列，拿到了左右子树的前中序序列，那么和之前一样的方法再去建立左右子树。
3.源码：
#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
template<class T>
struct Node
{
T _value;
Node<T>* _left;
Node<T>* _right;
Node(T value)
:_value(value),_left(NULL),_right(NULL)
{}
};
template<class T>
class Rebuild
{
public:
typedef Node<T> Node;
Rebuild(vector<T> InOrder,vector<T> PrevOrder)
{
assert(InOrder.size() == PrevOrder.size());
assert(InOrder.size() != 0);
_root = new Node(PrevOrder[0]);
if (InOrder.size() == 1)
return;
_root=_Rebulid(InOrder,PrevOrder,_root);
}
void PrevOrder()
{
_PrevOrder(_root);
}
protected:
void _PrevOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_value<<" ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
Node* _Rebulid(vector<T>InOrder,vector<T>PrevOrder,Node*& root)
{
if (InOrder.size() == 0)
return NULL;
root = new Node(PrevOrder[0]);
size_t i = 0;
for (; i < InOrder.size(); i++) //找到中序数组里根节点的位置
{
if (InOrder[i] == PrevOrder[0])
break;
}
vector<T> InOrderLeft;
vector<T> InOrderRight;
vector<T> PrevOrderLeft;
vector<T> PrevOrderRight;
size_t j = 0;
for (; j<i; j++)
{
InOrderLeft.push_back(InOrder[j]);
PrevOrderLeft.push_back(PrevOrder[j + 1]);
}
for (size_t k = i + 1; k < InOrder.size(); k++)
{
InOrderRight.push_back(InOrder[k]);
PrevOrderRight.push_back(PrevOrder[k]);
}
root->_left = _Rebulid(InOrderLeft,PrevOrderLeft,root->_left);
root->_right = _Rebulid(InOrderRight,PrevOrderRight,root->_right);
return root;
}
private:
Node* _root;
};
void TestRebuild()
{
int prev[] = { 1,2,3,4,5,6 };
vector<int> PrevOrder(prev,prev+6);
int in[] = { 3,1,6,5 };
vector<int> InOrder(in,in + 6);
Rebuild<int> rb(InOrder,PrevOrder);
rb.PrevOrder();
}
1.问题描述：
求二叉树中最远的两个节点的距离。
2.问题分析：
首先要明确，不能单单去把根节点左右的距离加起来就行。万一是下图这种情况那就有问题了。
所以，我的做法是。后续遍历这颗二叉树，用distence变量记住每一个结点左右树距离的最大值。最后返回即可。
3.源码：
#pragma once
#include<iostream>
using namespace std;
//普通二叉树寻找最远的两个结点的距离
template<class t>
struct binarytreenode
{
binarytreenode(t value = 0)
:_value(value),_right(NULL)
{}
t _value;
binarytreenode<t>* _left;
binarytreenode<t>* _right;
};
template<class t>
class binarytree
{
public:
typedef binarytreenode<t> node;
binarytree()
{}
binarytree(t* a,size_t size,const t& invalid)
{
size_t index = 0;
_root = _creattree(a,size,index,invalid);
}
binarytree(const binarytree<t>& bt)
{
_root = _copy(bt._root);
}
binarytree<t>& operator=(binarytree<t>& bt)
{
if (this != &bt)
{
binarytree<t> tmp(bt);
swap(tmp._root,_root);
}
}
~binarytree()
{
_root = _distory(_root);
}
node* Find(const t& n)
{
return _Find(_root,n);
}
int FindFarthestTwoNode()
{
int distence = 0;
_FindFarthestTwoNode(_root,distence);
return distence;
}
protected:
int _FindFarthestTwoNode(node* root,int& distence)
{
if (NULL == root)
{
distence = 0; //递归到空结点把上一个结点的左右最大距离清为0
return 0;
}
if (root->_left == NULL && root->_right == NULL)
{
return 0;
}
int leftd=_FindFarthestTwoNode(root->_left,distence)+1;
int rightd=_FindFarthestTwoNode(root->_right,distence)+1;
distence = (distence > (leftd + rightd) ? distence : (leftd + rightd)); //更新distence
return leftd > rightd ? leftd : rightd;
}
node* _Find(node* root,const t& n)
{
if (root == NULL)
return NULL;
if (root->_value == n)
return root;
node* left = _Find(root->_left,n);
node* right = _Find(root->_right,n);
return left ? left : right;
}
node* _distory(node* root)
{
if (root)
{
_distory(root->_left);
_distory(root->_right);
node* del = root;
delete del;
}
return root;
}
node* _creattree(t*a,size_t& index,const t& invalid)
{
node* root = NULL;
if ((index < size) && (a[index] != invalid))
{
root = new node(a[index]);
root->_left = _creattree(a,++index,invalid);
root->_right = _creattree(a,invalid);
}
return root;
}
node* _copy(node* copyroot)
{
node* root = NULL;
if (copyroot != NULL)
{
root = new node(copyroot->_value);
root->_left = _copy(copyroot->_left);
root->_right = _copy(copyroot->_right);
}
return root;
}
private:
node* _root;
};
void TestFindNearParent()
{
int array1[15] = { 1,'#',7,8 };
binarytree<int> bt(array1,15,'#');
cout<<bt.FindFarthestTwoNode();
}
1.问题描述：
判断一棵树是否是完全二叉树。
2.问题分析：
完全二叉树有什么特点呢？除最后一层外，其余每一层的结点都是满的，且最后一层结点不间断。如下图
3.源码：
#pragma once
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template<class t>
struct binarytreenode
{
binarytreenode(t value = 0)
:_value(value),_root);
}
}
~binarytree()
{
_root = _distory(_root);
}
bool IsCompleteTree() //判断是否是完全二叉树
{
queue<node*> q;
q.push(_root);
node* cur = q.front();
while ((cur = q.front()) != NULL) //当前结点不为空则push进它的左右
{
q.push(cur->_left);
q.push(cur->_right);
q.pop();
}
while (!q.empty()) //到这里说明取到了一个空结点，判断剩下的是否有不为空的结点。
{
cur = q.front();
if (cur != NULL)
return false;
q.pop();
}
return true;
}
protected:
node* _distory(node* root)
{
if (root)
{
_distory(root->_left);
_distory(root->_right);
node* del = root;
delete del;
}
return root;
}
node* _creattree(t*a,invalid);
}
return root;
}
node* _copy(node* copyroot)
{
node* root = NULL;
if (copyroot != NULL)
{
root = new node(copyroot->_value);
root->_left = _copy(copyroot->_left);
root->_right = _copy(copyroot->_right);
}
return root;
}
private:
node* _root;
};
void TestIsCompleteTree()
{
int array[10] = { 1,6 };
int array1[15] = { 1,'#');
cout<<bt.IsCompleteTree();
}
1.问题描述：
求二叉树两个节点的最近公共父节点。
2.问题分析：
当这棵树是一个二叉搜索树的时候，可以利用二叉搜索树的性质。从根节点找，若当前结点比两个结点中小的那个大，比大的那个小。说明当前结点就是最近的公共父节点。若当前结点比传进来的两个数都大，说明公共父节点在当前结点的左树上，那么向左树去找；若比两个数都小，说明公共父节点在当前结点的右树上，向右树去找。
当这棵树是一颗普通的二叉树的时候，一种做法是保存找到两个结点的路径，存到两个链表里，再去找两个链表的第一个交点。这种方法简单粗暴，但是空间复杂度近似于O(n^2)。另一种方法是，递归去找传进来的两个结点，若找到了则返回。那么如果分别在当前结点的左右找到，那就返回当前结点，说明当前结点就是最近的公共父节点。若左右有一个为空，说明不为空的那个就是最近的公共父节点。
3.源码：
#pragma once #include<iostream> using namespace std; //二叉搜索树找最近的公共父节点 template<class K> struct SelectBinaryTreeNode { typedef SelectBinaryTreeNode<K> Node; K _key; Node* _left; Node* _right; SelectBinaryTreeNode(const K& key) :_key(key),_right(NULL) {} }; template<class K> class SelectBinaryTree { public: typedef SelectBinaryTreeNode<K> Node; SelectBinaryTree() {} ~SelectBinaryTree() //析构，递归实现 { _Destory(_root); } bool Insert(const K& key) //非递归插入 { if (NULL == _root) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = NULL; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key>key) { parent = cur; cur = cur->_left; } else return false; } if (parent->_key < key) { parent->_right = new Node(key); } else parent->_left = new Node(key); return true; } bool InsertR(const K& key) //递归插入 { return _InsertR(_root,key); } Node* Find(const K& k) { return _FindR(_root,k); } K FindNearestParent(const K& key1,const K& key2) { Node* node1 = Find(key1); Node* node2 = Find(key2); if (node1 == NULL || node2 == NULL) { return -1; } K min = 0; K max = 0; if (key1 > key2) { min = key2; max = key1; } else { min = key1; max = key2; } Node* cur = _root; while (cur) { if (cur->_key >= min && cur->_key <= max) { return cur->_key; } else if (cur->_key <= min && cur->_key <= max) { cur = cur->_right; } else { cur = cur->_left; } } return -1; } protected: Node* _FindR(Node* root,const K& key) { if (NULL == root) return NULL; if (root->_key == key) return root; else if (root->_key < key) _FindR(root->_right,key); else if (root->_key>key) _FindR(root->_left,key); } bool _InsertR(Node*& root,const K& key) { if (NULL == root) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right,key); else if (root->_key>key) return _InsertR(root->_left,key); else return false; } void _Destory(Node* root) { Node* cur = root; while (cur) { Node* del = cur; cur = cur->_right; delete del; } } private: Node* _root; }; void TestFindNearestParent() { SelectBinaryTree<int> sbt; int a[] = { 5,8,9 }; for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++) { sbt.InsertR(a[i]); } cout << sbt.FindNearestParent(8,9) << endl; } 普通二叉树寻找最近的父节点 template<class t> struct binarytreenode { binarytreenode(t value = 0) :_value(value),n); } t FindNearParent(const t& n1,const t& n2) { node* node1 = Find(n1); node* node2 = Find(n2); if (node1 == NULL || node2 == NULL) //若传过来的结点不在树内 { throw std::invalid_argument("结点不在树内"); } node* ret=_FindNearParent(_root,node1,node2); return ret->_value; } protected: node* _FindNearParent(node* root,node* n1,node*n2) { if (NULL == root) return NULL; if (root == n1 || root == n2) //找到了其中一个结点 { return root; } node* left = _FindNearParent(root->_left,n1,n2); node* right = _FindNearParent(root->_right,n2); if (left&&right) //left和right都存在，说明结点分别在root的左右 { return root; } return left ? left : right; //左右哪个不为空返回哪个，说明两个结点都在一侧 } node* _Find(node* root,const t& n) { if (root == NULL) return NULL; if (root->_value == n) return root; node* left=_Find(root->_left,n); node* right=_Find(root->_right,n); return left ? left : right; } node* _distory(node* root) { if (root) { _distory(root->_left); _distory(root->_right); node* del = root; delete del; } return root; } node* _creattree(t*a,invalid); } return root; } node* _copy(node* copyroot) { node* root = NULL; if (copyroot != NULL) { root = new node(copyroot->_value); root->_left = _copy(copyroot->_left); root->_right = _copy(copyroot->_right); } return root; } private: node* _root; }; void TestFindNearParent() { int array1[15] = { 1,8 }; binarytree<int> bt(array1,'#'); try{ cout << bt.FindNearParent(0,8); } catch (exception &e) { cout << e.what() << endl; } }
1.问题描述：
将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
2.问题分析：
这个问题其实和二叉树的线索化有些类似，根据二叉搜索树的性质，中序遍历的结果就是一个有序的数组，所以我们中序去做。二叉树原来的左指向默认为双向链表的前驱指针，有指向默认为next指针。做法是：定义一个prev指针，递归去让prev的左指向当前结点，如若prev不为空，则prev的右指向当前结点，再去更新prev。要注意的是，二叉搜索树被转换成双向链表之后，它的析构函数必须要重新写，变成链表的析构，否则会导致栈溢出。
3.源码：
#pragma once
#include<iostream>
using namespace std;
template<class K>
struct SelectBinaryTreeNode
{
typedef SelectBinaryTreeNode<K> Node;
K _key;
Node* _left;
Node* _right;
SelectBinaryTreeNode(const K& key)
:_key(key),_right(NULL)
{}
};
template<class K>
class SelectBinaryTree
{
public:
typedef SelectBinaryTreeNode<K> Node;
SelectBinaryTree()
{}
~SelectBinaryTree() //析构，递归实现
{
_Destory(_root);
}
void TodoubleLink() //二叉搜索树转化成双向链表
{
Node* prev = NULL;
_TodoubleLink(_root,prev);
Node* head = _root;
while (head->_left)
{
head = head->_left;
}
_root = head;
while (head)
{
cout << head->_key << " ";
head = head->_right;
}
cout << endl;
}
bool Insert(const K& key) //非递归插入
{
if (NULL == _root)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
return false;
}
if (parent->_key < key)
{
parent->_right = new Node(key);
}
else
parent->_left = new Node(key);
return true;
}
bool InsertR(const K& key) //递归插入
{
return _InsertR(_root,key);
}
protected:
Node* _TodoubleLink(Node* root,Node*& prev)
{
if (root == NULL)
return NULL;
Node* cur = root;
_TodoubleLink(cur->_left,prev);
cur->_left = prev;
if (prev)
prev->_right = cur;
prev = cur;
_TodoubleLink(cur->_right,prev);
return root;
}
bool _InsertR(Node*& root,key);
else
return false;
}
void _Destory(Node* root)
{
Node* cur = root;
while (cur)
{
Node* del = cur;
cur = cur->_right;
delete del;
}
}
private:
Node* _root;
};
void TestTodoubleLink()
{
int a[] = { 5,0 };
SelectBinaryTree<int> sbt;
for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
sbt.InsertR(a[i]);
}
sbt.TodoubleLink();
}
