题目6.39：

题目里面注明了mark如何使用，也让我学习到了一定的知识

//利用mark(0:继续向左 1:向右 2:访问并回到双亲)的三叉链表的后序遍历（不用栈）
#include<iostream>
using namespace std;
#define TElemType double
typedef struct BiTNode
{
    TElemType data;
    int mark;//标志变量0:继续向左 1:向右 2:访问该结点
    struct BiTNode* lchild,* rchild,* parent;//在二叉链表的基础上+parent构成三叉链表
}BiTNode,* BiTree;

void Creat_BiTree(BiTree& T,BiTree parent)//在原来创建二叉树的情况下设置双亲指针的值
//递归构建三叉链表是在递归构建二叉链表的基础上
//parent存放 指向T的双亲结点 的指针，若为根结点，则parent为nullptr
{
    TElemType num;
    if(cin>>num){
        T=new BiTNode;
        if(!T) exit(-2);
        T->data=num;
        T->parent=parent;//设置双亲
        T->mark=0;//新开辟的结点的mark设为0
        Creat_BiTree(T->lchild,T);
        Creat_BiTree(T->rchild,T);
    }
    if(!cin){
        T=nullptr;
        if(parent)//为了后序遍历
            parent->mark++;//每有一个孩子(即T)为空，则parent的mark++
        cin.clear();
        cin.sync();
    }
}

void PreOrder_BiTree(BiTree T)//先序遍历打印三叉链表每个结点的mark值
{
    if(T){
        cout<<T->mark<<endl;
        PreOrder_BiTree(T->lchild);
        PreOrder_BiTree(T->rchild);
    }
}
void PostOrder_BiTree(BiTree T)//利用mark对三叉链表进行后序遍历
{
    BiTree p=T;
    while(p){//当p为空结束循环
        while(p->mark==0){//0：继续向左  “继续”体现了循环，所以用while
            p->mark++;
            p=p->lchild;
        }
        if(p->mark==1){//1：向右
            p->mark++;
            p=p->rchild;
        }
        if(p->mark==2){//2：访问并回到双亲结点
            cout<<p->data<<endl;
            p=p->parent;
        }
    }
}

int main()
{
    BiTree T;
    Creat_BiTree(T,nullptr);//根结点的双亲为空
    cout<<"检验mark值:\n";
    PreOrder_BiTree(T);//带mark的三叉链表构建完成后，检验每个结点的mark值
    cout<<"检验完成\n";
    PostOrder_BiTree(T);
    return 0;
}

1
2
4
@
7
3
@
@
4
@
@
5
@
@
3
@
@
检验mark值:
0
0
1
0
2
2
2
2
检验完成
3
4
7
4
5
2
3
1

Process returned 0 (0x0)   execution time : 4.365 s
Press any key to continue.

静态数组实现二叉树

二叉链表实现二叉树

三叉链表实现二叉树

线索二叉树

三叉链表存储结构

数据结构

//二叉树的三叉链表存储表示
typedef struct BiTPNode
{
    TElemType data;
    BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
} BiTPNode, *BiPTree

存储示例

代码实现

main.c

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-07-22     tyustli      first version
 */

#include "tree.h"

void visitT(BiPTree T)
{
    if (T) // T非空
        printf("%d ", T->data);
}

int main(int argc, char *argv[])
{
    printf("this bitree\r\n");
    int i;
    BiPTree T, c, q;
    TElemType e1, e2;
    InitBiTree(&T);
    printf("构造空二叉树后,树空否？%d(1:是 0:否)树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
    e1 = Root(T);
    if (e1)
        printf("二叉树的根为: %d \n", e1);
    else
        printf("树空，无根\n");

    printf("请按先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n");
    CreateBiTree(&T);
    printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
    e1 = Root(T);
    if (e1)
        printf("二叉树的根为: %d \n", e1);
    else
        printf("树空，无根\n");

    printf("\n先序递归遍历二叉树:\n");
    PreOrderTraverse(T, visitT);
    printf("\n中序递归遍历二叉树:\n");
    InOrderTraverse(T, visitT);
    printf("\n后序递归遍历二叉树:\n");
    PostOrderTraverse(T, visitT);
    printf("\n层序遍历二叉树:\n");
    LevelOrderTraverse(T, visitT);
}

/***************** end of file ******************/

tree.c

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-07-22     tyustli      first version
 */

#include "tree.h"

// 二叉树的三叉链表存储的基本操作

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

TElemType Nil = 0; // 设整型以0为空

// 操作结果：构造空二叉树T
void InitBiTree(BiPTree *T)
{
    *T = NULL;
}

// 初始条件：二叉树T存在。
// 操作结果：销毁二叉树T
void DestroyBiTree(BiPTree *T)
{
    if (*T) // 非空树
    {
        if ((*T)->lchild)                 // 有左孩子
            DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树
        if (&(*T)->rchild)                // 有右孩子
            DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树
        free(*T);                         // 释放根结点
        *T = NULL;                        // 空指针赋0
    }
}

// 按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造三叉链表表示的二叉树T
void CreateBiTree(BiPTree *T)
{
    TElemType ch;
    scanf("%d ", &ch);
    if (ch == Nil) // 空
    {
        *T = NULL;
    }
    else
    {
        *T = (BiPTree)malloc(sizeof(BiTPNode)); // 动态生成根结点
        if (!*T)
            exit(-1);
        (*T)->data = ch;               // 给根结点赋值
        (*T)->parent = NULL;           // 根结点无双亲
        CreateBiTree(&(*T)->lchild);   // 构造左子树
        if ((*T)->lchild)              // 有左孩子
            (*T)->lchild->parent = *T; // 给左孩子的双亲域赋值
        CreateBiTree(&(*T)->rchild);   // 构造右子树
        if ((*T)->rchild)              // 有右孩子
            (*T)->rchild->parent = *T; // 给右孩子的双亲域赋值
    }
}

// 初始条件：二叉树T存在。
// 操作结果：若T为空二叉树，则返回TRUE，否则FALSE
Status BiTreeEmpty(BiPTree T)
{
    if (T)
        return FALSE;
    else
        return TRUE;
}

// 初始条件：二叉树T存在。
// 操作结果：返回T的深度
int BiTreeDepth(BiPTree T)
{
    int i, j;
    if (!T)
        return 0; // 空树深度为0
    if (T->lchild)
        i = BiTreeDepth(T->lchild); // i为左子树的深度
    else
        i = 0;
    if (T->rchild)
        j = BiTreeDepth(T->rchild); // j为右子树的深度
    else
        j = 0;
    return i > j ? i + 1 : j + 1; // T的深度为其左右子树的深度中的大者+1
}

// 初始条件：二叉树T存在。
// 操作结果：返回T的根
TElemType Root(BiPTree T)
{
    if (T)
        return T->data;
    else
        return Nil;
}

// 初始条件：二叉树T存在，p指向T中某个结点。
// 操作结果：返回p所指结点的值
TElemType Value(BiPTree p)
{
    return p->data;
}

// 给p所指结点赋值为value
void Assign(BiPTree p, TElemType value)
{
    p->data = value;
}

#if 1

typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型

typedef struct QNode
{
    QElemType data;     /* 数据域 */
    struct QNode *next; /* 指针域 */
} QNode, *QueuePtr;

typedef struct LinkQueue
{
    QueuePtr front; // 队头指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;

void InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
void ClearQueue(LinkQueue *Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemType *e);
void EnQueue(LinkQueue *Q, QElemType e);
Status DeQueue(LinkQueue *Q, QElemType *e);
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType));
void print(QElemType i);
void InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));

    if (Q->front == NULL)
        exit(-1);
    Q->front->next = NULL;
}

void DestroyQueue(LinkQueue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
}

void ClearQueue(LinkQueue *Q)
{
    QueuePtr p, q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
}
Status QueueEmpty(LinkQueue Q)
{
    if (Q.front->next == NULL)
        return TRUE;
    else
        return FALSE;
}
int QueueLength(LinkQueue Q)
{
    int i = 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p)
    {
        i++;
        p = p->next;
    }
    return i;
}
Status GetHead(LinkQueue Q, QElemType *e)
{
    QueuePtr p;
    if (Q.front == Q.rear)
        return ERROR;
    p = Q.front->next;
    *e = p->data;

    return OK;
}
void EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p;
    if (!(p = (QueuePtr)malloc(sizeof(QNode))))
        exit(-1);
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;
    free(p);

    return OK;
}
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType))
{
    QueuePtr p;
    p = Q.front->next;
    while (p)
    {
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}
void print(QElemType i)
{
    // printf("%s ", i);
}
#endif

// typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型

// 返回二叉树T中指向元素值为e的结点的指针
BiPTree Point(BiPTree T, TElemType e)
{
    LinkQueue q;
    QElemType a;
    if (T) // 非空树
    {
        InitQueue(&q);         // 初始化队列
        EnQueue(&q, T);        // 根结点入队
        while (!QueueEmpty(q)) // 队不空
        {
            DeQueue(&q, &a); // 出队，队列元素赋给a
            if (a->data == e)
                return a;
            if (a->lchild)              // 有左孩子
                EnQueue(&q, a->lchild); // 入队左孩子
            if (a->rchild)              // 有右孩子
                EnQueue(&q, a->rchild); // 入队右孩子
        }
    }
    return NULL;
}

// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：若e是T的非根结点，则返回它的双亲，否则返回＂空＂
TElemType Parent(BiPTree T, TElemType e)
{
    BiPTree a;
    if (T) // 非空树
    {
        a = Point(T, e);            // a是结点e的指针
        if (a && a != T)            // T中存在结点e且e是非根结点
            return a->parent->data; // 返回e的双亲的值
    }
    return Nil; // 其余情况返回空
}

// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的左孩子。若e无左孩子,则返回"空"
TElemType LeftChild(BiPTree T, TElemType e)
{
    BiPTree a;
    if (T) // 非空树
    {
        a = Point(T, e);            // a是结点e的指针
        if (a && a->lchild)         // T中存在结点e且e存在左孩子
            return a->lchild->data; // 返回e的左孩子的值
    }
    return Nil; // 其余情况返回空
}

// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的右孩子。若e无右孩子,则返回"空"
TElemType RightChild(BiPTree T, TElemType e)
{
    BiPTree a;
    if (T) // 非空树
    {
        a = Point(T, e);            // a是结点e的指针
        if (a && a->rchild)         // T中存在结点e且e存在右孩子
            return a->rchild->data; // 返回e的右孩子的值
    }
    return Nil; // 其余情况返回空
}

// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回＂空＂
TElemType LeftSibling(BiPTree T, TElemType e)
{
    BiPTree a;
    if (T) // 非空树
    {
        a = Point(T, e);                                                // a是结点e的指针
        if (a && a != T && a->parent->lchild && a->parent->lchild != a) // T中存在结点e且e存在左兄弟
            return a->parent->lchild->data;                             // 返回e的左兄弟的值
    }
    return Nil; // 其余情况返回空
}

// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回＂空＂
TElemType RightSibling(BiPTree T, TElemType e)
{
    BiPTree a;
    if (T) // 非空树
    {
        a = Point(T, e);                                                // a是结点e的指针
        if (a && a != T && a->parent->rchild && a->parent->rchild != a) // T中存在结点e且e存在右兄弟
            return a->parent->rchild->data;                             // 返回e的右兄弟的值
    }
    return Nil; // 其余情况返回空
}

// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空
// 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点
Status InsertChild(BiPTree p, int LR, BiPTree c) // 形参T无用
{
    //           的原有左或右子树则成为c的右子树
    if (p) // p不空
    {
        if (LR == 0)
        {
            c->rchild = p->lchild;
            if (c->rchild) // c有右孩子(p原有左孩子)
                c->rchild->parent = c;
            p->lchild = c;
            c->parent = p;
        }
        else // LR==1
        {
            c->rchild = p->rchild;
            if (c->rchild) // c有右孩子(p原有右孩子)
                c->rchild->parent = c;
            p->rchild = c;
            c->parent = p;
        }
        return OK;
    }
    return ERROR; // p空
}

// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1
// 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树
Status DeleteChild(BiPTree p, int LR) // 形参T无用
{
    if (p) // p不空
    {
        if (LR == 0) // 删除左子树
            ClearBiTree(&p->lchild);
        else // 删除右子树
            ClearBiTree(&p->rchild);
        return OK;
    }
    return ERROR; // p空
}

// 先序递归遍历二叉树T
void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{
    if (T)
    {
        Visit(T);                           // 先访问根结点
        PreOrderTraverse(T->lchild, Visit); // 再先序遍历左子树
        PreOrderTraverse(T->rchild, Visit); // 最后先序遍历右子树
    }
}

// 中序递归遍历二叉树T
void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{
    if (T)
    {
        InOrderTraverse(T->lchild, Visit); // 中序遍历左子树
        Visit(T);                          // 再访问根结点
        InOrderTraverse(T->rchild, Visit); // 最后中序遍历右子树
    }
}

// 后序递归遍历二叉树T
void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{
    if (T)
    {
        PostOrderTraverse(T->lchild, Visit); // 后序遍历左子树
        PostOrderTraverse(T->rchild, Visit); // 后序遍历右子树
        Visit(T);                            // 最后访问根结点
    }
}

// 层序遍历二叉树T(利用队列)
void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{
    LinkQueue q;
    QElemType a;
    if (T)
    {
        InitQueue(&q);
        EnQueue(&q, T);
        while (!QueueEmpty(q))
        {
            DeQueue(&q, &a);
            Visit(a);
            if (a->lchild != NULL)
                EnQueue(&q, a->lchild);
            if (a->rchild != NULL)
                EnQueue(&q, a->rchild);
        }
    }
}

/***************** end of file ******************/

tree.h

/*
 * Change Logs:
 * Date           Author       Notes
 * 2021-07-22     tyustli      first version
 */

#include <string.h>
#include <ctype.h>
#include <malloc.h> // malloc()等
#include <limits.h> // INT_MAX等
#include <stdio.h>  // EOF(=^Z或F6),NULL
#include <stdlib.h> // atoi()
#include <math.h>   // floor(),ceil(),abs()

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status;  // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

typedef int TElemType;

//二叉树的三叉链表存储表示
typedef struct BiTPNode
{
    TElemType data;
    struct BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
} BiTPNode, *BiPTree;

void InitBiTree(BiPTree *T);
void CreateBiTree(BiPTree *T);
void DestroyBiTree(BiPTree *T);
void ClearBiTree(BiPTree *T);
Status BiTreeEmpty(BiPTree T);
int BiTreeDepth(BiPTree T);
TElemType Root(BiPTree T);
TElemType Value(BiPTree p);
void Assign(BiPTree p, TElemType value);
BiPTree Point(BiPTree T, TElemType e);
TElemType Parent(BiPTree T, TElemType e);
TElemType LeftChild(BiPTree T, TElemType e);
TElemType RightChild(BiPTree T, TElemType e);
TElemType LeftSibling(BiPTree T, TElemType e);
TElemType RightSibling(BiPTree T, TElemType e);
Status InsertChild(BiPTree p, int LR, BiPTree c);
Status DeleteChild(BiPTree p, int LR);
void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree));

/***************** end of file ******************/

makefile

objects  = main.o tree.o
obj: $(objects)
	cc -o obj $(objects) -lm

main.o : tree.h
tree.o : tree.h

.PHONY : clean
clean :
	-rm obj $(objects)

在二叉链表的基础上增加了一个指向双亲的指针域。

data、lchild和rchild三个域的含义同二叉链表的结点结构；
parent域为指向该结点的双亲结点的指针。

结点数据类型声明：

template<class T>
struct Node
{
	T data;
	Node<T> * lchild, *rchild,*parent;
};

template <class T>
BiNode<T> * BiTree<T>::Creat(BiNode<T> * &root,BiNode<T> *parent)
{
    T ch;
    cout<<"请输入创建一棵二叉树的结点数据"<<endl;
    cin>>ch;
    if (ch=="#")
        root = NULL;
    else
    {
        root = new BiNode<T>;       //生成一个结点
        root->data=ch;
        root->parent=parent;
        Creat(root->lchild,root );    //递归建立左子树
        Creat(root->rchild,root);    //递归建立右子树
    }
    return root;
}

template<class T>
BiTree<T>::BiTree( int i)
{
    number=0;
    Creat(root,NULL);
}

森林转换为二叉树
⑴ 将森林中的每棵树转换成二叉树；
⑵ 从第二棵二叉树开始，
依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，
当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树或森林
⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；
⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；
⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

森林的遍历
⑴前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。
⑵后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。