二叉树遍历的应用（递归!递归！递归！）数据结构

在学习《数据结构》中二叉树这块的时候，能很好地帮助我们学习递归思想，
本文就二叉树的遍历的递归思想，写点二叉树的常见性质题（什么高度，同构，叶子节点各种乱七八糟~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 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; }

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

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