数据结构与算法——二叉树

一、二叉树及其存储

定义：一个有穷的结点集合
这个集合可以为空
若不为空，则它是有根结点和称其为左子树和右子树的两个不相交的二叉树组成。

ADT：
类型名称：二叉树
数据对象集：一个有穷的节点集合
操作集：判断是否为空，遍历访问，初始化一棵二叉树

二叉树的顺序存储结构：
对于完全二叉树：按从上至下，从左到右顺序存储n个结点的完全二叉树的结点父子关系

但是对于一般的二叉树，需要对其进行补齐才能顺序存储，会造成浪费大量空间。

所以一般二叉树采取链式存储
typedef struct TreeNode* BinTree;
typedef BinTree Position;
struct TreeNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
二叉树的3中递归遍历：先序，中序，后序
若干同样用递归实现，那么仅仅是访问的语句顺序不一样。
对于先序，每一个树，先根再左后右
中序，先左，再中，后右
后序：左中右

代码实现

#include<iostream>
using namespace std;

typedef struct TreeNode* BinTree;
struct TreeNode
{
    int data;
    BinTree Left;
    BinTree Right;
};

BinTree BST;


BinTree FindMin(BinTree BST)
{
    //BinTree MinNode;
    //MinNode = new struct TreeNode;
    if(BST->Left!=NULL) BST = FindMin(BST->Left);
    return BST;
}


//删除
BinTree Delete(int x,BinTree BST)//
{
    BinTree temp;
    if(!BST)
    {
        cout << "未找到该元素"<<endl;//若该树是空树或该树中没有该元素
        //return;
    }
    else if(x>BST->data)
        BST->Right = Delete(x,BST->Right);
    else if(x<BST->data)
        BST->Left = Delete(x,BST->Left);
    else
    {//找到了该元素对应的结点
        if(BST->Left&&BST->Right)//若要删除的结点含有左右2个子树，则在左子树或右子树找到最小元素，填充待删除节点
        {
            temp = FindMin(BST->Left);//这里找的是左子树，temp是最小元素对应的结点
            BST->data = temp->data;
            BST->Left = Delete(BST->data,BST->Left);
        }else{
            temp = BST;
            if(BST->Left==NULL)  //无左孩子或压根无子结点
                BST = BST->Right;
            else if(BST->Right==NULL) //无右孩子或压根无子结点
                BST = BST->Left;
            free(temp);
            }

    }
    return BST;//返回删除结点后的树
}


//插入
BinTree MakeTree(int item,BinTree BST)
{
    if(!(BST))
    {
        BST = new struct TreeNode;
        BST->Left = BST->Right = NULL;
        BST->data = item;
        return BST;
    }
    if(item>BST->data)
        BST->Right = MakeTree(item,BST->Right);
    else if(item<BST->data)
        BST->Left = MakeTree(item,BST->Left);
}

//先序遍历二叉树
void PreOrderTravel(BinTree BT)
{
    if(BT)
    {
        cout <<BT->data<<endl;
        PreOrderTravel(BT->Left);//中序只需把访问语句放在中间
        PreOrderTravel(BT->Right);//后序只需把访问语句放在后面
    }
}

//中序，先序非递归遍历
void InOrderTraversal(BinTree BST)
{
    BinTree T=BST;
    Stack S = CreatStack(MaxSize);
    while(T||!IsEmpty(S))
    {
        while(T)//对于一个节点一直向左压到栈底
        {
            Push(S,T);//对于非递归先序只需把访问语句写在这里，即在压入栈底时访问，因为压入的顺序是按照从头结点到左到右的
            T = T->Left;
        }
        if(!IsEmpty(S)){
            T = Pop(S);
            cout<<T->data;
            T = T->Right;//转向右子树
        }
    }
}

//后序非递归遍历

void PostTraversal(BinTree BST)
{
    BinTree T=BST,r=NULL;
    Stack S = CreatStack(MaxSize);
    while(T||!IsEmpty(S))
    {
        while(T)
        {
            Push(S,T);
            T = T->Left;
        }
        T = S.top();
        if(T->Right!=NULL&&T->Right!=r)//右子树存在且未被访问过，这里多了一个测试有没有访问的条件
            T = T->Right;               //是因为某些子树其右子树存在，先访问其右子树，还剩下父节点未访问，
        else{                          //这时第二次访问该父节点，这也是后序遍历的难点，根节点留到最后访问
            Pop(S);
            cout<<T->data<<endl;
            r = T;//记录最近访问过的结点
            T =NULL;//结点访问完置空
        }
    }
}

int main()
{

    BST = MakeTree(3,BST);
    BST = MakeTree(7,BST);
    BST = MakeTree(10,BST);
    BST = MakeTree(2,BST);
    BST = MakeTree(6,BST);
    BST = MakeTree(1,BST);
    BST = MakeTree(-3,BST);
    BST = MakeTree(0,BST);
    //PreOrderTravel(BST);
    //cout<<FindMin(BST)->data<<endl;
    Delete(6,BST);
    PreOrderTravel(BST);
}

后序非递归遍历：

void PostOrderS(Node *root) {
    Node *p = root, *r = NULL;
    stack<Node*> s;
    while (p!=NULL || !s.empty()) {
        if (p!=NULL) {//走到最左边，这一个循环是为了在访问结点之前遍历所有左子树
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            if (p->right!=NULL && p->right != r)//右子树存在，且右子未被访问,这一步是为了后序中的在结点之前遍历右子树
                p = p->right;
            else {
                s.pop();
                visit(p->val);
                r = p;//记录最近访问过的节点
                p = NULL;//节点访问完后，重置p指针
            }
        }
    }
}

二叉树还有层次遍历，利用队列实现。