二叉树结构：

1
2
3
4
5
6
7
template < class  T>
struct  BinaryTreeNode
{
     T _data;  
     BinaryTreeNode<T>* _left;   
     BinaryTreeNode<T>* _right;
}

  1. 前序，中序，后序遍历（递归&非递归）

先写非递归实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
void  PrevOrder_NonR()         //前序非递归
{
     stack<BinaryTreeNode<T>*> s;
     if  (_root)
     {
         s.push(_root);   //将树入栈
     }
     while  (!s.empty())   //栈不为空，根节点先出栈
     {
         BinaryTreeNode<T>* top = s.top();
         s.pop();
         cout << top->_data <<  " " ;
 
 
         if  (top->_right)             //压入右子树
         {
             s.push(top->_right);
         }
 
         if  (top->_left)          //压入左子树
         {
             s.push(top->_left);
         }
     }
 
     cout << endl;
}
 
void  InOrder_NonR()         //中序非递归
{
     stack<BinaryTreeNode<T>*> s;
     BinaryTreeNode<T>* cur = _root;
     while  (cur || !s.empty())
     {
         while  (cur)
         {
             s.push(cur);
             cur = cur->_left;
         }
         if  (!s.empty())
         {
             BinaryTreeNode<T>* top = s.top();
             cout << top->_data <<  " " ;
             s.pop();
 
             cur = top->_right;
         }
     }
 
     cout << endl;
}
 
void  PostOrder_NonR()         //后序非递归
{
     stack<BinaryTreeNode<T>*> s;
     BinaryTreeNode<T>* cur = _root;
     BinaryTreeNode<T>* prevVisited = NULL;
     while  (cur || !s.empty())
     {
         while  (cur)
         {
             s.push(cur);
             cur = cur->_left;
         }
 
         BinaryTreeNode<T>* top = s.top();
         if  (top->_right == NULL || top->_right == prevVisited)
         {
             cout << top->_data <<  " " ;
             prevVisited = top;
             s.pop();
         }
         else
         {
             cur = top->_right;
         }
     }
     cout << endl;
}

再实现递归方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void  _PrevOrder(BinaryTreeNode<T>* root)     //前序
{
     if  (root == NULL)
     {
         return ;
     }
     cout << root->_data <<  " " ;
     _PrevOrder(root->_left);
     _PrevOrder(root->_right);
}
 
void  _InOrder(BinaryTreeNode<T>* root)         //中序
{
     if  (root == NULL)
     {
         return ;
     }
 
     _InOrder(root->_left);
     cout << root->_data <<  " " ;
     _InOrder(root->_right);
}
 
void  _PostOrder(BinaryTreeNode<T>* root)         //后序
{
     if  (root == NULL)
     {
         return ;
     }
 
     _PostOrder(root->_left);
     _PostOrder(root->_right);
     cout << root->_data <<  " " ;
}

2.层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void  _LevelOrder()
{
     queue<BinaryTreeNode<T>*> q;    //定义一个队列q
     if  (_root)          //判断_root是否为空
     {
         q.push(_root);
     }
     while  (!q.empty())
     {
         BinaryTreeNode<T>* front = q.front();
         q.pop();
         cout << front->_data <<  " " ;
 
         if  (front->_left)    //由左向右依次进入队列，依次输出
         {
             q.push(front->_left);
         }
             
         if  (front->_right)
         {
             q.push(front->_right);
         }
     }
 
     cout << endl;
}

3.求二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
12
int  _Depth(BinaryTreeNode<T>* root)
{
     if  (root == NULL)
     {
         return  0;
     }
 
     int  leftDepth = _Depth(root->_left);
     int  rightDepth = _Depth(root->_right);
 
     return  leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

4.求叶子节点的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void  _GetLeafNum(BinaryTreeNode<T>* root,  int & num)
{
     if  (root == NULL)
     {
         return ;
     }
 
     if  (root->_left == NULL&&root->_right == NULL)
     {
         ++num;
         return ;
     }
 
     _GetLeafNum(root->_left, num);
     _GetLeafNum(root->_right, num);
}

5.求二叉树第K层的节点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int  _GetLevelLeafNum( const  BinaryTreeNode<T>* root,  const  int  k)
{
     int  count = 0;
 
     if  (root == NULL || k < 0)
     {
         return  0;
     }
 
     if  (k == 0)
     {
         count++;
     }
 
     _GetLevelLeafNum(root->_left, k - 1);
     _GetLevelLeafNum(root->_right, k - 1);
     return  count;
}

6.判断一个节点是不是在二叉树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BinaryTreeNode<T>* _Find(BinaryTreeNode<T>* root,  const  T& x)
{
     if  (root == NULL)
     {
         return  NULL;
     }
 
     else  if  (root->_data == x)
     {
         return  root;
     }
     else
     {
         BinaryTreeNode<T>* ret = _Find(root->_left, x);
         if  (ret)
         {
             return  ret;
         }
         else
         {
             return  _Find(root->_right, x);
         }
     }
}

7.求两个节点的最近公共祖先

1
2
3
4
int  FindCommonAncestor(BinaryTreeNode<T>* root,BinaryTreeNode<T>* node1, BinaryTreeNode<T>* node2)
{
 
}

8.判断二叉树是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool  _IsBalanceTree(Node* root)
{
     if  (root == NULL)
     {
         return  true ;
     }
     int  left = _Height(root->_left);
     int  right = _Height(root->_right);
 
     int  bf =  abs (right - left);
     if  (bf > 1)
     {
         return  false ;
     }
     else  if  (bf !=  abs (root->_bf))
     {
         cout << root->_bf <<  "平衡因子有误！"  << endl;
         return  false ;
     }
     return  _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

9.求二叉树中最远的两个节点的距离

1
2
3
4
void  MaxDistance()
{
 
}

10. 由前序，中序遍历重建二叉树(前序：1, 2，3, 4, 5, 6；中序：3, 2, 4, 1, 5, 6)

1
2
3
4
5
6
7
8
9
10
11
12
BinaryTreeNode* RebuildBinaryTree( int * pPrevOrder,  int * pInOrder,  size_t  length)
{
     if  (pPrevOrder == NULL || pInOrder == NULL || length <= 0)
     {
         return  NULL;
     }
     return  ConstructCore(pPrevOrder, pPrevOrder + length - 1, pInOrder, pInOrder + length - 1);
}
BinaryTreeNode* ConstructCore( int * startPrevOrder,   int * startInOrder)
{
 
}

11.判断是否是完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool  _IsCompleteBinaryTree(BinaryTreeNode<T>* root)
{
     //空树也算作是完全二叉树
     if  (root == NULL)
         return  true ;
 
     queue<BinaryTreeNode<T>*> q;
     q.push(root);
     bool  NextNoChild =  false ;
     bool  result =  true ;
         
     while (!q.empty())
     {
         BinaryTreeNode<T>* pNode = q.front();
         q.pop();
         if  (NextNoChild)
         {
             if  (pNode->_left != NULL || pNode->_right != NULL)
             {
                 result =  false ;
                 break ;
             }
         }
         else  if  (pNode->_left != NULL && pNode->_right != NULL)
         {
             q.push(pNode->_left);
             q.push(pNode->_right);
         }
         else  if  (pNode->_left != NULL && pNode->_right == NULL)
         {
             q.push(pNode->_left);
             NextNoChild =  true ;
         }
         else  if  (pNode->_left == NULL && pNode->_right != NULL)
         {
             return  false ;
             break ;
         }
         else
         {
             NextNoChild =  true ;
         }
     }
     return  result;
}

12.求二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//递归实现
void  _TreeMirror(BinaryTreeNode<T>* root)
{
     if  (root == NULL || (root->_left == NULL && root->_right == NULL))
     {
         return ;
     }
 
     swap(root->_left, root->_right);
     if  (root->_left)
         _TreeMirror(root->_left);
     if  (root->_right)
         _TreeMirror(root->_right);
}
 
//非递归实现
void  _TreeMirror_NonR(BinaryTreeNode<T>* root)
{
     if  (root == NULL)
     return ;
     stack<BinaryTreeNode<T> *> s;
     s.push(root);
 
     while  (s.size())
     {
         BinaryTreeNode<T>* pNode = s.top();
         s.pop();
 
         if  (NULL != pNode->_left || NULL != pNode->_right)
         {
             BinaryTreeNode<T> *pTemp = pNode->_left;
             pNode->_left = pNode->_right;
             pNode->_right = pTemp;
             //swap(pNode->_left, pNode->_right);
         }
 
         if  (NULL != pNode->_left)
             s.push(pNode->_left);
 
         if  (NULL != pNode->_right)
             s.push(pNode->_right);
     }
}

13.将二叉搜索树转换为双向链表

1
2
3
4
void  ToList()
{
 
}