Data structure

二叉树节点结构C定义：

typedef struct nodeT{

    int data;
    struct nodeT *left;
    struct nodeT *right;
} node;

1. 二叉搜索树查找

递归方法：

node *LookupNode(node *root, int data)
{
    if(!root) return NULL;
    else if(root->data == data) return root;
    else if(root->data < data) return LookupNode(root->right, data);
    else if(root->data > data) return LookupNode(root->left, data);
}

  非递归方法：

node *LookupNode(node *root, int data)
{
    node *curNode = root;
    while(curNode)
    {
       if(curNode->data == data) return curNode;
       else if(curNode->data < data) curNode = curNode->right;
       else if(curNode->data > data) curNode = curNode->left;
    }
    return NULL;
}

当二叉搜索树为二叉平衡树时，二叉树查找的最差复杂度为O(log(n))；否则，二叉树最坏退化成链表，最差复杂度为O(n)。

READ MORE…