树 算法题(一)

1、计算二叉树中所有结点个数

int CntNode(BiTree T){
    int k=0;
    if(T){
        k++;
        k+=CntNode(T->lchild);
        k+=CntNode(T->rchild);
    }
    return k;
}

2、计算二叉树中所有叶子节点的个数

int LeafNode(BiTree T){
    int k=0;
    if(T){
        if(T->lchild==NULL&&T->rchild==NULL)
            k++;
        else{
            k+=LeafNode(T->lchild);		//统计左子树叶子结点
            k+=LeafNode(T->rchild);		//统计右子树叶子结点
        }
    }
    return k;
}

3、计算二叉树中所有双分支的节点个数

int DNodes(BiTree T){
    if(T==NULL)
        return 0;
    else if(T->lchild!=NULL&&T->rchild!=NULL)//双分支结点
        return DNodes(T->lchild)+DNodes(T->rchild)+1;
    else//单分支结点或叶子结点
        return DNodes(T->lchild)+DNodes(T->rchild);
}

4、计算二叉树的深度

int Deepth(BiTree T){
    int hl=0,hr=0;	//hl是左子树高度，hr是右子树高度
    if(T==NULL)
        return 0;
    else{	
        hl=Deepth(T->lchild);	//遍历左子树求高度
        hr=Deepth(T->rchild);	//遍历右子树求高度
        return hl>hr?hl+1:hr+1;	//返回子树高度较高的+根结点
    }
}

5、找出二叉树中最大值的点

//基于中序遍历的非递归算法
ElemType Inorder(BiTree T){
    ElemType max=-1;
    InitStack(S);
    p=T;
    while(p||!StakEmpty(S)){
        if(p){
            p=p->lchild;
            Push(S,p);	//入栈
        }
        else{
            Pop(S,p);	//出栈
            if(p->data>max)
                max=p->data;
            p=p->rchild;
        }
    }
    
    return max; 
}

6、判断两个二叉树是否相似(指都为空或者都只有一一个根节点，或者左右子树都相似)

bool IsSimilar(BiTree T1, BiTree T2){
    if(T1==NULL&&T1==NULL)	//都为空树
        return true;
    else if(T1==NULL||T1==NULL)	//只有一个棵树为空
        return false;
    else	//递归判断子树
        return IsSimilar(T1-lchild,T2->lchild) && IsSimilar(T1-rchild,T2->rchild);
}

7、把二叉树所有节点左右子树交换

/**
	先交换左子树中的结点
	再交换右子树中的结点
	最后交换左右子树，基于后序遍历
**/

void SwaptTree(BiTree T){
    BiTree temp;
    if(T){
        SwaptTree(T->lchild);	//递归交换左子树
        SwaptTree(T->rchild);	//递归交换右子树
        temp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=temp;
    }
}

8、输出先序遍历第k个结点的值

int cnt=0;	//全局变量，统计结点个数
Status pre_k(BiTree T,int k){
    if(T){
        cnt++;
        if(cnt==k){
            print(T->data);	//输出第k个结点的值
            return OK;
        }
        else{
            if(pre_k(T->lchild,k))
                return OK;
            if(pre_k(T->rchild,k))
                return OK;
        }
    }
    return ERROR;
}

9、求二叉树中值为x的层号

int h=1;
void levelnum(BiTree T,ElemType x){
    if(T){
        if(x==T->data)
            cout<<h;	//打印层号
        ++h;
        levelnum(T->lchild,x);
        levelnum(T->rchild,x);
        --h;
    }
}

12、树中元素为x的结点，删除以它为根的子树
13、利用结点的右孩子指针将一个二叉树的叶子节点从左向右连接成一个单链表(head 指向第一个， tail 指向最后一个)
14、输出根节点到每个叶子结点的路径
15、已知满二叉树先序序列存在于数组中，设计算法将其变成后序序列
16、先序与中序遍历分别存在两个一维数组A，B中，试着建立二叉链表
17、二叉树以顺序方式存在于数组A的中，设计算法以二叉链表表示
18、增加一个指向双亲节点的parent指针，输出所有节点到根节点的路径
19、先序非递归遍历二叉树
20、中序非递归遍历二叉树
21、后序非递归遍历二叉树
22、在二叉树中查找值为x的结点，打印出值为x的所有祖先
23、找到p和q最近公共祖先结点r
24、层次遍历
25、试给出自下而上从右到左的层次遍历
26、求解二叉树的宽度
27、用层次遍历求解二叉树的高度
28、判断二叉树是否为完全二叉树
29、计算二叉树的带权路径长度(叶子节点)
30、将给定的二叉树转化为等价的中缀表达式
31、建立中序线索二叉树
32、中序遍历线索二叉树
33、先序建立二叉搜索树并先序遍历
34、寻找中序线索二叉树的前驱结点
35、用孩子兄弟表示法求树所有叶子结点个数
36、用孩子兄弟表示法求树的高度
37、已知一棵树的层次序列和每个节点的度,编写算法构造此树的孩子兄弟链表。
38、判断二叉树是否是二叉排序树