数据结构复习 -- 二叉树

2015-08-26

@(C Plus Plus)

前些天为了准备一些面试，把本科学习的笔记翻出来，是之前参加的魔鬼训练营的学习笔记，重点是关于树的部分，另外还有一些链表和操作系统相关的东西，后续几天认真复习整理一下。手写了代码，还是手动的敲一遍，增加印象。

前序、中序和后序遍历二叉树（递归）

首先定义数的节点：

struct BTNode
{
    int val;
    BTNode *left;
    BTNode *right;
};

先序遍历算法（递归）

void preorder(BTNode *T)
{
    if(T == NULL)
        return;
    cout<<T->val<<" ";
    preorder(T->left);
    preorder(T->right);
}

中序遍历算法（递归）

void inorder(BTNode *T)
{
    if(T == NULL)
        return;
    inorder(T->left);
    cout<<T->val<<" ";
    inorder(T->right);
}

后续遍历算法（递归）

void postorder(BTNode *T)
{
    if(T == NULL)
        return;
    postorder(T->left);
    postorder(T->right);
    cout<<T->val<<" ";
}

前序、中序和后序遍历二叉树（非递归）

树的遍历非递归的方法一般多少采用栈数据结构辅助完成的。其中先序遍历和中序遍历算法比较简单。只需要一个栈就足够了。
先序遍历（非递归）

void dpreorder(BTNode *T)
{
    if(T == NULL)
        return;
    stack<BTNode *> s;
    while(T != NULL || !s.empty())
    {
        while(T != NULL)
        {
            cout<<T->val<<" ";
            s.push(T);
            T = T->left;
        }
        if(!s.empty())
        {
            T = s.top();
            s.pop();
            T = T->right;
        }
    }
}

中序遍历（非递归）

void dinorder(BTNode *T)
{
    if(T== NULL)
        return;
    stack<BTNode *> s;
    while(T != NULL || !s.empty())
    {
        while(T != NULL)
        {
            s.push(T);
            T = T->left;
        }
        if(!s.empty())
        {
            T = s.top();
            cout<<T->val<<" ";
            s.pop();
            T = T->right;
        }
    }
}

后序遍历二叉树的非递归算法要复杂一些，需要用到辅助标记，先序遍历是在入栈之前就访问，中序遍历是在第一次访问栈顶的时候就访问，后序遍历不一样，需要两次访问栈顶的时候才出栈并打印。
下面是后序遍历二叉树（非递归）

typedef enum{L,R} tagtype;
struct stacknode{
    BTNode *ptr;
    tagtype tag;
};
void dpostorder(BTNode *T)
{
    stacknode x;
    stack<stacknode> s;
    if(T == NULL)
        return;
    do
    {
        while(T != NULL)
        {
            x.ptr = T;
            x.tag = L;
            s.push(x);
            T = T->left;
        }
        while(!s.empty() && s.top().tag == R)
        {
            x = s.top();
            s.pop();
            T = x.ptr;
            cout<<T->val<<" ";
        }
        if(!s.empty())
        {
            x = s.top();
            T = x.ptr;
            s.top().tag = R;
            T = T->right;
        }
    }while(!s.empty());
}

构造二叉树

给定一个二叉树的先序遍历和中序遍历序列，构造一颗二叉树。正好创建一个二叉树验证前面的程序。
程序代码如下：

BTNode *CreateTree(int pre[],int in[],int beg1,int end1,int beg2,int end2)
{
	if(beg1 > end1 || beg2 > end2)
		return NULL
    BTNode *p;
    p = new BTNode;
    p->val = pre[beg1];
    p->left = p->right = NULL;
    if(beg1 == end1)
        return p;
    int k = beg2;
    while(pre[beg1] != in[k])
        ++k;
    int t = k - beg2 + beg1;
    p->left = CreateTree(pre,in,beg1+1,t,beg2,k-1);
    p->right = CreateTree(pre,in,t+1,end1,k+1,end2);
    return p;
}

完全二叉树遍历

给定一个完全二叉树，存储方式是使用数组方式存储的，空节点存储的是0.
题目要求是给定两个节点的位置i和j，求解这两个节点的最近的双亲。

int comparent(int i,int j)
{
    while(i != j)
    {
        if(i > j)
            i /= 2;
        else
            j /= 2;
    }
    return i;
}

求二叉树的节点数

用递归的方法比价简单

int finnum(BTNode *T)
{
    int lcount;
    int rcount;
    if(T == NULL)
        return 0;
    else if(T->left == NULL && T->right == NULL)
        return 1;
    else
        return finnum(T->left) + finnum(T->right);
}

层次遍历二叉树和树的高度

void findlevel(BTNode *T,int &level)
{
    BTNode* que[maxlength];
    int front = 0;
    int rear  = 0;
    int k;
    if(T != NULL)
    {
        que[(rear++)% maxlength] = T;
        k = rear;
        level = 0;
    }
    while(rear != front)  // 队列空
    {
        T = que[(front++) % maxlength];
        cout<<T->val<<" ";
        if(T->left != NULL)
            que[(rear++)% maxlength] = T->left;
        if(T->right != NULL)
            que[(rear++)% maxlength] = T->right;
        if(k == front)
        {
            k = rear;
            level ++;
            cout<<endl;
        }
    }
}

参考

本科参加魔鬼训练营笔记