6-3 Height of Binary Search Tree (25 分)

末蓝、 2023-10-03 07:45 23阅读 0赞

You are supposed to write a function of finding the height of a binary search tree with the given postorder sequence.

#### Format of function: ####

int Height_of_BST( int postorder[], int N );

where the postorder sequence is stored in int postorder\[\], and the integer N is the number of nodes in the tree, which is guaranteed to be positive. The function Height\_of\_BST is supposed to return the height of the binary search tree.

Note:

*  It is guaranteed that the postorder sequence consists of distinct integers and does correspond to a binary search tree.
 *  You may assume that MAXN is a small number (less than 100) in the judge’s program.

#### Sample program of judge: ####

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXN 10
    
    int Height_of_BST( int postorder[], int N );
    
    int main()
    {
        
        int postorder[MAXN], N, i;
    
        scanf("%d", &N);
        for (i=0; i<N; i++) scanf("%d", &postorder[i]);
        printf("%d\n", Height_of_BST(postorder, N));
    
        return 0;
    }
    
    /* Your function will be put here */

#### Sample Input: ####

9
    2 8 9 6 22 20 30 25 10

#### Sample Output: ####

#### 思路： ####

先根据二叉排序树的后序序列生成该二叉树，再求其高度。

###### 如何根据一个二叉排序树的后序序列生成该二叉树？ ######

*  我们建立二叉树，就是确定根，然后建立该根的左子树、右子树。
 *  其中关键在于如何确定其左子树中节点的个数，对于前、中和后、中序列的，由于有中序序列，可以轻易确定左右子树中节点的个数。
 *  对于这个二叉排序树的后序序列，我们可以轻易找到根，然后序列中大于等于根的就是根的右子树中节点，小于根的就是左子树中的节点。
 *  后序序列：2 8 9 6 22 20 30 25 10

#### 代码： ####

typedef struct BiNode
    {
        
        int data;
        struct BiNode *Left,*Right;
    }*BiTree;
    
    BiTree CreateTree( int postorder[], int N );
    BiTree CreateTree( int postorder[], int N )
    {
        
        int i=0,root=0;
        BiTree T=(BiTree)malloc(sizeof(struct BiNode));
        if(N==0)
        {
        
            return NULL;
        }
        //确定根
        root=postorder[N-1];
        T->data=root;
        i=0;
        //确定左子树中节点个数，比根大的就是右子树中的节点，即可求得左子树中节点的个数（间接得到右子树中的节点个数）
        while(i<N)
        {
        
            if(postorder[i]>=root)
            {
        
                break;
            }
            i++;
        }
        T->Left=CreateTree(postorder,i);
        T->Right=CreateTree(postorder+i,N-i-1);
        return T;
    }
    
    int GetHight(BiTree BT);
    int GetHight(BiTree BT)
    {
        
        int hl=0,hr=0,maxh=0;
        if(BT)
        {
        
            hl=GetHight(BT->Left);
            hr=GetHight(BT->Right);
            if(hl>hr)
            {
        
                maxh=hl;
            }
            else
            {
        
                maxh=hr;
            }
            return maxh+1;
        }
        else
        {
        
            return 0;
        }
    }
    
    
    int Height_of_BST( int postorder[], int N );
    int Height_of_BST( int postorder[], int N )
    {
        
        BiTree BT;
        BT=(BiTree)malloc(sizeof(struct BiNode));
        BT=CreateTree(postorder,N);
        return GetHight(BT)-1;
    }