设计算法，递归的计算二叉树的高度
1）算法思想
2）伪代码
int TreeDepth(TreeNode root) { if(root==null) return 0; int left = TreeDepth(root.left); int right = TreeDepth(root.right); return Math.max(left, right)+1; }
3）时间复杂度分析
没有树的任何信息，可对树的每个节点访问一次，O(N)如果是一个平衡树，我们只需要遵循一个分支，并且平衡树的属性确保分支长度为O(log(N))，所以针对某个分支的时间复杂度为O(logN)
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,如果相等，则打印出其层号L printf("层号：%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初值为0 void allPath(BTNode *p){ if (p == NULL) return; pathstack[top]=p->data; ++top; //所访问结点入栈，即p自上至下走的时候结点入栈 if (p->lchild==NULL&&p->rchild==NULL){ //如果当前结点是叶子结点，则打印路径 for(i=0; i
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; }
好文链接
发表评论