定义：

树是n（n>=0）个结点的有限集。n=0时为空树，在任意一棵非空树中：

（1）仅有一个特定的根（root）的结点

（2）当n>1时，其余结点可分为m（m>0）个相互不相交的有限集T1....Tn，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）

结点的分类

度（Degree）结点拥有的子树数称为结点的度
度为0的结点称为叶结点（Leaf）或最终结点
度不为0的结点称为非终端结点或分支结点
除根结点之外，分支结点叶称为内部结点
数的度就是树内各结点度的最大值

结点间的关系

结点的子树的根称为该结点的孩子（Child）
该结点称为孩子的双亲（Parent）
同一个孩子之间称为兄弟（Sibling）
结点的祖先时从根到该结点所经所有结点
以某结点为根的子树中的任意一结点都称为该结点的子孙

树的其他概念

结点的层次：从根结点开始定义起，根为第一层，根的孩子为第二层
最大深度：树中结点的最大层次称为树的深度（Depth）或高度
有序数：数中结点各子树看成从左到右有次序的，不能互换，称为有序树，否则时无序数
森林（Forest）是m（m>=0）颗互不相交的树的集合

树的抽象数据类型

InitTree 构造空树
DestroyTree 销毁树
ClearTree 若树存在，清空树
TreeEmpty 若T为空树，返回true 否则返回false
TreeDepth 返回T的深度
Root 返回树的根结点
Value(T,cur_e) cur_e是树中的一个结点，返回此结点的值
Assign(T,cur_e,value) 给树的结点赋值为value
Parent（T,cur_e）若cur_e是树的非根结点，返回他的双亲，否则返回空

三种不同的表示方法

双亲表示法
孩子表示法
孩子兄弟表示法

双亲表示法

除了根结点外，其余每个结点不一定有孩子，但是一定有且仅有一个双亲

#include"iostream"
#include"stdlib.h"
#define MAX 10
using namespace std;
typedef int sjlx;
typedef struct PTNode{  //结点结构 
    sjlx data;
    int parent;
    int son[MAX];
    int sonxhao=0;
}ptnode; 

typedef struct tree{
    ptnode nodes[MAX];  //结点数组 
    int r=-1;
    int n;            //根的位置和结点数 
}Tree; 
void Initptnode(Tree &tree)
{
    int n=0;
    cin>>n;
    int Data,Par;
    for(int i=0;i<n;i++){
        cout<<"输入第"<<i<<"个结点的数据和双亲"<<endl; 
        cin>>Data;
        cin>>Par;
        tree.nodes[i].data=Data;
        tree.nodes[i].parent=Par;
        if(Par!=-1)
        {
            tree.nodes[Par].son[tree.nodes[Par].sonxhao]=Data;
            tree.nodes[Par].sonxhao++;
            cout<<"tree.nodes[Par].sonxhao="<<tree.nodes[Par].sonxhao<<endl;
        }

    }
}
void Find(Tree &tree){
    int i;
    cout<<"请输入要找的结点序号:";
    cin>>i;
    cout<<"为："<<tree.nodes[i].data<<endl;
    cout<<"儿子有：";
    int j=0;
    for(j=0;j<tree.nodes[i].sonxhao;j++){
        cout<<tree.nodes[i].son[j]<<"  ";
    } 
}
int main(){
    Tree tree;
    Initptnode(tree);
    while(1)
    Find(tree);
    return 0;
}

7
输入第0个结点的数据和双亲
10 -1
输入第1个结点的数据和双亲
20 0
tree.nodes[Par].sonxhao=1
输入第2个结点的数据和双亲
30 0
tree.nodes[Par].sonxhao=2
输入第3个结点的数据和双亲
40 1
tree.nodes[Par].sonxhao=1
输入第4个结点的数据和双亲
50 1
tree.nodes[Par].sonxhao=2
输入第5个结点的数据和双亲
60 2
tree.nodes[Par].sonxhao=1
输入第6个结点的数据和双亲
70 2
tree.nodes[Par].sonxhao=2
请输入要找的结点序号:1
为：20
儿子有：40  50  请输入要找的结点序号:0
为：10
儿子有：20  30  请输入要找的结点序号:

孩子表示法

多重链表表示法

typedef struct CTNode{  //孩子结点 
    int child;
    struct CTNode *next;
}*ChildePtr;
typedef struct{   //表头结构 
    TElemTyp data;
    ChildPtr firstchild;
}CTBox;
typedef struct    // 树结构 
{
    CTBox nodes[max];
    int r,n;
}CTree;

孩子兄弟表示法

任意一棵树他的结点的第一个孩子如果存在就是唯一的，他的右兄弟也是唯一的，设置俩个指针，指向第一个孩子和他的右兄弟

把一颗复杂的树变成了二叉树

二叉树

由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成

二叉树特点

每个结点最多有两颗子树
左子树和右子树是有顺序的
即使树中某结点只有一个子树，也要分左右

特殊二叉树

斜树所有结点都只有左子树叫做左斜树，反之线性表可以理解为树的一种特殊形式
满二叉树慢慢的
完全二叉树还没满的满二叉树编号为i的结点和满二叉树中编号为i的结点位置一样（按层序编号，没有空挡）

二叉树的性质

建立二叉树

在二叉树的第i层至多有2的(i-1)次方个结点（i>=1）
深度为k的二叉树至多有2的k-1次方个结点

#include"iostream"
#include"stdlib.h"
using namespace std;

typedef struct BitNode{
    char data;
    struct BitNode *lchild,*rchild;
}*BiTree;

void cjtree(BiTree *T){   //以前序式输入
    char ch;
    cin>>ch;
    if(ch=='#'){
        *T=NULL;
    }
    else{
        *T=(BiTree)malloc(sizeof(BitNode));
        (*T)->data=ch;
        cjtree(&(*T)->lchild);
        cjtree(&(*T)->rchild);
    }
}
void operation2(char ch,int level){
    cout<<ch<<"在第"<<level<<"层"<<endl; 
}
void PreorderTraverse(BiTree T,int level){   //前序
    if(T==NULL)
    return ;
    ;
    PreorderTraverse(T->lchild,level+1);
    PreorderTraverse(T->rchild,level+1);
} 
void InorderTraverse(BiTree T,int level){   //中序

    PreorderTraverse(T->lchild,level+1);
    operation2(T->data,level)
    PreorderTraverse(T->rchild,level+1);
}

int main(){
    BiTree T =NULL;
    cjtree(&T);
    int level=1;
    cout<<"前序遍历"<<endl;
    PreorderTraverse(T,level);
}

ABDG##H###CE#I##F##
前序遍历
A在第1层
B在第2层
D在第3层
G在第4层
H在第4层
C在第2层
E在第3层
I在第4层
F在第3层

输入的树

数据结构(树)插图

带#号表示

数据结构(树)插图1

二叉树的遍历方法 https://www.cnblogs.com/liuamin/p/6269950.html

前序遍历：若二叉树为空，则空操作返回，否则先左后右访问
中序遍历：左子树，根，右子树（使劲往左走，再往右走，根结点为界）
后序遍历：从左到右，先叶子后结点访问左右子树，最后根结点
层序遍历：根结点开始，在同一层从左到右访问

它的前序遍历顺序为：ABDGHCEIF

它的中序遍历顺序为：GDHBAEICF

它的后序遍历顺序为：GHDBIEFCA

线索二叉树（节省内存资源）（遍历或查找时需要某种遍历序列中的前驱和后继）

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树

等于把一个二叉树转换成一个双向链表

对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化

typesef enum {Link,Thread}pointerTag;
typedef struct BiThrNode{
    TelemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag Ltag;
    PointerTag Rtag 
}*BiThrTree; 
void InTherading(BiThTree p){
    if(p){
        InTherading(p->lchile);
        if(!p->lchild){
            p->LTag=Thread;
            p->lchild=pre;
        }
        if(!pre->rchild){
            pre->RTag=Thread;
            pre->rchild=p;
        }
        pre=p;
        InThreading(p->rchild); 
    }
}

树转换为二叉树

加线在所有兄弟结点间加线
去线对树中的每个结点只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
层次调整以树的根结点为核心，将树顺时针旋转一定角度，使结构分明

数据结构(树)

定义：