数据结构--树

树的存储结构一(分为顺序存储和链式存储[二叉链表])
树的存储结构二

树的定义.png 树的结点以及树的度.png 树结点间的关系.png 树的深度.png 线性结构与树性结构对比.png

二叉树

二叉树：是n（n≥0）个结点的有限集合，该几个或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
对于折半查找，对于这种在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错、正与反等，都适合用树状结构来建模，而这种书是一种特殊的树状结构，叫做二叉树。

二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在大于2的结点。

• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树种某结点只有一颗子树，也要区分它是左子树还是右子树。

二叉树的五种基本形态

1、 空二叉树。
2、只有一个根结点。
3、根结点只有左子树。
4、根结点只有右子树。
5、根结点既有左子树又有右子树。

特殊二叉树（斜树、满二叉树、完全二叉树）

1、斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫做右斜树。两者统称为斜树。

斜树特点：就是每个层都只有一个结点，结点的个数与二叉树的深度相同。
线性表结构可以理解为是树的一种极其特殊的表现形式，斜树。

2、满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。
满二叉树的特点：
1、叶子只能出现在最下层，出现在其他层就不能达到平衡。
2、非叶子结点的度一定是2。
3、在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

3、完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号为i（1≤i<≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，而这颗二叉树称为完全二叉树。

完全二叉树的特点：
1、叶子结点只能出现在最下两层。
2、最下层的叶子一定集中在左部连续位置。
3、倒数二层，若有叶子结点，一定都在右部连续位置。
4、如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
5、同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质
二叉树的存储结构（顺序存储结构和链式存储结构）

二叉树的遍历（前序遍历、中序遍历、后序遍历、层序遍历）二叉树创建、遍历算法代码实现一
二叉树创建、遍历算法代码实现二
OC二叉树

//OC创建二叉树
@interface BinaryTreeNode : NSObject { 
    id data; 
    BinaryTreeNode *left; 
    BinaryTreeNode *right;
}
+ (BinaryTreeNode*)addTree:(BinaryTreeNode *)p andValue:(id)value{ 
  if (nil == p) { 
    p = [[BinaryTreeNode alloc] init]; 
    p -> data = value; 
    p -> left = p -> right = nil; 
  } else if (![value intValue] < [p ->data intValue]) { 
    p -> left = [BinaryTreeNode addTree:p -> left andValue:value]; 
  } else { 
    p -> right = [BinaryTreeNode addTree:p -> right andValue:value]; 
  } 
  return p;
}



//前序遍历
- (void)inOrderBinaryTree:(BinaryTreeNode *)p { 
    if (p != nil) { 
        NSLog("%d/n", [p -> data intValue]);
        [self inOrderBinaryTree:p -> left]; 
        [self inOrderBinaryTree:p -> right]; 
    }
}

//中序遍历
- (void)inOrderBinaryTree:(BinaryTreeNode *)p { 
    if (p != nil) { 
        [self inOrderBinaryTree:p -> left]; 
        NSLog("%d/n", [p -> data intValue]);
        [self inOrderBinaryTree:p -> right]; 
    }
}

//后序遍历
- (void)inOrderBinaryTree:(BinaryTreeNode *)p { 
    if (p != nil) { 
        [self inOrderBinaryTree:p -> left]; 
        [self inOrderBinaryTree:p -> right]; 
        NSLog("%d/n", [p -> data intValue]);
    }
}

非递归遍历二叉树，运用栈保存每一个非叶结点信息。

//非递归遍历二叉树，前序遍历
void preorderTraversalNew(TreeNode *root, vector<int> &path)
{ 
    stack<TreeNode *> s; 
    s.push(root); 
    while(!s.empty()) { 
        root = s.top(); 
        s.pop(); 
        if(root ！= NULL) { 
            path.push_back(root->val); //等同于println
            s.push(root->right); 
            s.push(root->left);
        }
    }
}

二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问依次且仅被访问依次。
其中包括两个关键词：访问和次序
1、前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。（根左右）
遍历结果为：ABDGHCEIF

前序遍历.png
2、中序遍历：若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。（左根右）
遍历顺序为：GDHBAEICF
中序遍历.png
3、后序遍历：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。（左右根）
遍历顺序为：GHDBIEFCA
后序遍历.png
4、层序遍历：若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
遍历顺序为：ABCDEFGHI
层序遍历.png

二叉树里面一个重要的概念：线索二叉树

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

二叉树的线索化 线索二叉树其实就是一个双向链表

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

二叉树线索化--后继.png 二叉树线索化--前驱.png 二叉树线索化--双向链表.png
如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？
线索二叉树lchild和rchild指向实现.png
线索二叉树结构实现
线索二叉树的遍历

线索化的实质就是将儿茶链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的工程。

/* 二叉树的二叉线索存储结构定义 */
//Link==0 表示指向左右孩子指针
//Thread==1表示指向前驱或后继的线索
typedef enum {link, thread} PointerTag; 
typedef struct BiThrNode 
{ 
    char data;     //结点数据
    struct BiThrNode *lchild,*rchild;   //左右孩子指针
    PointerTag lTag;   //左右标志
    PointerTag rTag; 
}  BiThrNode, *BiThrTree ;

中序遍历线索化.png
线索二叉树的遍历.jpg

二叉树和链表 -> 题
树、森林与二叉树的转换
重点：赫夫曼树与赫夫曼编码