1、求二叉树中的节点个数
递归解法：
（1）如果二叉树为空，节点个数为0
（2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
int NodeNum(BTNode * root){ if(root== NULL) // 递归出口 return 0; return NodeNum(root->lchild) + NodeNum(root->rchild) + 1;} 2、求二叉树的深度
递归解法：
（1）如果二叉树为空，二叉树的深度为0
（2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
int GetDepth(BTNode * root){ if(root== NULL) // 递归出口 return 0; int depthLeft = GetDepth(root->lchild); int depthRight = GetDepth(root->rchild); return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1); } 3、求二叉树第K层的节点个数
递归解法：
（1）如果二叉树为空或者k<1返回0
（2）如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
//可将此问题转换为求根结点左右子树的k-1层结点数int TreeLevelSize(BTNode* root, int k){if(root == NULL || k < 1){//空树return 0;}if(k == 1){return 1;}return TreeLevelSize(root->lchild,k-1) + TreeLevelSize(root->rchild,k-1);} 4、求二叉树中叶子节点的个数
递归解法：
（1）如果二叉树为空，返回0
（2）如果二叉树不为空且左右子树为空，返回1
（3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数
参考代码如下：
int GetLeafNodeNum(BTNode * root){ if(root== NULL) return 0; if(root->lchild== NULL && root->rchild== NULL) return 1; return GetLeafNodeNum(root->lchild) + GetLeafNodeNum(root->rchild);} 5、计算二叉树中双分支结点的个数 int Double(BTNode *b){ if(b==NULL) return 0; //返回的树的高度为0 if(b->lchild != NULL && b->rchild != NULL) return Double(b->lchild) + Double(b->rchild)+1; else return Double(b->lchild) + Double(b->rchild);} 6、删除二叉树中以元结点值x为的根节点的子树 void Del(BTNode *b, int x){ //基于先序遍历的递归算法，先找到值为x的结点p,然后调用DestoryBTree(p)删除并释放该子树 if(b==NULL) return; if(b->data == x) { DestoryBTree(b); b = NULL; } else { Del(b->lchild,x); Del(b->rchlid,x); }}void DestoryBTree(BTNode *b){ //释放二叉树b中所有结点分配的空间 if(b!=NULL) { DestoryBTree(b->lchild); DestoryBTree(b->rchild); free(b); }} 7、判断两棵二叉树是否结构相同
不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。
递归解法：
（1）如果两棵二叉树都为空，返回真
（2）如果两棵二叉树一棵为空，另一棵不为空，返回假
（3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
int StructureCmp(BTNode * root2, BTNode * root2){ if(root== NULL && root2== NULL) // 都为空，返回真 return 1; else if(root== NULL || root2== NULL) // 有一个为空，一个不为空，返回假 return 0; int resultLeft = StructureCmp(root1->lchild, root2->lchild); // 比较对应左子树 int resultRight = StructureCmp(root1->rchild, root2->rchild); // 比较对应右子树 return (resultLeft && resultRight);} 8、查找一个值
//遍历二叉树即可，当发现与该值相等时返回该结点
//若没有则返回NULL
BTNode* TreeFind(BTNode* root, int to_find){if(root == NULL){//空树return NULL;}if(root->data == to_find){return root;}BTNode* lresult = TreeFind(root->lchild,to_find);BTNode* rresult = TreeFind(root->rchild,to_find);//若左右子树均没有，返回值依然为空return lresult != NULL ? lresult : rresult;} 9、返回一个结点的父结点 BTNode* Parent(BTNode* root, BTNode* node){if(root == NULL){return NULL;}if(root->lchild == node || root->rchild == node){//说明此结点即为要找的结点的父结点return root;}BTNode* lresult = Parent(root->lchild,node);BTNode* rresult = Parent(root->rchild,node);return lresult != NULL ? lresult : rresult;} 10. 判断二叉树是不是平衡二叉树
递归解法：
（1）如果二叉树为空，返回真
（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
int IsAVL(BTNode* root, int height){ if(root== NULL) // 空树，返回真 { height = 0; return 1; } int heightLeft; bool resultLeft = IsAVL(root->lchild, heightLeft); int heightRight; bool resultRight = IsAVL(root->rchild, heightRight); if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL，并且高度相差不大于1，返回真 { height = max(heightLeft, heightRight) + 1; return 1; } else { height = max(heightLeft, heightRight) + 1; return 0; }} 11、假设二叉树采用二叉链存储结构，设计一个算法，利用结点的右孩子指针rchild将一棵二叉树的叶子结点按照从左往右的顺序串成一个单链表(在题目中定义两个指针head与tail,其中head指向第一个叶子结点，head 初值为NULL, tail 指向最后一个叶子结点)。
分析：要想解决本题，显然需要遍历这棵二叉树。通过遍历此二叉树，能访问到每一个叶
子结点，并在访问时对其rchild指针进行修改，以达到将叶子结点串
成一条单链表的目的。我们所需要做的只是在访问每个结点的过程中，判断此结点是否是叶子结点，如果是，就对rchild指针修改，如果不是，就什么都不做。这里采用先序遍历方
式来解此题。
void linkTree(BTNode *p,BTNode *head,BTNode *tail){if(p == NULL)retrun;if(p->lchild == NULL && p->rchild == NULL){//判断是不是叶子结点if(head == NULL){//head为NULL，则当前是第一个叶子结点，将head和tail都指向它head = p;tail = p;}else{tail->rchild = p;//不是第一个结点，将此结点连接到链表的表尾，用tail指向它，即指向新的表尾tail - p;}}linkTree(p->lchild,head,tail);linkTree(p->rchild,head,tail);} 12、在二叉树的二叉链存储结构中，增加一个指向双亲结点的parent指针，设计一个算法，给这个指针赋值，并输出所有结点到根结点的路径。
（1）修改结构定义
typedef struct BTNode{int data;struct BTNode *lchild,*rchild,*parent;}BTNode;
（2）给各个结点的parent赋值。
因为要访问所有结点，显然要用遍历来做，修改遍历模板即可。在每访问到一个新结点时，都要知道其双亲结点的地址，才可以将其parent指针指向它，为此需要一个指针来指向其双亲结点。
void triBtree(BTNode *p, BTNode *q)班//此处参数 q始终指向当前访问结点p的双亲结点。当p为根结点时，q应为NULL{if(p == NULL)return;p->parent = q;//将当前所访问的结点的parent指针指向q//即指向其双亲结点q = p;//将q指向p,因为下边将要对p的左孩子和右孩子的//parent指针进行赋值，显然P是其双亲结点triBtree(p->1child,q); //修改其左子树中所有结点的parent指针triBtree(p->rchild,q); //修改其右子树中所有结点的parent指针}
（3）打印路径
①任给一个结点，怎样打印出这个结点到根结点的路径呢?只需打印出此结点，然后通过parent找到其双亲结点。如此重复，直到parent为NULL (上一步中已经提到，根结点的parent为NULL)即可。
void printPath(BTNode *p){while (p!=NULL){//p不为空时就打印其data域值printf("%d ",p->data) ;p = p->parent;//找到其双亲结点}}
②怎样打印出所有路径?要打印所有路径，必须找到所有结点并逐一打印，因此这里又用到了遍历，显然任何一种遍历方式都可以。
void allPath(BTNode *p){if(p == NULL)return;printPath(p) ;//每到一个结点的时候就调用①中的函数printPath来打印这个结点到根结点的路径allPath (p->1child) ;allPath(p->rchi1d) ;} 13、假设满二叉树b的先序遍历序列已经存在于数组中(在解题过程中，此数组名称可自定义，长度为n)，设计一个算法将其转换为后序遍历序列。
已知先序遍历序列，则序列中第一个元素即为根结点。将除去第-个元素之外的元素序列分成
前后相等长度的两半，前一半为左子树上的结点，后一半为右子树上的结点。只需将根结点移动到整个序列的末尾，然后分别递归地去处理序列的前一半和后一半即可。
假设原序列在pre[]数组内，转化后的序列存在pos[]数组内。
void change(char pre[], int L1,int R1,char post[],int. L2, int R2){if (L1<=R1){post [R2]=pre[L1]; //将 pre[]中的第一个元素放在post[]的末尾递归地处理pre[]中的前一半序列，将其存在ppost[]数组中对应的前一半位置change (pre ,L1+1, (L1+1+R1) /2,post,L2, (L2+R2-1)/2) ;//递归地处理pre[]中的后一半序列，将其存在post[]数组中对应的后一半位置change (pre, (L1+1+R1) /2+1 ,R1,post, (L2+R2-1) /2+1,R2-1) ;}} 14、假设二叉树采用二叉链存储结构，设计一个算法，求二叉树b中值为x的结点的层号。 int L = 1;//L是全局变量，初值为1,用来记录当前所访问的结点层号void leno(BTNode *p, char x){if(p == NULL)return;if (p->data==x){ //当第一次来到这个结点时，对其data域进行检查，看是否等于x,如果相等，则打印出其层号Lprintf("层号：%d",L);}++L;//打印完层号之后，指针p将要进入下一层结点，因此L要自增1,代表下一层的层号leno(p->1child,x) ;leno(p->rchild,x);--L;//p指针将要由下一层返回上一层，因此L要自减1,代表} 15、设中序线索二叉树的类型为TBTNode* InThTree; 1）设计算法，在一棵中序线索二叉树中寻找结点t的子树上中序下的最后一个结点。
算法的思路: 沿结点t的右子树链一直走下去，直到遇到其右指针为右线索的结点为止，该结点即为所求。 TBTNode* inLast(TBTNode *t){TBTNode *p = t;while(p &&!p->rtag)p = p->rchild;return p;} 2)设计算法，在一棵中序线索二叉树中寻找结点t的中序下的前驱。
算法的思路: 若结点t有左线索，则其左线索所指结点即为其中序前驱;若无左线索，则其左子树中中序的最后一个结点即为它的中序前驱。
TBTNode* inPrior(TBTNode *t){TBTNode *p = t->lchild;while(p && !p->ltag)p = p->rchild;return p;} 3)设计算法，在一棵中序线索二叉树中寻找结点t的前序下的后继。
TBTNode* treNext(TBTNode *t){TBTNode *p;if(!t->ltag)p = t-> lchild;else if (!t->rtag)p = t->rchi1d;else{p = t;while (p && p->rtag)p = p->rchild;if (p)p = p->rchild;}return p;} 16、假设二叉树采用二叉链存储结构，设计一个算法，输出根结点到每个叶子结点的路径。
这里用一个栈来保存路径上的结点，当p自上至下走的时候将所经过的结点依次入栈。当p自下至上走的时候，将p所经过的结点依次出栈;当p来到叶子结点的时候，自底至项输出栈中元素就是根到叶子的路径。
int i;int top = 0;//此处两句定义了存储路径用的栈，这里采用先入栈char pathstack [maxSize] ;//然后++top的方式，因此top初值为0void allPath(BTNode *p){if (p == NULL)return;pathstack[top]=p->data; ++top;//所访问结点入栈，即p自上至下走的时候结点入栈if (p->lchild==NULL&&p->rchild==NULL){//如果当前结点是叶子结点，则打印路径for(i=0; i<top; ++i)printf("%c ",pathstack[i]);}allPath(p->lchild) ;allPath(p->rchild) ;--top;//所访问结点出栈，即p自下至上走的时候结点出栈} 17、求先序遍历中第k个结点的值 int i=0;int PreNode(BTNode *T,int k){if(T == NULL){return 0;}i++;if(i==k){//visit(T); return T->data;}int ch = PreNode(T->lchild,k);if(ch != 0)return ch;ch = PreNode(T->rchild,k);return ch;}