四、树

引子：二分查找

int BinarySearch(List tbl,ElementType k)
{
    int left,right,mid,NoFound = -1;
    left = 0;
    right = tbl->length - 1;
    while (left <= right) {
        mid = (left + right)/2;
        if(k < tbl->data[mid])
            right = mid - 1;
        else if (k > tbl->data[mid])
            left = mid + 1;
        else
            return mid;
    }
    return NoFound;
    
}

树

树(Tree): n(n>0)个节点构成的集合。
当n=0时，为空树。
对于一棵非空树(n>0)，它具有一下性质：

树中有一个称为“根(Root)”的特殊结点，用r表示;
其余结点可分为m(m>0)个互不相交的有限集T1，T2,..，Tm，其中每个集合本身又是一棵树，称为原来树的“子树(SubTree)'
n个节点的树有n-1个边

树的一些基本术语：

结点的度(Degree):结点的子树个数
树的度:树的所有结点中最大的度数
叶结点 (Leaf):度为0的结点
父结点 (Parent):有子树的结点是其子树
的根结点的父结点
子结点 (Child):若A结点是B结点的父结
点，则称B结点是A结点的子结点;子结点也称孩子结点。
兄弟结点(Sibling):具有同一父结点的各
结点彼此是兄弟结点。
路径和路径长度:从结点n,到n的路径为一
个结点序列n1,n2 ,… ，n ,n是 n+的父结点。路径所包含边的个数为路径的长度。
祖先结点(Ancestor):沿树根到某一结点路
径上的所有结点都是这个结点的祖先结点。
子孙结点(Descendant):某一结点的子树
中的所有结点是这个结点的子孙。
结点的层次(Level):规定根结点在1层，其它任一结点的层数是其父结点的层数加1。12.树的深度(Depth):树中所有结点中的最大层次是这棵树的深度。

二叉树

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

1. 特殊的二叉树

斜二叉树

斜二叉树
满二叉树：一棵深度为k且有2ⁿ-1个节点的二叉树

满二叉树
完全二叉树：一棵深度为k有n个节点的二叉树，当且仅当每个节点的编号与深度为k的满二叉树中的编号一一对应的二叉树

完全二叉树

2. 二叉树的几个性质

一个二叉树第i层最多有2^i-1个结点(i>=1)
深度为k的二叉树最大结点数为2^k -1 (k>=1)
对于任何非空二叉树T, n₀表示叶子结点个数，n₂表示度为2的非叶子结点个数，那么满足n₀ = n₂ + 1;

3. 二叉树的存储结构

1. 顺序存储结构

但是对于一般二叉树来说如果补全空缺位，改成完全二叉树之后在存储会造成空间浪费。

2. 链式存储结构

4. 二叉树的遍历

1. 先序遍历

1. 访问根结点
2. 先序访问左子树
3. 先序访问右子树

1. 递归遍历
void PreOrserTraversal(BinTree BT)
{
    if(BT){
        printf("%d",BT->data);
        PreOrserTraversal(BT->left);
        PreOrserTraversal(BT->right);
    }
}
2. 非递归遍历
void PreOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack s = CreateStack(MAXSIZE);
    while (T || !IsEmpty(s)) {
        if(T){
            Push(T);
            printf("%d",T->data);
            T = T->left;
        }else{
            T = Pop(s);
            T -> right;
        }
    }
}

2. 中序遍历

1. 中序访问左子树
2. 访问根结点
3. 中序访问右子树

1. 递归遍历
void InOrderTraversal(BinTree BT)
{
    if(BT){
        InOrderTraversal(BT->left);
        printf("%d",BT->data);
        InOrderTraversal(BT->right);
    }
}
2. 非递归遍历
void InOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack s = CreateStack(MAXSIZE);
    while (T || !IsEmpty(s)) {
        if(T){
            Push(T);
            T = T->left;
        }else{
            T = Pop(s);
            printf("%d",T->data);
            T = T->right;
        }
    }
}

3. 后序遍历

1. 后序访问左子树
2. 后序访问右子树
3. 访问根结点

1. 递归遍历
void PostOrderTraversal(BinTree BT)
{
    if(BT){
        PostOrderTraversal(BT->left);
        PostOrderTraversal(BT->right);
        printf("%d",BT->data);
    }
}

2. 非递归遍历
void PostOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack s = CreateStack(MAXSIZE);
    while (T || !IsEmpty(s)) {
        if(T){
            Push(T);
            T = T->left;
        }else{
            T = Pop(s);
            if(T->right == NULL || T->flag == 1){
                printf("%d",T->data);
                T = NULL;
            }else{
                Push(T);//重新入栈
                T->flag == 1; // flag表示已经访问过右子树了
                T = T->right;
            }
        }
    }
}

4. 层序遍历

1. 先将根结点入队列
2. 从队列中取出结点并访问
3. 然后将该结点的所有非空子结点入队列

void LevelOrderTraversal(Bin�Tree BT)
{
    Queue Q;
    BinTree T;
    if(!BT) return;
    Q = CreateQueue(MAXSIZE);
    EnQueue(Q, BT);
    while (!IsEmpty(Q)) {
        T = DeQueue(Q);
        printf("%d",T->data);
        if(T->left) EnQueue(Q,T->left);
        if(T->right) EnQueue(Q, T->right);
    }
}

5. 遍历应用例子

1. 遍历二叉树中的叶子结点

void PreOrserTraversal(BinTree BT)
{
    if(BT){
       if(!BT->left && !BT->right)
        printf("%d",BT->data);

        PreOrserTraversal(BT->left);
        PreOrserTraversal(BT->right);
    }
}

这个例子也可以用中序和后序

2. 求二叉树的高度

int PostOrderGetHeight(BinTree BT)
{
    int Max, HL, HR;
    if(BT){
        HL = PostOrderGetHeight(BT->left);
        HR = PostOrderGetHeight(BT->right);
        Max = HL > HR ? HL : HR;
        return Max + 1;
    }
    return 0;
}

6. 二叉树同构问题

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。现给定两棵树，请你判断它们是否是同构的。

1. 二叉树静态链表表示

2. 建二叉树

Tree BuildTree(struct TreeNode T[])
{
    int N, Root = Null;
    char cl,cr;
    scanf("请输入结点个数：%d\n",&N);
    int *check = (int *)malloc(N*sizeof(int));
    if(N){
        for (int i = 0; i<N; i++) check[i] = 0;
        for (int i = 0; i<N; i++) {
            scanf("%c,%c,%c\n",&T[i].Element,&cl,&cr);
            if(cl != '-'){
                T[i].left = cl - '0';
                check[T[i].left] = 1;
            }else{
                T[i].left = Null;
            }
            
            if(cr != '-'){
                T[i].right = cr - '0';
                check[T[i].right] = 1;
            }else{
                T[i].right = Null;
            }
        }
        
        for (int i = 0; i<N; i++) {
            if(!check[i]) break;
        }
        Root = i;
    }
    return Root; //返回根结点索引
}

3. 判定同构

int Isomorphic(Tree R1,Tree R2)
{
    if(R1==Null && R2==Null)
        return 1;
    if((R1==Null && R2!=Null) || (R1!=Null && R2==Null))
        return 0;
    if(T1[R1].Element != T2[R2].Element)
        return 0;
    if(T1[R1].left == Null && T2[R2].left == Null)
        return Isomorphic(T1[R1].right,T2[R2].right);
    if((T1[R1].left != Null && T2[R2].left != Null)&&
       (T1[T1[R1].left].Element == T2[T2[R2].left].Element))
        return Isomorphic(T1[R1].left,T2[R2].left)&&Isomorphic(T1[R1].right,T2[R2].right);
    else
        return Isomorphic(T1[R1].left,T2[R2].right)&&Isomorphic(T1[R1].right,T2[R2].left);
    
}

二叉搜索树

二叉搜索树: 一棵二叉树，可以为空;如果不为空，满足以下性质:

非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。

二叉搜索树操作的特别函数:

Position Find( ElementType X, BinTree BST):从二叉搜索树BST中查找元素X，返回其所在结点的地址;
Position FindMin( BinTree BST):从二叉搜索树BST中查找并返回最小元素所在结点的地址;
Position FindMax( BinTree BST):从二叉搜索树BST中查找并返回最大元素所在结点的地址。
BinTree Insert(ElementType X, BinTree BST )
BinTree Delete(ElementType X, BinTree BST )

1. 递归查找法
Position Find( ElementType X, BinTree BST)
{
    if(!BST) return NULL;
    if(X > BST->Data)
        return Find(X, BST->Right);
    else if(X < BST->Data)
        return Find(X, BST->Left);
    else
        return BST;
}
2. 非递归查找法
Position IterFind(ElementType X, BinTree BST)
{
    while (BST) {
        if(X > BST->Data)
            BST = BST->Right;
        else if (X < BST->Data)
            BST = BST->Left;
        else
            return BST;
    }
    return NULL;
}
3. 查找最小元素 递归法
Position FindMin( BinTree BST)
{
    if(!BST)
        return NULL;
    else if (!BST->Left)
        return BST;
    else
        return FindMin(BST->Left);
}
4. 查找最大元素 非递归法
Position FindMax( BinTree BST)
{
    if(BST)
        while (BST->Right) {
            BST = BST->Right
        }
    
    return BST;
}
5. 递归插入
BinTree Insert(ElementType X, BinTree BST )
{
    if(!BST){
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else if(X < BST->Data)
            BST->Left = Insert(X, BST->Left);
    else if (X > BST->Data)
        BST->Right = Insert(X, BST->Right)
        
    return BST;
}

二叉搜索树的删除

考虑三种情况：

要删除的结点是叶子结点：直接删除，并将父结点指针置为NULL
要删除的结点有一个孩子结点：删除该结点，并将父结点的指针指向这个孩子结点
要删除的结点有左右子树：用另一个结点替代被删除的结点：左子树最大元素或右子树的最小元素

BinTree Delete(ElementType X, BinTree BST )
{
    BinTree Tmp;
    if(!BST)
        printf("要删除的元素未找到");
    else if(X < BST->Data)
        BST->Left = Delete(X,  BST->Left);
    else if (X > BST->Data)
        BST->Right = Delete(X, BST->Right);
    else if (BST->Left && BST->Right){
        Tmp = FindMin(BST->Right);
        BST->Data = Tmp->Data;
        BST->Right = Delete(Tmp->Data, BST->Right);
    }else{
        Tmp = BST;
        if(!BST->Left)
            BST = BST->Right;
        else if (!BST->Right)
            BST = BST->Left;
        free(Tmp);
    }
    
    return BST;
    
}

平衡二叉树

可以看出(b)的查找效率最高，越平衡的树查找效率越高。
平衡因子(Balance Factor 简称:BF): BF = h_L - h_R , h_L h_R 分别为左右子树高度。
平衡二叉树(AVL树)： 空树，或者任意左右子树的高度差绝对值不超过1，即|BF(T)|<=1。

平衡二叉树的调整

LL旋转

LR旋转

RR旋转

RL旋转

1. 判断二叉树是否平衡
bool noBalance = false;
struct TreeNode *rjt = NULL;

int checkTreeBalance(struct TreeNode *root)
{
    if(NULL == root) return 0;
    int l = checkTreeBalance(root->left);
    int r = checkTreeBalance(root->right);
    if(noBalance) return 0;
    
    int dif = abs(l - r);
    if(dif > 1){
        noBalance = true;
        rjt = root;
    }
    return l > r ? l + 1 : r + 1;
}
2. 父结点查询
TreeNode* queryTopData(TreeNode *root, int data)
{
    TreeNode *top = NULL;
    TreeNode *tmp = root;
    
    while (tmp != NULL) {
        if(data == tmp->data){
            return top;
        }
        
        top = tmp;
        
        if(data > tmp->data)
            tmp = tmp->right;
        else if(data < tmp->data)
            tmp = tmp->left;
    }
    return NULL;
}
3. 左左旋转
//不平衡二叉树
           70
           / \
          50  80
         /  \
        40  60
        /
       30
// 左左旋转后的二叉树
         50
         / \
        40 70
        /  / \
       30 60 80
bool rotateLL(TreeNode **root, TreeNode *notBalanceRoot)
{
    if(*root != notBalanceRoot){
        printf("左左旋转，非根结点");
         //查找不平衡结点的父结点
        TreeNode *fNode = queryTopData(*root,notBalanceRoot->data);
        if(fNode == NULL) return false;

        TreeNode *left = notBalanceRoot->left;
        TreeNode *lright = left->right;

        left->right = notBalanceRoot;
        notBalanceRoot->left = lright;
        
        if(notBalanceRoot == fNode->left)
            fNode->left = left;
        else if (notBalanceRoot == fNode->right)
            fNode->right = left;
        
        return true;
    }else{
        printf("左左旋转，根结点");
        
        TreeNode *left = notBalanceRoot->left;
        TreeNode *lright = left->right;
        
        left->right = notBalanceRoot;
        *root->left = lright;
        
        *root = left;
        return true;
    }
}

4. 左右旋转
//不平衡二叉树
        70
       /  \
      50   80
     /  \
    40  60
        /
       55
//左右旋转后的二叉树
        60
        / \
       50  70
      /  \  \
     40  55  80
bool rotateLR(TreeNode **root, TreeNode *notBalanceRoot)
{
    if(*root != notBalanceRoot){
        printf("左右旋转，非根结点");
        
        TreeNode *fNode = queryTopData(*root,notBalanceRoot->data);
        if(fNode == NULL) return false;
        
        TreeNode *left = notBalanceRoot->left;
        TreeNode *lright = left->right;
        TreeNode *lrightLeft = lright->left;
        TreeNode *lrightRight = lright->right;
        
        lright->left = left;
        lright->right = notBalanceRoot;
        left->right = lrightLeft;
        notBalanceRoot->left = lrightRight;
        
        if(notBalanceRoot == fNode->left)
            fNode->left = lright;
        else if (notBalanceRoot == fNode->right)
            fNode->right = lright;
        
        return true;
    }else{
        printf("左右旋转，根结点");
        TreeNode *left = notBalanceRoot->left;
        TreeNode *lright = left->right;
        TreeNode *lrightLeft = lright->left;
        TreeNode *lrightRight = lright->right;
        
        lright->left = left;
        lright->right = notBalanceRoot;
        left->right = lrightLeft;
        notBalanceRoot->left = lrightRight;
        
        *root = lright;
        
        return true;
}

5. 右右旋转
//不平衡的二叉树
         70
        /  \
       50   80
           /  \
          75   88
               /
              85
//右右旋转的二叉树
         80
        /  \
       70   88
       / \  /
      50 75 85
bool rotateRR(TreeNode **root, TreeNode *notBalanceRoot)
{
    if(*root != notBalanceRoot){
        printf("右右旋转，非根结点");
        
        TreeNode *fNode = queryTopData(*root,notBalanceRoot->data);
        if(fNode == NULL) return false;
        
        TreeNode *right = notBalanceRooot->right;
        TreeNode *rleft = right->left;
        right->left = notBalanceRoot
        notBalanceRoot->right = rleft;
        
        if(notBalanceRoot == fNode->left)
            fNode->left = right;
        else if(notBalanceRoot == fNode->right)
            fNode->right = right;
        
        return true;
    }else{
        printf("右右旋转，根结点");
        
        TreeNode *right = notBalanceRooot->right;
        TreeNode *rleft = right->left;
        right->left = notBalanceRoot
        notBalanceRoot->right = rleft;
        
        *root = right;
        
        return true;
    }
}
6. 右左旋转
//不平衡二叉树
        70
       /  \
      50   80
          /  \
         75   88
           \
           77
//右左旋转后的二叉树
        75
       /  \
      70   80
     /    /  \
    50   77   88
bool rotateRL(TreeNode **root,TreeNode *notBalanceRoot)
{
    if(*root != notBalanceRoot){
        printf("右左旋转，非根结点");
        
        TreeNode *fNode = queryTopData(*root,notBalanceRoot->data);
        if(fNode == NULL) return false;
        
        TreeNode *right = notBalanceRoot->right;
        TreeNode *rleft = right->left;
        TreeNode *rleftLeft = rleft->left;
        TreeNode *rleftRight = rleft->right;
        
        rleft->left = notBalanceRoot;
        rleft->right = right;
        
        notBalanceRoot->right = rleftLeft;
        right->left = rleftRight;
        
        if(notBalanceRoot == fNode->left)
            fNode->left = rleft;
        else if (notBalanceRoot == fNode->right)
            fNode->right = rleft;
        
        return true;
    }else{
        printf("右左旋转，根结点");
        
        TreeNode *right = notBalanceRoot->right;
        TreeNode *rleft = right->left;
        TreeNode *rleftLeft = rleft->left;
        TreeNode *rleftRight = rleft->right;
        
        rleft->left = notBalanceRoot;
        rleft->right = right;
        
        notBalanceRoot->right = rleftLeft;
        right->left = rleftRight;
        
       *root = rleft;
        
        return true;
    }
}

最后编辑于：2023.10.23 17:48:04

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 223,858评论 6赞 521
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 95,753评论 3赞 402
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 170,876评论 0赞 366
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 60,560评论 1赞 300
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 69,574评论 6赞 399
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 53,097评论 1赞 314
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 41,477评论 3赞 427
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 40,452评论 0赞 278
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,980评论 1赞 324
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 39,017评论 3赞 343
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 41,168评论 1赞 354
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,807评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 42,497评论 3赞 336
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,976评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 34,094评论 1赞 275
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 49,659评论 3赞 380
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 46,196评论 2赞 363

四、树