树相关代码

树相关代码

1. 二叉树链式存储结构描述

typedef struct BiTNode{
    int data;                        //数据域
    struct BiTree *lchild, *rchild;  //左、右孩子指针
}BiTNode, *BiTree;

2. 先序遍历

void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);             //访问根节点
        PreOrder(T->lchild);  //递归遍历左子树
        PreOrder(T->rchild);  //递归遍历左子树
    }
}

3. 中序遍历

void PreOrder(BiTree T){
    if(T != NULL){
        PreOrder(T->lchild);  //递归遍历左子树
        visit(T);             //访问根节点
        PreOrder(T->rchild);  //递归遍历左子树
    }
}

4. 后序遍历

void PreOrder(BiTree T){
    if(T != NULL){
        PreOrder(T->lchild);  //递归遍历左子树
        PreOrder(T->rchild);  //递归遍历左子树
        visit(T);             //访问根节点
    }
}

5. 层次遍历（层次遍历是利用队列作为辅助结构，并且只有层次遍历时循环语句是只用队列是否为空作为判断条件的，其他遍历方式均为判定结点不为空或者栈不为空）

void LevelOrder(BiTree T){
    BiTree Queue[maxsize];              //初始化辅助队列
    int front = -1, rear = -1;
    BiTree p;                           //p用于遍历二叉树
    Queue[++rear] = T;                  //将根节点入队Q
    while(front!=rear){                 //队列不为空则循环
        p = Queue[++front];             //队头结点出队
        visit(p);                       //访问出队结点
        if(p->lchild != NULL){
            Queue[++rear] = p->lchild;  //左子树不为空，则左子树根结点入队
        }
        if(p->rchild != NULL){
            Queue[++rear] = p->rchild;  //右子树不为空，则右子树根节点入队
        }
    }   
}

6. 先序非递归（使用栈来辅助存储的，切勿与层次遍历搞混了）

void PreOrder(BiTree T){
    BiTree Stack[maxsize];     //初始化辅助栈S
    int top = -1;              //栈的下标
    BiTree p = T;              //p是遍历指针
    while(top!=-1 || p!=NULL){ //栈不空或p不为空时，开始循环
        if(p){                 //一路向左
            visit(p);          //访问当前结点
            Stack[++top] = p;  //入栈元素
            p = p -> lchild;   //左孩子不为空，一直向左走
        }else{                 //出栈，并转向出栈结点的右子树
            p = Stack[top--];  //栈顶元素出栈
            p = p -> rchild;   //向右子树走，p赋值为当前结点的右孩子
                               //返回while循环继续进入if-else语句
        }
    }
}

7. 中序非递归（使用栈来辅助储存的。先序与中序的区别便是：先序是先访问再压栈，中序是出栈后再访问）

void InOrder(BiTree T){
    InitStack(S);              //初始化栈S
    BiTree p = T;              //p是遍历指针
    while(p || !IsEmpty){      //栈不空或p不为空时，开始循环
        if(p){                 //一路向左
            Push(S,p);         //入栈元素
            p = p -> lchild;   //左孩子不为空，一直向左走
        }else{                 //出栈，并转向出栈结点的右子树
            Pop(S,p);          //栈顶元素出栈
            visit(p);          //访问出栈结点
            p = p -> rchild;   //向右子树走，p赋值为当前结点的右孩子
                               //返回while循环继续进入if-else语句
        }
    }
}

8. 后序非递归（后序非递归遍历是最重要的。一定要记住当遍历到某一结点时，栈里存在的元素是其所有的祖先结点）

void PostOrder(BiTree T){
    InitStack(S);
    p = T;                                      //p是遍历指针
    r = NULL;
    while(p || !IsEmpty(S)){
        if(p){                                  //走到最左边
            push(S,p); 
            p = p -> lchild;
        }else{                                  //向右
            GetTop(T,p);                        //读栈顶结点（非出栈）
            if(p->rchild && p->rchild != r){    //若右子树存在，且未被访问过
                p = p -> rchild;                //向右转
                push(S,p);                      //压入栈
                p = p -> lchild;                //再走到最走
            }else{                              //否则，弹出结点并访问
                pop(S,p);                       //将结点弹出
                visit(p->data);                 //访问该节点
                r = p;                          //记录最近访问过的结点
                p = NULL;                       //结点访问完后，重置p指针
            }
        }//else
    }//while
}

9.递归求树的高度

• 写递归时首先需要考虑的便是递归运行到什么时候终止

int Btdepth(BiTree T){
    if(T == NULL){
        return 0;
    }
    int ldep = Btdepth(T->lchild);
    int rdep = Btdepth(T->rchild);
    if(ldep > rdep){
        return ldep + 1;
    }else{
        return rdep + 1;
    }
}

10.递归交换二叉树的左右子树

• 此代码暗含着结点为递归出口

void swap(BiTree b){
//本算法递归的交换二叉树的左、右子树
    if(b){
        swap(b->lchild);
        swap(b->rchild);
        BiTree temp = b -> lchild;
        b->lchild = b->rhcild;
        b->rchild = temp;
    }
}

11.递归删除以某一结点为根节点的子树并释放其存储空间

• 此代码暗含着节点为空时为递归出口

void DeleteXTree(BiTree bt){
    if(bt){
        DeleteXTree(bt->lchild);
        DeleteXTree(bt->rchild);
        free(bt);
    }
}

12.利用层次遍历求树的高度（这里还没看）

int LeverOrder(BiTree T){
    BiTree Queue[maxsize];
    int front=-1,rear=-1,level=0,last=0;
    BiTree p;
    Queue[++rear] = T;
    while(front != rear){
        p = Queue[++front];
        if(p->lchild!=NULL){
            Queue[++rear] = P->lchild;
        }
        if(p->lchild!=NULL){
            Queue[++rear] = P->rchild;
        }
        if(front==last){
            level++;
            last = rear;
        }
    }
}

13.利用层次遍历求树的宽度

int LevelOrder(BiTree T){
    BiTree Queue[maxsize];
    int front=rear=-1,width=last=max=0;
    BiTree p;
    Queue[++rear] = T;
    while(front!=rear){
        p = Queue[++front];
        width++;
        if(p->lchild!=NULL){
            Queue[++rear] = p->lchild;
        }
        if(p->rchild!=NULL){
            Queue[++rear] = p->rchild;
        }
        if(front == last){
            if(max < width){
                max = width;
            }
            last = rear;
        }
    }
    return max;
}

14.求二叉树中叶子结点的个数

int LevelOrder(BiTree T){
    BiTree Queue[maxsize];
    int front=rear=-1,count=0;
    BiTree p;
    Queue[++rear] = T;
    while(front!=rear){
        p = Queue[++front];
        if(p->lchild == NUll && p->rchild == NULL){
            count++;
        }
        if(p->lchild != NUll){
            Queue[++rear] = p->lchild;
        }
        if(p->rchild != NUll){
            Queue[++rear] = p->rchild;
        }
    }
    return count;
}

15.求树中独生叶结点的个数（既是叶结点又无兄弟结点）

int LevelOrder(BiTree T){
    BiTree Queue[maxsize];
    int front=rear=-1;
    int num = 0;
    BiTree p;
    Queue[++rear] = T;
    while(front!=rear){
        p = Queue[++front];
        if(p->lchild != NUll && p->rchild == NULL){
            if(p->lchild->lchild == NUll && p->lchild->rchild == NULL){
                num++;
            }
        }
        if(p->lchild == NUll && p->rchild != NULL){
            if(p->rchild->lchild == NUll && p->rchild->rchild == NULL){
                num++;
            }
        }
        if(p->lchild != NUll){
            Queue[++rear] = p->lchild;
        }
        if(p->rchild != NUll){
            Queue[++rear] = p->rchild;
        }
    }
    if(T->lchild == NULL && T-rchild == NULL){
        num++
    }
    return num;
}

16.求一棵二叉树是否为平衡二叉树

int High(BiTree T){
    if(T == NULL){
        return 0;
    }
    int llen = High(T->lchild);
    int rlen = High(T->rchild);
    if(llen >= rlen){
        return llen+1;
    }else{
        return rlen+1;
    }
}

bool PostOrder1(BiTree T){
    BiTree Stack[maxsize];
    int top = -1;
    BiTree p = T,r = NULL;//p为遍历二叉树指针，r指向最近访问结点
    while(p!=NULL || top!=-1){
        if(p!=NULL){
            Stack[++top] = p;
            p = p->lchild;
        }else{
            p = Stack[top];
            if(p->rchild!=NULL && p->rchild!=r){//p的右孩子不为空，且未被访问过
                p = p->rchild;
                Stack[++top] = p;
                p = p->lchild;
            }else{
                p = Stack[top--];
                if(abs(High(p->lchild)-High(p->rchild))>1){
                    return false;
                }
                r = p;
                p = NULL;
            }
        }
    }
    return true;
}

17.给出二叉树的自下而上、从右到左的层次遍历算法

void InverLevel(BiTree T){
    BiTree Queue[maxsize];
    int front=rear=0;
    BiTree Stack[maxsize];
    int top=-1;
    BiTree p;
    Queue[++rear] = T;
    while(front!=rear){
        p = Queue[++front];
        Stack[++top] = p;
        if(p->lchild！= NULL){
            Queue[++rear] = p;
        }
        if(p->rchild！= NULL){
            Queue[++rear] = p;
        }
    }
    while(top!=-1){
        p = Stack[top--];
        Visit(p);
    }
}

18.线索二叉树的构造，结构描述

• 对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左右指针域是否为空，若为空，讲他们改为指向前驱结点或后继结点的线索
• ltag=0，lchild域指示结点的左孩子；ltag=1，lchild域指示结点的前驱
• ltag=0，rchild域指示结点的右孩子；ltag=1，rchild域指示结点的后继

typedef struct ThreadNode{
    int data;                            //数据元素
    struct ThreadNode *lchild,*rchild;   //左、右孩子指针
    int ltag,rtag;                       //左、右线索标志
}ThreadNode,*ThreadTree;

19.中序二叉树线索化

void InThread(ThreadTree &p, ThreadTree &pre){
    if(p!=NULL){
        Inthread(p->lchild,pre);
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL && pre->rchild == NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(pre->rchild,pre);
    }
}

20.二叉排序树的查找

• 二叉排序树：左＜根＜右

BSTNode *BST_Search(BiTree T,int key){
    p = NULL;
    while(T!=NULL && key!=T-data){
        p = NULL;
        if(key<T->data){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}

21.二叉排序树的插入

BSTNode *BST_Search(BiTree T,int key){
    p = NULL;
    while(T!=NULL && key!=T-data){
        p = NULL;
        if(key<T->data){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    BiTree Bt = (BiTree)malloc(sizeof(BSTNode));
    if(key<p->data){
        p->lchild = BT;
    }
    if(key>p->data){
        p->rchild = BT;
    }
    return T;
}

22.二叉排序树的构造

void Creat_BST(BiTree &T,KeyType str[],int n){
    T = NULL;
    int i = 0;
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}