@yudesong 2017-06-24T15:07:50.000000Z 字数 12605 阅读 607

树

树 yudesong 2017/6/24

二叉树

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>  
using namespace std;
typedef struct Node
{
    char data;
    struct Node *left,*right;
}BTree;
BTree* CreateTree(BTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')  T=NULL;
    else
    {
        T=(BTree *)malloc(sizeof(BTree));
        T->data = ch;
        T->left = CreateTree(T->left); 
        T->right = CreateTree(T->right);
    }
    return T;
}
void PreOrder(BTree *T)
{
    if(T)
    {
        printf("%c",T->data);
        PreOrder(T->left);
        PreOrder(T->right);
    }
}
//先序遍历非递归算法 
void PreOrder1(BTree *T) 
{
    int top = -1;    
    BTree *p;
    BTree *Str[100];
    if(T!=NULL)
    {
        top++;
        Str[top] = T;
        while(top>-1)
        {
            p = Str[top];
            printf("%c",p->data);
            top--;
            if(p->right!=NULL) 
            {
                top++;
                Str[top] = p->right;
            }
            if(p->left!=NULL) 
            {
                top++;
                Str[top] = p->left;
            }
        }
    }
}
void CengCi(BTree *T) 
{
    int font,rear;
    BTree *Str[10];
    BTree *p;
    font=rear=-1;
    if(T)
    {
        rear = (rear+1)%10;
        Str[rear] = T;
        while(font!=rear)
        {
            font = (font+1)%10;
            p = Str[font];
            printf("%c",p->data);
            if(p->left)
            {
                rear=(rear+1)%10;
                Str[rear] = p->left; 
            }
            if(p->right)
            {
                rear=(rear+1)%10;
                Str[rear] = p->right; 
            }       
        }
    }
}
int sumLeaf(BTree *T)
{
    int sum=0,l=0,r=0;
    if(T)
    {
      if(T->left==NULL&&T->right==NULL)
      sum++;
      l = sumLeaf(T->left);
      sum+=l;
      r = sumLeaf(T->right);
      sum+=r;         
    }
    return sum;
}
int deapTree(BTree *T)
{
    int deap,ldeap,rdeap;  
    if(T== NULL) deap = 0;
    else
    {
      ldeap = deapTree(T->left);
      rdeap = deapTree(T->right);
      deap = 1+(ldeap>rdeap? ldeap:rdeap);
    }
    return deap;
}
BTree* invertTree(BTree *T)
{
    if(T==NULL) return NULL;
    BTree *node = invertTree(T->left);
    T->left = invertTree(T->right);
    T->right = node;
    return T;
}
BTree* invertTree1(BTree *T)
{
    if(T==NULL)  return NULL;
    stack<BTree*> stack;
    stack.push(T);
    while(!stack.empty())
    {
      BTree *p = stack.top();
      stack.pop();
      BTree *tmp;
      tmp = p->left;
          p->left = p->right;
      p->right = tmp;
      if(p->left) stack.push(p->left);
      if(p->right) stack.push(p->right);
    }
    return T;
}
bool isEqual(BTree *T1,BTree *T2)
{
    if(T1==NULL && T2==NULL) return 1;
    if(T1==NULL || T2==NULL) return 0;
    if(T1->data==T2->data)
    {
return isEqual(T1->left,T2->left)&&isEqual(T1->right,T2->right);
    }   
    else
     return 0;
}
int main()
{ 
    BTree *T; 
    T = CreateTree(T);
//  T = invertTree(T);
    // ABC##DE#G##F###
//  421##3##76##9##
//  PreOrder(T);
//  PreOrder1(T);
    CengCi(invertTree1(T));
    printf("\n%d",sumLeaf(T));
    printf("\n%d",deapTree(T));
    return 0;
}

构造哈夫曼树

/*
根据Huffman树的构造原理进行构造  ... 
哈夫曼树在编码压缩的领域有很好的应用,利用Huffman进行编码可以保证
数据传输的无二义性 。
但是要注意的是 对于出现频率大的数据我们应该尽量放在离根节点近的
地方进行编码 ,出现频率小的数据我们可以放在距离根节点小的地方。
这样可以提高数据的传输效率 。
*/
#include "stdio.h"
#include "malloc.h" 
///节点声明
typedef struct  node{
    node *lChild ;
    node *rChild ;
    int data ;//权值
}TreeNode ; 
//数组a表示权的数组  n是个数
TreeNode * CreateHuffmanTree(int a[],int n)  ;  
 //查找出2个权值最小的节点的下标 
void  FindLittle(int *x1,int *x2 ,TreeNode**pArr,int n)  ;
//数组a表示权的数组  n是个数
TreeNode * CreateHuffmanTree(int a[],int n)    
{      
        //动态产生指针数组
    TreeNode**pArr=(TreeNode**)malloc(sizeof(TreeNode*)*n);  
    TreeNode*p =NULL;//用于返回哈夫曼树的根节点的指针 
    int k1,k2 ;  
        //k1代表最小权  k2代表次小权  
        //用于做为 FindLittle的参数查找最小权下标
    for(int i=0;i<n;i++)
    {
        pArr[i]=new TreeNode ;    
               //为节点指针数组动态分配指向的对象
        pArr[i]->data=a[i]  ;
        pArr[i]->lChild=pArr[i]->rChild=NULL ;
               //初始化每个节点的左右节点都是空    
    }
//因为哈夫曼树是循环的从节点数组中找出权值最小的两个节点进行组合 
//并从数组中删除这两个节点,并把合并后的节点添加到数组中。
    for(i=0;i<n-1;i++) //因为最后还剩下一个节点所以就会挑选n-1次 
    {
        FindLittle(&k1,&k2,pArr,n) ; //查找2个最小权节点下标 
        p=new TreeNode;   
                //循环组合最后的p指向的节点便是最终的pRoot 
        p->data=pArr[k1]->data+pArr[k2]->data  ;
        p->lChild=pArr[k1] ;
        p->rChild=pArr[k2] ;  
         //将合并后的新节点赋值给pArr最小的那个下标
        pArr[k1]=p    ;  
        pArr[k2]=NULL ;   
// 次下标设置NULL, k1和k2也可以反过来这个具体我们自己定
    }
    free(pArr) ;//释放指针数组  
    return p;  
}
//查找出2个权值最小的节点的下标
void  FindLittle(int *x1,int *x2 ,TreeNode**pArr,int n)  
{
    int  k1,k2;  //保存权最小的两个节点下标 
    k1=-1 ; //表示没有找到数据
        //找出其中的前两个元素不为NULL的下标
    for(int i=0;i<n;i++)    
    {  
        if(pArr[i]!=NULL&&k1==-1)
        {
            k1=i ;     //第一个下标
            continue ;
        }
        if(pArr[i]!=NULL) 
        {
            k2=i ;
            break;//找到第二个下标退出循环
        }
    }
    ////// 最小权的2个下标的搜索实现//////////    
//我们是先获取k1  后获取k2所以一开始 一定是从k2开始循环的   
        for(i=k2;i<n;i++)  
    { 
    if(pArr[i]!=NULL)
    {
        //如果下标k1的权 小于当前下标的元素的权 
        if(pArr[i]->data<pArr[k1]->data )  
        {  
            k2=k1;  //此时还是k1<k2满足我们返回的结果
            k1=i ;
        }
        else if(pArr[i]->data<pArr[k2]->data)
        {
            k2=i ;
        }
    }    
    }
    *x1=k1  ;
    *x2=k2  ;
}
///哈夫曼树的先序遍历 
void PreHufOrder(TreeNode*p)   //先序遍历
{  
    if(p!=NULL)
    {
        printf("%d ",p->data) ; 
        PreHufOrder(p->lChild) ;
        PreHufOrder(p->rChild) ;
    } 
}
//中序遍历  
void InHufOrder(TreeNode*p)
{
       if(p!=NULL)
       {
           InHufOrder(p->lChild) ;
           printf("%d ",p->data) ;
           InHufOrder(p->rChild) ;
       }
}
//后续遍历 
void PostHufOrder(TreeNode*p)
{
    if(p!=NULL)
    {
        InHufOrder(p->lChild) ;
        InHufOrder(p->rChild) ;
        printf("%d ",p->data) ;
    }
}
//清空树  
void ClearHufTree(TreeNode*p)
{
    if(p!=NULL)
    {
        ClearHufTree(p->lChild) ;
        ClearHufTree(p->rChild) ;
        delete p ;
    }
}
int main()
{
    int a[]={3,5,3,8,7,9,4,2,4,5,6,3,2,3} ;  //权值 
     //创建huffman树
    TreeNode*p=::CreateHuffmanTree(a,sizeof(a)/sizeof(int)) ;
    printf("Huffman前序遍历:\n") ;
    PreHufOrder(p) ;  //前序遍历huffmanTree
    printf("\n");
    printf("Huffman后序遍历:\n") ;
    PostHufOrder(p) ;//后序遍历
    printf("\n");
    printf("Huffman中序遍历:\n") ;
    InHufOrder(p) ;//中序遍历
    printf("\n");
    ClearHufTree(p) ;//清空树
    return  0 ;
}

1. 求二叉树中的节点个数

递归解法：（1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

参考代码如下：

int GetNodeNum(BinaryTreeNode * pRoot)
{
  if(pRoot == NULL) // 递归出口
  return 0;
  return GetNodeNum(pRoot->m_pLeft)+GetNodeNum(pRoot->m_pRight)+1;
}

2. 求二叉树的深度

递归解法：（1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度，右子树深度) + 1

参考代码如下：

int GetDepth(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL) // 递归出口  
        return 0;  
 int depthLeft = GetDepth(pRoot->m_pLeft);  
 int depthRight = GetDepth(pRoot->m_pRight);  
 return depthLeft>depthRight?(depthLeft+1):(depthRight+1);   
}

3. 前序遍历，中序遍历，后序遍历前序遍历

递归解法：（1）如果二叉树为空，空操作（2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树

参考代码如下：

void PreOrderTraverse(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return;  
    Visit(pRoot); // 访问根节点  
    PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树  
    PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树  
}

中序遍历递归解法（1）如果二叉树为空，空操作。（2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树

参考代码如下：

void InOrderTraverse(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return;  
    InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树  
    Visit(pRoot); // 访问根节点  
    InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树  
}

后序遍历递归解法（1）如果二叉树为空，空操作（2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点

参考代码如下：

void PostOrderTraverse(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return;  
    PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树  
    PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树  
    Visit(pRoot); // 访问根节点  
}

4.分层遍历二叉树

（按层次从上往下，从左往右）相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

void LevelTraverse(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return;  
    queue<BinaryTreeNode *> q;  
    q.push(pRoot);  
    while(!q.empty())  
    {  
        BinaryTreeNode * pNode = q.front();  
        q.pop();  
        Visit(pNode); // 访问节点  
        if(pNode->m_pLeft != NULL)  
            q.push(pNode->m_pLeft);  
        if(pNode->m_pRight != NULL)  
            q.push(pNode->m_pRight);  
    }  
    return;  
}

5. 将二叉查找树变为有序的双向链表要求不能创建新节点，只调整指针

递归解法：（1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL （2）如果二叉查找树不为空：如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作；如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链表的最后一个节点连接；如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作；如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连接。参考代码如下：

/************************************************************
参数：
pRoot: 二叉查找树根节点指针
pFirstNode: 转换后双向有序链表的第一个节点指针
pLastNode: 转换后双向有序链表的最后一个节点指针
************************************************************/
void Convert(BinaryTreeNode * pRoot, 
 BinaryTreeNode *&pFirstNode,BinaryTreeNode *&pLastNode)
{
BinaryTreeNode *pFirstLeft,*pLastLeft,*pFirstRight,*pLastRight;
  if(pRoot == NULL) 
  {
   pFirstNode = NULL;
   pLastNode = NULL;
   return;
  }
  if(pRoot->m_pLeft == NULL)
  {
    //如果左子树为空，对应双向有序链表的第一个节点是根节点
    pFirstNode = pRoot;
  }else
  {
   Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);
   //二叉查找树对应双向有序链表的第一个节点就是左子树转换
   //后双向有序链表的第一个节点
   pFirstNode = pFirstLeft;
// 将根节点和左子树转换后的双向有序链表的最后一个节点连接
   pRoot->m_pLeft = pLastLeft;
   pLastLeft->m_pRight = pRoot;
  }
  if(pRoot->m_pRight == NULL)
  {
   //对应双向有序链表的最后一个节点是根节点
   pLastNode = pRoot;
   }else
   {
    Convert(pRoot->m_pRight, pFirstRight, pLastRight);
//对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点
    pLastNode = pLastRight;
    // 将根节点和右子树转换后的双向有序链表的第一个节点连接
    pRoot->m_pRight = pFirstRight;
    pFirstRight->m_pLeft = pRoot;
   }
   return;
}

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

递归解法：（1）如果二叉树为空或者k<1返回0 （2）如果二叉树不为空并且k==1，返回1 （3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

参考代码如下：

int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)  
{  
    if(pRoot == NULL || k < 1)  
        return 0;  
    if(k == 1)  
        return 1;  
     // 左子树中k-1层的节点个数 
    int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); 
    // 右子树中k-1层的节点个数  
    int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); 
    return (numLeft + numRight);  
}

7. 求二叉树中叶子节点的个数

递归解法：（1）如果二叉树为空，返回0 （2）如果二叉树不为空且左右子树为空，返回1 （3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数

参考代码如下：

int GetLeafNodeNum(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return 0;  
    if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)  
        return 1;  
    // 左子树中叶节点的个数
    int numLeft = GetLeafNodeNum(pRoot->m_pLeft);   
    // 右子树中叶节点的个数  
    int numRight = GetLeafNodeNum(pRoot->m_pRight);
    return (numLeft + numRight);  
}

8. 判断两棵二叉树是否结构相同不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。

递归解法：（1）如果两棵二叉树都为空，返回真（2）如果两棵二叉树一棵为空，另一棵不为空，返回假（3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假

参考代码如下：

bool StructureCmp(BinaryTreeNode *pRoot1,BinaryTreeNode *pRoot2)  
{  
// 都为空，返回真
if(pRoot1 == NULL && pRoot2 == NULL) return true;  
// 有一个为空，一个不为空，返回假  
else if(pRoot1 == NULL || pRoot2 == NULL) return false;  
// 比较对应左子树  
bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); 
// 比较对应右子树  
bool resultRight=StructureCmp(pRoot1->m_pRight,pRoot2->m_pRight);
return (resultLeft && resultRight);  
}

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

递归解法：（1）如果二叉树为空，返回真（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

参考代码：

bool IsAVL(BinaryTreeNode * pRoot, int & height)  
{  
    if(pRoot == NULL) // 空树，返回真  
    {  
        height = 0;  
        return true;  
    }  
    int heightLeft;  
    bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);  
    int heightRight;  
    bool resultRight = IsAVL(pRoot->m_pRight, heightRight);  
     // 左子树和右子树都是AVL，并且高度相差不大于1，返回真  
    if(resultLeft&&resultRight&&abs(heightLeft-heightRight)<=1)
    {  
        height = max(heightLeft, heightRight) + 1;  
        return true;  
    }  
    else  
    {  
        height = max(heightLeft, heightRight) + 1;  
        return false;  
    }  
}

10. 求二叉树的镜像

递归解法：（1）如果二叉树为空，返回空（2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树

参考代码如下：

BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL) // 返回NULL  
        return NULL;  
    BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); 
    BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); 
        // 交换左子树和右子树  
    pRoot->m_pLeft = pRight;  
    pRoot->m_pRight = pLeft;  
    return pRoot;  
}

11. 求二叉树中两个节点的最低公共祖先节点

递归解法：（1）如果两个节点分别在根节点的左子树和右子树，则返回根节点（2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树

参考代码如下：

bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)  
{  
 if(pRoot == NULL || pNode == NULL) return false;  
 if(pRoot == pNode) return true;  
 bool found = FindNode(pRoot->m_pLeft, pNode);  
 if(!found) found = FindNode(pRoot->m_pRight, pNode);
 return found;  
}  
BinaryTreeNode *GetLastCommonParent(BinaryTreeNode *pRoot,
   BinaryTreeNode * pNode1,BinaryTreeNode * pNode2)  
{  
 if(FindNode(pRoot->m_pLeft, pNode1))  
 {  
  if(FindNode(pRoot->m_pRight, pNode2))  
     return pRoot;  
  else  
    return GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);  
 }else{  
    if(FindNode(pRoot->m_pLeft, pNode2)) return pRoot;  
    else  
    return GetLastCommonParent(pRoot->m_pRight,pNode1,pNode2);  
 }  
}

12. 求二叉树中节点的最大距离即二叉树中相距最远的两个节点之间的距离

递归解法：（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0 （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。

参考代码如下：

int GetMaxDistance(BinaryTreeNode*pRoot,int&maxLeft,int &maxRight)
{
    // maxLeft, 左子树中的节点距离根节点的最远距离
    // maxRight, 右子树中的节点距离根节点的最远距离
    if(pRoot == NULL)
    {
        maxLeft = 0;
        maxRight = 0;
        return 0;
    }
    int maxLL, maxLR, maxRL, maxRR;
    int maxDistLeft, maxDistRight;
    if(pRoot->m_pLeft != NULL)
    {
    maxDistLeft=GetMaxDistance(pRoot->m_pLeft,maxLL, maxLR);
    maxLeft = max(maxLL, maxLR) + 1;
    }
    else
    {
        maxDistLeft = 0;
        maxLeft = 0;
    }
    if(pRoot->m_pRight != NULL)
    {
    maxDistRight = GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);
    maxRight = max(maxRL, maxRR) + 1;
    }
    else
    {
        maxDistRight = 0;
        maxRight = 0;
    }
return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);
}

13. 由前序遍历序列和中序遍历序列重建二叉树

二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。递归解法：（1）如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。（2）创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍历序列，重建左右子树。

BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{
    if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
        return NULL;
    BinaryTreeNode * pRoot = new BinaryTreeNode;
    // 前序遍历的第一个数据就是根节点数据
    pRoot->m_nValue = pPreOrder[0];
    pRoot->m_pLeft = NULL;
    pRoot->m_pRight = NULL;
    // 查找根节点在中序遍历中的位置，中序遍历中，根节点左边为左子树，右边为右子树
    int rootPositionInOrder = -1;
    for(int i = 0; i < nodeNum; i++)
        if(pInOrder[i] == pRoot->m_nValue)
        {
            rootPositionInOrder = i;
            break;
        }
    if(rootPositionInOrder == -1)
    {
        throw std::exception("Invalid input.");
    }
    // 重建左子树
    int nodeNumLeft = rootPositionInOrder;
    int * pPreOrderLeft = pPreOrder + 1;
    int * pInOrderLeft = pInOrder;
    pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
    // 重建右子树
    int nodeNumRight = nodeNum - nodeNumLeft - 1;
    int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
    int * pInOrderRight = pInOrder + nodeNumLeft + 1;
    pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
    return pRoot;
}

14.判断二叉树是不是完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。

bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return false;
    queue<BinaryTreeNode *> q;
    q.push(pRoot);
    bool mustHaveNoChild = false;
    bool result = true;
    while(!q.empty())
    {
        BinaryTreeNode * pNode = q.front();
        q.pop();
        if(mustHaveNoChild) // 已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空）
        {
            if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)
            {
                result = false;
                break;
            }
        }
        else
        {
            if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)
            {
                q.push(pNode->m_pLeft);
                q.push(pNode->m_pRight);
            }
            else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)
            {
                mustHaveNoChild = true;
                q.push(pNode->m_pLeft);
            }
            else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)
            {
                result = false;
                break;
            }
            else
            {
                mustHaveNoChild = true;
            }
        }
    }
    return result;
}

树

二叉树

1. 求二叉树中的节点个数

2. 求二叉树的深度

3. 前序遍历，中序遍历，后序遍历 前序遍历

4.分层遍历二叉树

5. 将二叉查找树变为有序的双向链表 要求不能创建新节点，只调整指针

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

7. 求二叉树中叶子节点的个数

8. 判断两棵二叉树是否结构相同 不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。

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

10. 求二叉树的镜像

11. 求二叉树中两个节点的最低公共祖先节点

12. 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离

13. 由前序遍历序列和中序遍历序列重建二叉树

14.判断二叉树是不是完全二叉树

内容目录

选择主题

3. 前序遍历，中序遍历，后序遍历前序遍历

5. 将二叉查找树变为有序的双向链表要求不能创建新节点，只调整指针

8. 判断两棵二叉树是否结构相同不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。

12. 求二叉树中节点的最大距离即二叉树中相距最远的两个节点之间的距离