二叉树遍历的应用（递归!递归！递归！）

在学习《数据结构》中二叉树这块的时候，能很好地帮助我们学习递归思想，

本文就二叉树的遍历的递归思想，写点二叉树的常见性质题（什么高度，同构，叶子节点各种乱七八糟~ps：其实我只是想备考下期末考！）

二叉树定义：

typedef char ElemType;
typedef struct BiNode
{ElemType data;struct BiNode *Left;struct BiNode *Right;
}BiNode, *BiTree;

二叉树高度：

int height(BiTree T)
{if (!T)return 0;  //递到最后 空节点高度为0.return 1 + max(height(T->Left), height(T->Right));//高度=1+max(左，右)，有没有后序遍历的思想呢？
}

判断两个二叉树是否相同：

int IsSame(BiTree T1, BiTree T2)
{if (T1 == NULL&&T2 == NULL)return 1;if (T1 == NULL || T2 == NULL))//肯定有个不为空了。return 0;if (T1->Data != T2->Data)//为啥要设置这三个基础条件。一定要自己想清楚。return 0;return (IsSame(T1->Left, T2->Left) && IsSame(T1->Right, T2->Right));
}

判断两个二叉树是否同构（左右可以交换）：

int IsSame(BiTree T1, BiTree T2)
{if (T1 == NULL&&T2 == NULL)return 1;if ((T1 == NULL&&T2 != NULL) || (T1 != NULL&&T2 == NULL))//这样写就是啰嗦咯！return 0;if (T1->Data != T2->Data)//为啥要设置这三个基础条件。一定要自己想清楚。return 0;return (IsSame(T1->Left, T2->Left) && IsSame(T1->Right, T2->Right)||IsSame(T1->Left, T2->Right) && IsSame(T1->Left, T2->Right)););
}

计算叶子节点的数量：

int sum=0;
int leafnum(BiTree T)
{if (T){if (!T->Left && !T->Right)sum++;leafnum(T->Left);leafnum(T->Right);}
}

判断完全二叉树：

bool IsCompleteTree(BiTree root)
{if (root == NULL)return true;BiTree tmp = NULL;queue<BiTree> q;q.push(root);while (tmp = q.front())//层序遍历，遇到空节点停下来{q.push(tmp->Left);q.push(tmp->Right);q.pop();}while (!q.empty())//如果是完全二叉树，当二叉树遍历完的时候，才会出现空节点。如果空节点后面还有节点，那就是非完全二叉树了。{tmp = q.front();if (tmp != NULL)return false;q.pop();}return true;
}//如果是让判断是否为满二叉树，怎么判断？加计数器！

判断B节点是否为A节点的祖先节点：

bool Judge(BiTree A, BiTree B)
{if (!B->Left && !B->Right)return false;if (B->Left == A || B->Right == A)return true;return(Judge(A, B->Left) || Judge(A, B->Right));
}

交换左右子树：

void ReverseLeftRightChild(BiTree T)
{// 如果是叶子节点，则递归结束  if (T == NULL)return;swap(T->Left, T->Right); // 直接使用swap交换函数比较方便，直接交换指针；  ReverseLeftRightChild(T->Left);ReverseLeftRightChild(T->Right);
}

求二叉树的宽度：（求这玩意儿有用吗？考察层序遍历~!）

int width(BiTree T)
{   if (!T)return 0;BiTree q[100];  //队列int front = 0, rear = 0;//队头指针，队尾指针int last = 0;//同一层最右结点在队列中位置int temp = 0, maxw = 0;//当前层宽度与最大宽度q[rear] = T;BiTree p;while (front <= last){p = q[front++]; //出队temp++;//同层元素加1;if (p->Left)q[rear++] = p->Left;//入队if (p->Right)q[rear++] = p->Right;//入队if (front>last)//一层结束{last = rear;if (temp>maxw)maxw = temp;//更新最大宽度temp = 0;}}return maxw;
}

还有好多问题利用三种遍历就可以直接得出了，什么求节点总数，打印叶子节点~~~！