二叉树

2017-09-02 本文已影响0人安安zoe

0. 什么是树

数据的基本单位是数据元素，在涉及到数据处理时数据元素之间的关系称之为结构，我们依据数据元素之间关系的不同，将数据结构分为线性结构和非线性结构 两种。

线性结构：按照某种次序排列在一个序列中，在线性结构中，根据数据元素存取方法的不同分为三种。
1. 直接存取：直接存取指定项而不需要访问其前驱，如数组，文件；
2. 顺序存取：只能按序访问直到指定元素，如栈，队列，链表；
3. 字典结构：字典map，关键码索引
非线性结构：每个数据元素都有可能与其他零个或多个元素发生联系，可分为层次结果和群结构。层次结构中的典型结构就是树形结构。群结构中元素之间是无顺序结构，如集合，图，网络结构等。

这上面所划分的是数据结构的逻辑结构，而数据是如何在计算机中存储的，这涉及到数据的物理结构，逻辑结构是从解决问题出发，涉及到功能的简历，物理结构设计到响应速度，处理、修改、存储时间等问题。

顺序存储结构：逻辑上相邻元素存放到物理位置上相邻的存储单元
链接存储结构：逻辑上相邻的元素位置上不一定相邻，通过指针指示
索引存储结构：存储时建立附加索引表，（关键码，地址）
散列存储结构：通过散列计算存储地址

树：N个结点的有限集合.png

1. 基本性质

二叉树不存在度大于2的节点，二叉树是有序的树，需要区分左节点和右节点
设度为0 , 1, 2 的结点的个数为N0，N1，N2，则结点总数为N = N0 + N1 + N2
设B为二叉树的分支总数，（除了根节点都有一个接入的分支），N = B+1，而分支总数由度为1或2的结点练出，则有 B= N1 + 2N2；
叶子结点的个数 N0 = N2 +1；
非空二叉树的第K层最多有 2 ^(k-1) 个节点；
高度为H的二叉树最多有 2^H -1 个节点；
结点为 i 所在的层次为 log2（i） +1；
两种基本二叉树

二叉树.png

2. 二叉树存储结构

顺序存储结构：数组（一般仅适用于完全二叉树）
链式存储结构：数据域 + 指针域（leftchild + rightchild）

3. 二叉树的遍历

二叉树遍历是最基本的操作，分为先序遍历，中序遍历、后序遍历，以及层次遍历。

3.1 递归遍历方式

前序遍历

void pre_order(BTree *root){
    if (root != NULL){
        visit(root); //cout<<root->value
        pre_order(root->leftchild);
        pre_order(root->rightchild);
    }
}

中序遍历

void in_order(BTree* root){
    if (root != NULL){
        in_order(root->leftchild);
        visit(root);
        in_order(root->rightchild);
    }
}

后序遍历

void post_order(BTree * root){
    if (root != NULL){
        post_order(root->leftchild);
        post_order(root->rightchild);
        visit(root);
    }
}

递归调用的代价较高，递归的实现是调用函数的本身，每次调用都要保存局部变量，调用函数地址，返回值等等，所以递归算法很简洁，相对来说开销比较大。

3.2 非递归的遍历方式

前序遍历

#include<iostream>
#include<string>
#include<stack>
using namesapce std;

typedef struct node{
    int data;
    struct node *leftchild, *rightchild;
}BTree;

void pre_order(BTree *root){
    stack<BTree*> s;
    BTree *p = root;

    //当栈非空或者p指针非空时执行
    while (p != NULL || !s.empty()){
        while (p != NULL){
            cout << p->data;
            s.push(p);
            p = p->leftchild;
        }
        if (!s.empty()){
            p = s.top();
            s.pop();
            p->p->rightchild;
        }
    }
}

中序遍历

void in_order(BTree * root){
    stack<BTree *> s;
    BTree * p = root;

    while (p != NULL || !s.empty()){
        while (P != NULL){
            s.push(p);
            p = p->leftchild;
        }
        if (!s.empty()){
            p = s.top;
            cout << p->data;
            s.pop();
            p = p->rightchild;
        }
    }
}

后序遍历
方法一：当用栈来存储结点的时候，需要分清楚是返回根结点时，是从左子树返回的，还是从右子树返回的，因此需要使用一个辅助指针，也记录是否被访问过。

void post_order(BTree *root){
    stack<BTree *> s;
    BTree *p = root, *r = NULL;

    while (p != NULL || !s.empty()){
        if (p != NULL){
            s.push(p);
            p = p->leftchild;  // 最左边
        }
        else{
            p = s.top();
            //右子树存在且没有被访问过
            if (p->rightchild != NULL && p->rightchild != r){
                p = p->rightchild;
                s.push(p);
                p = p->leftchild;
            }
            else{
                p = s.top();
                //弹出结点并访问
                s.pop();
                cout << p->data;
                r = p;
                p = NULL;

            }
        }
    }
}

方法二：
对于任一结点，线将其入栈，如果结点P不存在左孩子和右孩子，则可以直接访问它，如果P上存在左孩子或者右孩子，但是左孩子或者右孩子已经访问过了，则直接访问该结点，否则，将P的右孩子和左孩子依次入栈。
这种方法要简单一些。

void post_order(BTree *root){
    stack<BTree *> s;
    BTree *cur = NULL; //当前结点
    BTree *pre = NULL; //前一次访问的结点

    s.push(root);
    while (!s.empty()){
        cur = s.top();
        if ((cur->leftchild == NULL && cur->rightchild == NULL) ||
            (pre != NULL && (pre == cur->leftchild || pre == cur->rightchild))){
            //如果当前结点没有孩子结点或者孩子结点已经被访问过
            cout << cur->data;
            s.pop();
            pre = cur;
        }
        else{
            if (cur->rightchild != NULL)
                s.push(cur->rightchild);
            if (cur ->rightchild ！= NULL)
                s.push（cur->leftchild);
        }
    }
}

3.3 层次遍历

《编程之美：分层遍历二叉树》的另外两个实现

// 输出以root为根结点的第level层中的所有结点（从左向右）
// 成功返回 1
// 递归实现
int printNodeAtLevel(BinaryNode *root, int level){
    if (!root || level < 0)
        return 0;
    if (level == 0){  // 根结点为0深度
        cout << root->data << " ";
        return 1;
    }
    return printNodeAtLevel(root->leftchild,level -1) + 
        printNodeAtLevel(root->rightchild,level-1)；

}

void layer_order(BTree *tree){
    if (tree == NULL)
        return;

    queue<BTree *> que;
    que.push(tree);

    BTree * p = NULL; 
    while (!que.empty()){
        p = que.front();
        visit(p);
        que.pop();
        if (p->leftchild != NULL)
            que.push(p->leftchild);
        if (p->rightchild != NULL)
            que.push(p->rightchild);
    }
}

// 自己实现队列
# define max 1000;
typedef struct sequeue{
    BTree data[max];
    int front;
    int rear;
}sequeue;

void enter(sequeue *q, BTree t){
    if (q->rear == max){
        cout << "the queue is full" << endl;
    }
    else{
        q->data[q->rear] = t;
        q->rear++;
    }
}

BTree del(sequeue *q, BTree t){
    if (q->front == q->rear){
        return NULL;
    }
    else{
        q->frot++;
        return q->data[q->front -1]
    }
}

void level_tree(bintree t){
    sequeue q;
    Btree temp;
    q.front = q.rear = 0;
    if (!t){
        printf("the tree is empty\n");
        return;
    }
    enter(&q, t);
    while (q.front != q.rear){
        t = del(&q);
        printf("%c ", t->data);
        if (t->lchild){
            enter(&q, t->lchild);
        }
        if (t->rchild){
            enter(&q, t->rchild);
        }
    }
}

4. 二叉树基本使用

二叉树中的那些常见的面试题

4.1 判断两棵二叉树是否相等

比较两棵二叉树是否相等，注意是否可以旋转的问题

bool isequal(BinaryNode *root1, BinaryNode *root2){
    if (root1 == NULL && root2 == NULL)
        return true;
    if (!root1 || !root2)
        return false;
    if (root1->data == root2->data)
        return isequal(root1->leftchild, root2->leftchild) &&
            isequal(root1->rightchild, root2->rightchild);
    else
        return false;
}

//如果左右节点可以旋转
return (isequal(root1->leftchild, root2->leftchild) && isequal(root1->rightchild, 
    root2->rightchild)) || isequal(root1->leftchild, root2->rightchild) &&
    isequal(root1->rightchild, root2->leftchild);

4.2 求二叉树的深度

本质上是二叉树的遍历，先求出左右子树的深度，才能求出根结点的深度

int tree_height(BinaryNode *root){
    int left, right;
    if (root == NULL) return -1;
    
    left = tree_height(root->leftchild);
    right = tree_height(root->rightchild);
    return (left > right) ? (left+1) : (right+1);
}

4.3 求二叉树结点的最大距离

《编程之美: 求二叉树中节点的最大距离》的另一个解法

距离的定义：如果将二叉树看做是一个图，父子结点之间的连线是双线的，定义距离是两结点之间边的个数。

最大距离.png

分析：计算一个二叉树的最大距离有两种情况：
A：路径经过左子树最深结点，通过根结点，再到右子树的最深结点
B：路径不穿过根结点，而是左子树或者右子树的最大路径，取其大者
只要计算这两种情况的路径距离，并取最大值，就是该二叉树的最大距离

情况A和情况B.png

因此情况A需要子树的最大深度，B需要子树的最大距离。

struct result{
    int nMaxDistance; // 最大距离
    int nMaxDepth; // 最大深度
};

result getMaximumDistance(BinaryNode *root){
    if (!root){
        result empty = { 0, -1 }; //最大深度初始化为 -1，调用者要对它加1，然后变为0
        return empty;
    }
    result res;
    result lhs = getMaximumDistance(root->leftchild);
    result rhs = getMaximumDistance(root->rightchild);
    res.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1);
    res.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance),
        lhs.nMaxDepth + rhs.nMaxDepth + 2);
    return res;

}

4.4 由遍历序列重建二叉树

先序遍历的第一个结点一定是二叉树的根结点，后序遍历序列的最后一个结点一定是根结点，在中序遍历中，根结点将中序序列分为两个左右子序列。
只要知道二叉树的中序序列和任意其他一种序列（前序，后序和层次），都可以唯一确定一棵二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

BinaryNode *Construct(int *preorder, int *inorder, int length){
    if (preorder == NULL || inorder == NULL || length <= 0)
        return NULL; // 注意return NULL
    // 前序 - 首：尾  中序 - 首：尾
    return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
}
BinaryNode *ConsturctCore(int *startPreorder, int *endPreorder,
                int * startInorder, int * endInorder){
    //前序遍历第一个数字是根结点的值
    int rootvalue = startPreorder[0];
    BinaryNode *root = new BinaryNode();//建立结点
    root->data = rootvalue;
    root->leftchild = root->rightchild = NULL;

    if (startPreorder == endPreorder){ // 边界条件
        if (startInorder == endInorder && *startPreorder == *startInorder)
            return root;
        else
            throw std:exception("Invalid input");//非法输入
    }

    // 在中序遍历中找到根结点的值
    int *rootInorder = startInorder;
    while (rootInorder <= endInorder && *rootInorder != rootvalue)
        ++rootInorder;
    if (rootInorder == endInorder && *rootInorder != rootValue)
        throw std::exception("Invaild input");
    
    int leftLength = rootInorder - startInorder;
    int *leftPreorderEnd = startPreorder + leftLength;
    if (leftLength > 0)
        //构建左子树 递归
        //中序遍历后根据根节点获取的 左子树元素  rootinorder是中序遍历中的根元素的位置
        root->leftchild = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
    if (leftLength < endPreorder - startPreorder)
        root->rightchild = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder, endInorder);
    return root;

}

4.5 从二叉树中查找值为x的结点

bool findBTree(BinaryNode *root, ElemType &x){
    if (root == NULL)
        return false;
    if (root->data == x){
        x = root->data;
        return true;
    }
    else{
        if (findBTree(root->leftchild, x))
            return true;
        if (findBTree(root->rightchild, x))
            return true;
        return false;
    }
}

4.6 统计二叉树中等于给定值x的结点的个数

int Count(BinaryNode *root, ElemType &x){
    if (root == NULL)
        return -1;
    if (root->data == x){
        return Count(root->leftchild, x) + Count(root->rightchild, x) + 1;
    }
    else
        return Count(root->leftchild, x) + Count(root->rightchild, x);
}

4.7 返回x结点所在的层号


int findlevel(BinaryNode *root, int x){
    if (root == NULL)
        return -1;
    if (root->data == x) // 根结点的层号为1
        return 1;
    else{
        int leftlevel = findlevel(root->leftchild, x);
        if (leftlevel >= 1)
            return leftlevel + 1;
        
        int rightlevel = findlevel(root->rightchild, x);
        if (rightlevel >= 1)
            return rightlevel + 1;
    }
    return -1;
}

4.8 从二叉树中找到所有结点的最大值

int MaxValue(BinaryNode * root){
    if (root == NULL)
        return 0;

    int leftmax, rightmax;
    leftmax = MaxValue(root->leftchild);
    rightmax = MaxValue(root->rightchild);
    int submax = (leftmax >= rightmax) ? leftmax : rightmax;
    return (submax >= root->data) ? submax : root->data;
}

4.9 求二叉树中所有结点数

int TreeCount(BinaryNode *root){
    if (root == NULL)
        return -1;
    else
        return Treecount(root->leftchild) + TreeCount(root->rightchild) + 1;
}

4.10 求二叉树中所有叶子结点数目

int LeafCount(BinaryNode *root){
    if (root == NULL)
        return -1;
    if (root->leftchild == NULL && root->rightchild == NULL)
        return 1;
    else
        return LeafCount(root->leftchild) + LeafCount(root->rightchild);
}

4.11 二叉树路径上结点的和等于定值

一棵二叉树每个结点包含一个整数，请设计一个算法输出所有满足条件的路径，此路径上所有结点的和等于定值，注意此类路径不要求必须从根结点开始

void printbuffer(vector<int> buffer, int level, int end){
    for (int i = level, i <= end; i++)
        cout << buffer[i] << " ";
    cout << endl;
}

// 输入：二叉树 sum定值 存储的vector<buffer>
void findsum(BinaryNode *root, int sum, vector<int> buffer, int level){
    if (root == NULL)
        return;
    int temp = sum;
    buffer.push_back(root->data);
    for (int i = level; i >= 0; i--){
        temp -= buffer[i];
        if (temp ==0)
            printbuffer(buffer,i,level)
    }
    findsum(root->leftchild, sum, buffer, level + 1);
    buffer.pop_back();
    level -= 1;
    findsum(root->rightchild, sum, buffer, level + 1);
}

5. 二叉排序树（树的应用）

二叉排序树（Binary sort/search Tree）/BST, BST 具有如下性质：（1）若根节点具有左子树，则左子树所有结点都比根结点要小（2）若根结点有右子树，则右子树的所有结点都比根结点大（3）左右子树也分别为BST；
左子树值<根结点值<右子树值，所以对BST进行中序遍历，可以得到一个递增的有序序列。
构造一个二叉排序树的目的：提高查找，插入，删除的速度；
如何判断一棵二叉树是否是二叉排序树

// 二叉搜索树的中序遍历是递增的
int prev = INT_MIN;
int judgeBST(BinaryNode *root){
    int b1, b2;
    if (root == NULL)
        return 1;
    else{
        b1 = judgeBST(root->rightchild);
        if (b1 == 0 || prev >= root->data)
            return 0;
        prev = root->data;
        b2 = judgeBST(root->rightchild);
        return b2;
    }
}

二叉排序树（二叉查找树）常用操作

常用操作：插入结点，先进行查找，查找到要插入的位置；查找结点；删除结点（删除结点相对来说比较复杂，不能使二叉树的特性不满足BST特性）
删除结点：
1. 删除叶子结点：直接删除
2. 删除只具有单孩子结点：删除后需要将孩子结点与自己的父亲结点相连
3. 删除具有左右孩子的结点：删除后谁做根结点，一般是右结点的左子树的最左孩子


// 查找是否含有key值
// 这是迭代写法 也可以递归写法
bool searchBST(BinarySortTree *root，int key){
    if (root == NULL)
        return false;
    BinarySortTree *current = root;
    while (root != NULL){
        if (key == current->data)
            return true;
        else if (key < current->data)
            current = current->leftchild;
        else
            current = current->rightchild;
    }
    return false;
}

// 插入结点
// 如果遇到重复的元素可以根据自己的定义将它归到左子树或者右子树
void insertBST(BinarySortTree *root，int key){
    BinarySortTree *current = root;
    BinarySortTree *pre = NULL;

    while (current != NULL){
        pre = current;
        if (key < current->data)
            current = current->leftchild;
        else if (key>current->data)
            current = current->rightchild;
        else
            return;
    }

    BinarySortTree newnode;
    newnode = (BinarySortTree)malloc(sizeof(BinarySortTreeNode));
    newnode->data = key;
    newnode->leftchild = newnode->rightchild = NULL;
    
    // prev 是要安放的结点的父亲结点
    if (current == NULL)
        current->data = key;
    else if (key < pre->data)
        pre->leftchild = newnode;
    else
        pre->rightchild = newnode;
}

6. 平衡二叉树（树的应用）

为了避免树的高度增加过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，保证任意结点左右子树的高度差不会超过1，并将这样的二叉树称之为平衡二叉树（AVL）
左子树与右子树的高度差称之为平衡因子，平衡因子的值只能为-1,0,1
平衡二叉树可以是一棵空树，它的左子树和右子树都是平衡二叉树，且左右子树的高度差绝对值不超过1.
1. 思路1：遍历树的每个结点时，调用函数tree_height得到它的左右子树的深度，如果每个结点的左右子树的深度相差不超过1，按照定义就是一棵平衡二叉树
2. 思路2：后序遍历，在遍历每一个结点的时候记录下它的高度，可以一边遍历一边判断每个结点是不是平衡的
3. 思路3：求出根结点的最大深度和最小深度，最大深度和最小深度之差就是任一子树深度差的最大值

//后序遍历
bool isBalanced(BinaryNode* root, int *pDepth){
    if (root == NULL){
        *pDepth = 0;
        return true;
    }
    int left, right;
    if (isBalanced(root->leftchild, &left) && isBalanced(root->rightchild, &right)){
        int diff = left - right;
        if (diff <= 1 && diff >= -1){
            *pDepth = 1 + (left>right ? left : right);
            return true;
        }
    }
    return false;
}

//最大深度和最小深度的差
int maxDepth(BinaryNode *root){
    if (root == NULL)
        return 0;
    return 1 + max(maxDepth(root->leftchild), maxDepth(root->rightchild));
}

int minDepth(BinaryNode *root){
    if (root == NULL)
        return 0;
    return 1 + min(minDepth(root->leftchild), minDepth(root->rightchild));
}

bool isBalanced(BinaryNode *root){
    return (maxDepth(root) - minDepth(root) <= 1);
}

7. 哈夫曼树和哈夫曼编码

[转载]Huffman树

哈夫曼编码是一种可变长度编码，其特点是对频率高的字符赋予短编码，频率低的字符赋予较长的编码，从而使得平均编码长度减短，从而起到压缩数据的效果。

8. 红黑树

红黑树是众多平衡搜索树中的一种，可保证在最坏情况下插入，搜索，删除等集合操作时间复杂度为O(lgn);
红黑树是二叉搜索树，它在叶子结点上增加了一个存储位来表示结点的颜色（red/black）
红黑性质：
1. 每个结点或是红色的，或是黑色的
2. 根结点是黑色的
3. 每个叶结点是黑色的
4. 如果一个结点是红色的，则它的两个子结点都是黑色的
5. 对与每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

9. B树和B+ 树

B树是专门为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树（非二叉树），B树类似红黑树，但是不同之处在于B树的结点可以有很多孩子，从数个到数千个
B+树：B树的一个常见的变种；

二叉树