二叉树

作者: 听风赏花_fc3e | 来源:发表于2018-04-08 19:11 被阅读0次

链表详解

用链表概念辅助理解二叉树，链表一个结点的后区指向下一个链表结点，前区指向上一个链表结点，线性结构。二叉树每个结点都包含左右两个树的指针，从根结点向下发散，只有向下的关联，没有向上的关联。

一个数据域，两个指针域（左右）
遍历方法：前序遍历，中序遍历，后序遍历，层序遍历

前序遍历：根节点 -> 左子树-> 右子树（从上到下，从左到右）
中序遍历：左子树(左最下)-> 向上找它根节点—>它根节点右树->向上找结点一直到根结点 -> 右侧同理
（先最左最下起点，（如果存在右结点，先读右结点）然后，向上查找自己根，再找自己根右结点，然后向上查找自己根上游）
后序遍历：左子树（左最下结点）（如果没有就是右子树）->同层级（右结点）->向上一级根（一次类推到）

二叉树结构图片地址

它的前序遍历顺序为：ABDGHCEIF（规则是先是根结点，再前序遍历左子树，再前序遍历右子树）

它的中序遍历顺序为：GDHBAEICF（规则是先中序遍历左子树，再是根结点，再是中序遍历右子树）

它的后序遍历顺序为：GHDBIEFCA（规则是先后序遍历左子树，再是后序遍历右子树，再是根结点）

二叉树储存结构

typedef struct BiTNode {
    int data ;
    struct BiTNode *left ,*right ;
}

创建二叉树

//二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树

void CreateBiTree(BiTree &T) {
    
    BitNode *T = new TreeNode ;
    char a ;
    cout<<"输入结点的值"<< end1 ；
    cin>> a ; /// 将输入值赋值给a

    if (a == '#')
    {
        T = NULL ;
    }else {
        T->data = a ;
        CreateBiTree(T->right) ;
        CreateBiTree(T->left) ;
    }
}

遍历二叉树

/// 前序
void PreOrderTraverse(BiTree T ){
    if (T == NULL){
        return ;
    }
    printf("%d",T->data);
    PreOrderTraverse(T->left);
    PreOrderTraverse(T->right);
}

/// 中序
void InOrderTraverse(BiTree T ){
    if (T == NULL){
        return ;
    }
    InOrderTraverse(T->left);
    printf("%d",T->data)
    InOrderTraverse(T->right);
}

///后序遍历
void PostOrderTraverse(BiTree T)
{
    if (T == NULL) {
        return ;
    }
    PostOrderTraverse(T->left);
    PostOrderTraverse(T->right);
    printf("%d",T->data);
}

相关常见问题

两个节点的最近公共祖先

搜索二叉树解题思路
- 从根结点开始遍历，如果node1和node2中任意一个和root匹配，那么root匹配的节点就是最低公共祖先。
- 如果都不匹配，则分别递归左，右子书，如果一个节点出现在左子书，并且另一个节点出现在右子树，则root就是最低公共祖先。
- 如果两个结点都出现在左子树，则说明最低公共在左子树中，否则在右子树

高兴再议论

一般二叉树
- 思路从根结点开始遍历，如果node1和node2的任何一个和root匹配，那么root匹配的节点就是最底公共祖先。如果不匹配，则分别递归左，右子树，如果有一个节点出现在左子树，并且另外一个出现在右子树，则root就是最低公共祖先，如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树

///时间复杂度O(N^2)
Node *GetAncestor (Node *root ,Node *x1 ,Node *x2) {
    if (root == NULL || x1 == NULL || x2 == NUL) {
        return NULL ;
    }
    ///如果两个节点是父子关系，其中一个节点为公共祖先
    if (root == x1 || root == x2) {
        return root ;
    }
    
    bool x1inleft ,x2inleft ,x1inright ,x2inright ;
    /// 判断x1是否在左子树
    x1inleft = JudgeNode(root->left ,x1) ;
    /// 判断x1是否在右子树
    x1inright = JudgeNode(root-right ,x1) ;
    /// 判断是否在树中 
    if (x1inleft == NULL || x1inright == NULL) {
        return NULL ;
    }
    
    x2inleft = JudgeNode(root->left,x2)；
    x2inRight = JudgeNode(root->right,x2);
    if(x2inleft == NULL || x2inright == NULL) {
        return NULL ;
    }
    
    /// 一个在左 一个在右
    if ((x1inleft && x2inright) || (x1inright && x2inright)) {
        return root ;
        
    }else if (x1inleft && x2inleft) {
    /// 都在左
        return GetAncestor(root->left,x1,x2);
    }else {
    /// 都在右
        return GetAncestor(root->right ,x1,x2);
    }
}

BiTNode *JudgeNode(BiTNode *node ,x) {
    
    if (node == NULL) {
        return NULL ;
    }
    
    if (node->data == x) {
        return node ;
    }
    
    BiTNode *nodeL = JudgeNode(node->left ,x);
    if (nodeL && nodeL->data == x) {
        return nodeL ;
    }
    BiTNode *nodeR = JudgeNode(node->right ,x);
    if (nodeR && nodeR->data == x) {
        return nodeR ;
    }
    
}

时间复杂度O（N），但是需要额外空间来储存路径
1. 找到node1 的路径，并储存在一个向量或数组中。
2. 找到node2的路径，储存向量或数组中
3. 遍历这两条路径，直到遇到一个不同的节点， 则前面的那个即为最低公共祖先

///第三个参数 定义栈空间类型为
bool GetNodePaths (BiTNode *root ,BiTNode *node ,stack<BiTNode *> & s) {
    
    if (root == NULL) {
        return false ;
    }
    s.push(root) ;/// 将root 压入栈空间
    
    if (root == node) {
        return true ;
    }
    
    /// 判断在左右分支 在返回ture
    bool inleft = GetNodePaths(root->left ,node ,s) ;
    if (inleft) {
        return true ;
    }
    
    bool inright = GetNodePaths(root->right,node,s) ;
    if (inright) {
        return true ;
    }
    ///推出栈空间
    s.pop();
    return false ;
    
}

Node *GetAncestor(Node *root ,Node *x1 ,Node *x2) {
    if (x1 != NULL && x2 != NULL) {
        return NULL ;
    }
    stack<Node *>paths1,paths2 ;
    if (!GetNodePaths(root->left,x1, paths1) || !GetNodePaths(root->right ,x2 ,paths2)){
        return NULL ;
    }else {
        while (paths1.size()>paths2.size()) {
            paths1.pop() ;
        }
        while (paths1.size()<paths2.size()) {
            paths2.pop();
        }
        while (!paths1.empty() && !paths2.empty() && paths1.top() != paths2.top()) {
            
            if(paths1.top() == paths.top()) {
                return paths1.top();
            }
            
            paths1.pop();
            paths2.pop();
        }
    }
    
    return NULL ;
}

2.最远的两个节点的距离

有两种情况
第一种，最远两个节点，的距离为它们到根节点路径长度之和
第二种 有可能距离最远的两个节点之间的路不经过根节点

第一种解法
借助两个子树的高度求解，但是要递归整棵树，如果子树中出现第二种情况要更新最大距离，时间复杂度为O(N)

size_t MaxLen(){
    size_t maxLen = 0 ;
    _MaxLen(_root ,maxLen);
    return maxLen ;
}

void _MaxLen(Node *root ,size_t maxLen) {
    
    if (root == NULL) {
        return 0 ;
    }
    
    size_t left = _MaxLen(root-left ,maxlen) ;
    size_t right = _MaxLen(root-right,maxlen);
    
    if(right+left > maxLen) {
        maxlen = right + left ;
    }
    
    /// 算上根节点
    return left > right ? left + 1 : right +1 ;
  
}

根据前序遍历和中序遍历重建二叉树
前序序列 123456
中序序列 324165
image
图片地址<html>
https://images2017.cnblogs.com/blog/1069650/201707/1069650-20170730115803599-1410818404.png
</html>

/// 应当先看图，div 相当于计数位
Node *RebulidTree(char *prev ,char *inbgein,char *inend) {
    
    if (prev == NULL || inbegin && inend) {
        
        return NULL ;
    }
    Node *root = new Node(*per);/// 创建根节点
    char *div = inbgin ; ///div 查找根节点
    while (div < inend) {
        if (*div == *perv) {
            if (inbegin <= div - 1) {
                root->left = RebulidTree(++prev ,inbegin,div- 1); /// 递归创建子树
            }else {
                root->left = NULL ;
            }
            if (div + 1 <= inend) {
                root ->right = RebulidTree(++orev ,div + 1 ,inend); /// 递归创建右子树
            }else {
                root -> right = NULL ;
            }
            break ;
        }
        ++ div ;
    }
    
    return root ;
}

4.判断一棵树是否是完全二叉树

完全二叉树，前n-1蹭都是满的，第n层如果空缺，则是缺在右边，即第n层的最右边节点，它的左边是满的，右边是空的

///将所有节点全部压入对了中，每次判断队列的头为空 则跳出循环，如果此后队列中还有元素则不是完全二叉树
/// queue （线性表）
队列是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

bool IsCompleteTree (TNode *pRoot) {
    if (pRoot == NULL) {
        ruturn false ;
    }
    queue<TNode *> q ;
    q.push(pRoot) ;
    TRoot *pCur = q.front();
    while (pCur != NULL) {
        q.pop();
        q.push(pCur->left);
        q.push(pCur->right);
        pCur = q.front();
    }
    q.pop() ;
    
    while (!q.empty()) {
        if (q.front() != NULL) {
            ruturn false ;
        }
        q.pop();
    }
    
    return true ;
}

将二叉树转换成一个排序的双向链表

void _ToList(BiTNode *root ,BiTNode *&lastNode) {
    
    if (root = NULL) {
        return ;
    }
    BitNode *pCur = root ;
    if (pCur->left != NULL) {
        _ToList(pCur->left ,lastNode);
    }
    pCur-> left = lastNode ;
    if (lastNode != NULL)  {
        lastNode ->right = pCur ;
    }
    lastNode = pCur ;
    if (pCur->right != NULL) {
        ConvertNode(pCur->right,lastNode) ;
    }
}

BitNode *toList (BitNode *HeadTree) {
    BitNode *lastNode = NULL ;
    _ToList(HeadTree ,lastNode) ;
    BSNode *cur =lastNode ;
    while (cur && cur->left) {
        cur = cur->left ;
    }
    return cur ;
}

6 . 求二叉树宽度
所谓二叉树的宽度是指：二叉树各层节点个数的最大值。

我们知道层序遍历二叉树是使用 queue 来实现的：每次打印一个节点之后，如果存在左右子树，则把左右子树压入 queue，那么此时的队列中可能既包含当前层的节点，也包含下一层的节点。

而我们要求的是对于特定某一层的节点的个数，因此我们需要从头结点开始，记录每一层的个数，对于当前层的每一个节点，在弹出自身之后把其左右子树压入 queue，当把当前层全部弹出队列之后，在队列中剩下的就是下一层的节点。然后比较队列的size和之前得到的maxWidth，取最大值即为队列的宽度。最终队列为空，得到的maxWidth就是二叉树的宽度！

int With(Node *root) {
    
    queue<Node *>q ;
    if (root) {
        q.push(root) ;
    }
    int maxwith = 1 ;
    while (!q.empty() ){
    
        int lenght = q.size() ;
        while (length -- > 0)
        {
            Node *front = q.front();
            q.pop();
            if (front->left) {
                q.push(front ->left);
            }
            if (front->right) {
                q.push(front ->right) ;
            }
        }
        maxwith = maxwidth > q.size()? maxwidth : q.size() ;
    }
    return maxwidth ;
}

二叉树是否是平衡树

二叉树中每一个节点的左右子树高度之差均小于2即为平衡二叉树。那么当一颗二叉树的所有子树都是平衡二叉树时，它本身必定为平衡二叉树，用此思想可递归判断二叉树是否是平衡二叉树

bool IsBalance(Node* root, int& depth)  //O(N)
    {
        if (root == NULL)
        {
            depth = 0;
            return true;
        }
        int leftdepth = 0;
        if (IsBalance(root->_left, leftdepth) == false)
        {
            return false;
        }
        int rightdepth = 0;
        if (IsBalance(root->_right, rightdepth) == false)
        {
            return false;
        }
        depth = rightdepth > leftdepth ? rightdepth + 1 : leftdepth + 1;
        return abs(leftdepth - rightdepth) < 2;
    }

8 .二叉树是否为另一颗树的子树

先在找二叉树里找根节点，找到之后判断后续的节点是否相等，如果相等，则为子树

bool JudgeNextTree(Node *next ,Node *child)///两棵树的起始节点的值已经相等，在判断其他节点是否相等  {
   if (child == NULL)
   {
       return ture;
   }
   if (next == NULL) 
   {
       return false ;
   }
   if (next->data == child->data) {
       return JudgeNextTree (next->left ,chiled->left) && JudgeNextTree(next->right,child->right);
   }else {
       return false ;
   }
}

bool JudgeTree(Node *parent ,Node *child)判断child是否为parent的子树
{
    if (child == NULL)///空树是任何树的子树 {
        return ture ;
    }    
    if (parent == NULL)///空树没有除空树的任何子树 {
        return false ;
    }
    if (parent->data == child->data)///当前节点与要查找子树的根节点相同时{
        return JudgeNextTree(parent ,child);///从相等节点开始判断是否为子树
    }else if (JudgeTree(parent->left,child->left) == true)///判断当前节点的左子树是否与要查找子树的根节点相同 {
        return true ;
    }else {
    /// 判断当前节点的右子树是否与要查找的子树根节点相同
        return JudgeTree(parent->right ,child->right);
    }
    
}

二叉树

用链表概念辅助理解二叉树，链表一个结点的后区指向下一个链表结点，前区指向上一个链表结点，线性结构。二叉树每个结点都包含左右两个树的指针，从根结点向下发散，只有向下的关联，没有向上的关联。

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读