『树』(Tree)，是n()个节点的有限集。当n=0时，成为「空树」。在任意一棵非空树中应满足：

• 有且只有一个特定的称为「根」的节点；
• 当 n>1 时，其余节点可分为 m(m>0) 个互不相交的有限集 T1,T2,...,Tm, 其中每个集合本身又是一棵树，并且称为根的「子树】。

笔记

树的特点：

• 树的根结点没有前驱，除根结点外的所有节点有且只有一个前驱；
• 书中所有节点可以有零个或多个后继。

树的层数称为树的「高度」。从1开始。
「『二叉树』是另一种树形结构。每个结点是每个结点至多只有2棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其顺序不能任意颠倒。

二叉树的类型

满二叉树

每一层节点数都满足 。 即每一层每个结点都有左右子树，或每一层每个结点都为空子树。

完全二叉树

倒数第二层以上为完全二叉树，最后一层的结点依次从左往右放。

满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

二叉树的存储

顺序存储

层次遍历。

链式存储

二叉树遍历

非递归执行效率更高，因为递归函数弹栈压栈消耗系统性能！一般多采用递归执行遍历。

前序遍历

又叫「先序遍历」。属于「深度优先遍历」。

中序遍历

后序遍历

层次遍历

又叫「层序遍历」，属于「广度优先遍历」，需要借助队列来实现。

实例

点击查看

使用C++ 实现。

#include <stdio.h>
#include <stdlib.h>

#define TreeType char
// 二叉树结点 结构体
typedef struct BitTreeNode{
    TreeType data;
    struct BitTreeNode *rChild,*lChild; // 左右孩子指针
}BitTreeNode,*pBitTreeNode;
//
typedef struct tagQueue{
    pBitTreeNode p; // 用于存放树某个结点的地址
    struct tagQueue *next;// 下一个指针
}tagQueue,*pTagQueue;

void preOrder(pBitTreeNode b){
    // 前序遍历  根左右    子树紧跟树根放
    if (b != NULL){
        putchar(b->data); // 打印数据
        preOrder(b->lChild); // 递归打印左子树
        preOrder(b->rChild); // 递归打印右子树
    }
}
void inOrder(pBitTreeNode b){
    // 中序遍历  左根右
    if (b != NULL){
        inOrder(b->lChild); // 递归打印左子树
        putchar(b->data); // 打印数据
        inOrder(b->rChild); // 递归打印右子树
    }
}
//void inOrderStack(pBitTreeNode b){
//    // 非递归中序遍历，需要借助 stack 来实现
//    SqStack s;
//    InitSqStack(s);
//    pBitTreeNode temp = b;
//    while (temp || !StackIsEmpty(s)){
//        if (temp){
//            Push(s,temp); // 将当前结点指针入栈
//            temp = temp->lChild; // 指针左移
//        }else{
//            Pop(s,temp); // 当前结点为空时，出栈
//            putchar(temp->data); // 打印当前结点数据
//            temp = temp->rChild; // 指针右移
//        }
//    }
//}

void postOrder(pBitTreeNode b){
    // 后序遍历  左右根
    if (b != NULL){
        postOrder(b->lChild); // 递归打印左子树
        postOrder(b->rChild); // 递归打印右子树
        putchar(b->data); // 打印数据
    }
}
void levelOrder(pBitTreeNode b){
    // 后序遍历  左右根
    if (b != NULL){
        postOrder(b->lChild); // 递归打印左子树
        postOrder(b->rChild); // 递归打印右子树
        putchar(b->data); // 打印数据
    }
}
int main() {
    pBitTreeNode Tree=NULL; // 树根
    pBitTreeNode tempTree;// 临时结点指针
    int i,j,pos;
    char c;
    pTagQueue pHead = NULL,pTail = NULL,tempTag,pCur; // 队列头指针、尾指针、队列临时指针、队列现在的指针
    while (scanf("%c",&c) !=EOF){
        if (c=='\n'){
            break;
        }
        tempTree = (pBitTreeNode)calloc(1,sizeof(BitTreeNode)); // 临时树节点，使用calloc申请空间并对空间进行初始化，赋值为0
        tempTree->data = c; // 存储数据
        tempTag = (pTagQueue)calloc(1, sizeof(tagQueue)); // 临时队列结点
        tempTag->p = tempTree; // 存放二叉树结点地址
        if (Tree == NULL){ // 空树
            Tree = tempTree; //树根
            pHead = tempTag;
            pTail = tempTag;
            pCur = tempTag;
            continue; // 跳出本次循环
        }else{ // 非空树
            pTail->next = tempTag; // 新结点通过尾插法插入链表，
            pTail = tempTag; // 指向对尾
        }

        if (pCur->p->lChild == NULL ){ // 判断队列当前结点的左孩子树是否为空
            pCur->p->lChild = tempTree; // 给左孩子树 赋值
        } else{
            pCur->p->rChild = tempTree; // 给右孩子树赋值
            pCur = pCur->next; // 右孩子树赋值后，当前结点后移
        }
    }

    preOrder(Tree);
    return 0;
}

线索二叉树

二叉排序树

又称「二叉查找树」，具有以下特点：

• 若左子树非空，则左子树上所有结点的值小于根结点的值；
• 若右子树非空，则右子树上所有结点的值小于根结点的值；
• 左右子树也分别是一棵二叉排序树。

简单来说，小值往左放，大值往右放。
中序遍历时，值从小到大排列。

二叉排序树遍历

二叉排序树删除

删除策略为：左子树左大数据或右子树最小数据，即，左子树的最后一个右结点或右子树的最后一个左结点。