树是n（n>=0）个有限个数据的元素集合，形状像一颗倒过来的树。
结点：结点包含数据和指向其它结点的指针。
结点的度：结点拥有的子节点个数。
叶子节点：没有子节点的节点(度为0)。
父子节点：一个节点father指向另一个节点child，则child为孩子节点，father为父亲结点。
兄弟节点：具有相同父节点的节点互为兄弟节点。
节点的祖先：从根节点开始到该节点所经的所有节点都可以称为该节点的祖先。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
树的高度：树中距离根节点最远结点的路径长度。
树的存储结构：
二叉树:二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
满二叉树:高度为N的满二叉树有2^N - 1个节点的二叉树。
完全二叉树: 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树
前序遍历(先根遍历):
（1）：先访问根节点；
（2）：前序访问左子树；
（3）：前序访问右子树；
中序遍历:
（1）：中序访问左子树
（2）：访问根节点；
（3）：中序访问右子树；
后序遍历(后根遍历):
（1）：后序访问左子树；
（2）：后序访问右子树；
（3）：访问根节点；
层序遍历：
（1）：一层层节点依次遍历。
下面是二叉树的具体实现：
template
struct BinaryTreeNode
{
BinaryTreeNode *_left;
BinaryTreeNode *_right;
T _data;
};
template
class BinaryTree
{
Typedef BinaryTreeNode< T> Node;
protected:
Node *_root;
public:
BinaryTree() //无参构造函数
:_root( NULL)
{
}
BinaryTree( const T *a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreateTree( a, size , invalid, index);
}
protected:
Node *__CreateTree( const T *a, size_t size, const T& invalid, size_t &index )
{
Node *root = NULL;
if (index < size && a[index ] != invalid) //是有效值时
{
root = new Node(a [index]);
root->_left = __CreateTree( a, size , invalid, ++ index);
root->_right = __CreateTree( a, size , invalid, ++index);
}
return root;
}
//前序遍历--------递归写法，缺点是：有大量的压栈开销。
void Prevorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
cout << root->_data << " " ;
_prevorder( root->_left);
_prevorder( root->_right);
}
}
//前序遍历------------非递归写法
//前序遍历的非递归写法思想：需要借助栈。
void PrevOrderRonR()
{
stack s;
if (_root == NULL )//根结点为空的话直接return掉即可。
{
return;
}
if (_root)
{
s.push(_root); //根不为空的时候将根结点进行压栈。
}
while (!s.empty())//判断栈是否为空
{
Node *top = s.top(); //栈不为空，则取栈顶元素
cout << top->_data << " ";//然后进行访问栈顶元素
s.pop(); //访问完栈顶元素将其从栈中pop掉。
if (top->_right)//要根据栈进行先序遍历，则必须是先访问根节点，再访问左子树，最后访问右子树，因为栈是“后进先出的”，要想先访问左子树，则必须先入右子树，再入左子树。如果栈顶元素的右子树不为空，
{
s.push(top->_right); //栈顶的右子树不为空，将其进行压栈。
}
if (top->_left)
{
s.push(top->_left); //栈顶的左子树不为空，将其进行压栈。
}
}
cout << endl;
}
//中序遍历----------递归写法
void _Inorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
_Inorder(Node * root)
{
if (root == NULL )
{
return;
}
else
{
_Inorder(root->_left);
cout << root->_data << " " ;
Inorder(root->_right);
}
}
}
}
//中序遍历的非递归写法，思想是：也是借助栈，主要核心是找最左结点，定义一个cur指针，让它最开始指向_root。
void TnOrderNonR()
{
stack s;
Node *cur = _root;
while (cur || !s.empty())
{
whie(cur) //找最左结点
{
s.push(cur); //将cur压栈。
cur = cur->_left; //cur指向它的左孩子
}
Node *top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;
}
}
//后序遍历---------递归写法
void Postorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
Postorder( root->_left);
Postorder( root->_right);
cout << root->_data << " " ;
}
}
//后序遍历----------非递归写法，思想是：先找最左结点，找到后但不能访问最左结点，要先判断最左结点的右子树是否为空，若为空， 则可以访问最左结点，否则不可以访问最左结点，需要访问右子树。
//可以访问根结点的条件：上一层访问的节点为右子树。所以我们需要定义两个指针prev与cur ，cur用来保存当前结点，prev用来保存上一层访问的结点。
void PostOrderNonR()
{
stack s;
Node *prev = NULL;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)//找最左结点
{
s.push(cur);
cur = cur->_left;
}
Node *top = s.top(); //定义一个栈顶指针，用来指向栈顶元素。
if (top->_right == NULL || top->_right == prev)//栈顶节点的右子树为空或者上一次访问的节点为右子树，则可以访问栈顶元素。
{
cout << top->_data << " " ;
s.pop();
prev = top;
}
else
{
cur = top->_left;
}
}
}
//二叉树的层序遍历（即是一层一层的进行遍历）：思想是：需要借助队列，首先取队头，判断它是否为空，若为空直接return；不为空的时候，进行入队操作。
//如何取到队头？入数据还是入指针？最好入指针，需要保存数据或者节点的时候最好入指针。
void LevelOrder()
{
queue q;
if (_root == NULL )
{
return;
}
q.push(_root);
while (!q.empty())
{
Node *front = q.front(); //取队头元素
q.pop();
cout << front->_data<< " ";
if (front->_left)//队头元素的左孩子不为空的时候，将它的左孩子压入队列
{
q.push(front->_left);
}
if (front->_right)//队头元素的右孩子不为空的时候，将它的右孩子压入队列
{
q.push(front->_right);
}
}
}
size_t _Depth(Node *root )//思想：当前深度=（左子树和右子树中深度较大的一个）+1；
{
if（root == NULL）
{
return 0；
}
int left = _Depth(root->_left);
int right = _Depth(root ->_right);
return left > right ? left + 1 : right + 1;
}
size_t _GetKLevel(Node *root , size_t K)//取第K层结点,递归写法。
{
if (root == NULL)
{
return 0;
}
if (K == 1)
{
return 1;
}
return _GetKLevel(root ->_left, K - 1) + _GetKLevel(root->_right, K - 1);
}
Node* _Find(Node * root, const T& x)//查找结点为x的结点
{
if (root == NULL)
{
return NULL ;
}
if (root ->_data == x)
{
return root ;
}
Node *ret = _Find( root->_left, x );
if (ret)
{
return ret;
}
else
{
return _Find(root ->_right, x);
}
}
size_t _leafsize(Node *root )//求叶子节点的个数,思想：左子树的叶子结点数目+右子树的叶子结点的数目。
{
if (root == NULL)
{
return 0;
}
if (root ->_left == NULL&& root->_right == NULL )
{
return 1;
}
return _leafsize(root ->_left) + _leafsize(root->_right);
}
//递归即是=子问题+返回条件
//方法一：
size_t _size(Node *root )//结点的数目
{
if (root == NULL)
{
return 0;
}
return _size(root ->_left) + _size(root->_right) + 1;
}
//方法二：遍历法
size_t _size(Node *root)
{
static size_t sSize = 0;//此句代码会让程序有线程安全问题
if (root == NULL )
{
return sSize;
}
++sSize;
_size(root->_left);
_size(root->_right);
return sSize;６
}
};
分享名称：二叉树常考面试题
网页URL：
http://www.cdkjz.cn/article/psosig.html
