树相关的一些概念。

树是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<class T>

struct BinaryTreeNode

{

BinaryTreeNode<T > *_left;

BinaryTreeNode<T > *_right;

T _data;

};

template<class T>

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<Node*> 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<Node*> 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<Node*> 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<Node*> 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;６

}

};