二叉树

2018-01-02 本文已影响5人 jameiShi

阅读目录

树的定义

树的表示方法

常见的术语

二叉树的常见性质

二叉树的类型

二叉树的常见操作

1.树的定义

有且仅有一个特定的称为根Root的结点.
当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一个棵树，并称为根的子树.

2.树的表示方法

最常见的是树形表示法和广义表表示法，下面是树形表示法，如图所示。

二叉树树形表示.jpg

上图的广义表表示法为：(A(B(D，E)，C(F，G)))

3.常见的术语

父节点，孩子节点，兄弟节点。以上图为例，A是B和C的父节点，B和C是A的孩子节点，B和C之间就是兄弟节点了。
结点的度和树的度。结点的度即结点有几个分支，比如节点A有两个分支B和C，那么结点A的度就是2，树的度即为一棵树中结点的最大度数，所以树的度也是2。
有序树和无序树。如果将树中结点的子树看成是从左至右依次有序且不能交换，则称该树为有序树，否则称为无序树。
森林。在上图中，如果将根节点A拿掉，那么B和C子树合并就是森林了。
二叉树。二叉树是一种特殊的树。它的每个结点至多只有两棵子树。

4.二叉树的常见性质

性质1: 在二叉树的第i层上至多有2i-1个结点(i>=1)
性质2:深度为k的二叉树至多有2k-1个结点(k>=1)
性质3: 满二叉树，在一棵深度为k且有2k-1个结点。完全二叉树，若一棵深度为k的二叉树，其前k-1层是一个棵满二叉树，而最下面一层(即第k层)上的结点都集中在该层最左边的若干位置上。

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

5.二叉树的两种存储结构

顺序存储:
对于完全二叉树而言，可以使用顺序存储结构。但是对于一般的二叉树来说，使用存储结构会有两个缺点，一，如果不是完全二叉树，则必须将其转化为完全二叉树，二是增加了很多虚节点，浪费资源空间。

完全二叉树的顺序存储结构表示.jpg
链式存储
这是最常用的一种二叉树存储结构。每个结点设置三个域，即值域，左指针域和右指针域，用data表示值域，lchild和rchild分别表示指向左右子树的指针域。如图所示。

二叉树的链式存储结构.jpg

6.二叉树的类型

普通二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉搜索树（排序树）、平衡二叉树、AVL平衡二叉树、红黑树、B树、B+树、堆等

完全二叉树:若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点,并且叶子结点都是从左到右依次排布
满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
线索二叉树:在有n个结点的二叉链表中必定存在n+1个空指针域，因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树被称为线索二叉树。
二叉搜索树(排序树,查找树):它或者是一棵空树，或者是具有下列性质的二叉树, 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树
哈夫曼树:给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树

7.二叉树的常见操作

插入节点
思路：首先找到要插入节点的父节点，然后确定插到父节点的左边还是右边，最后将节点插入。
查找节点
思路：运用递归查找。
计算树的深度
思路：分别递归左子树和右子树，取长度较大的那一个作为整个树的深度。
遍历之先序遍历
思路：先访问根，然后遍历左子树，再遍历右子树
遍历之中序遍历
思路：先遍历左子树，再访问根，最后遍历右子树
遍历之后序遍历
思路：先遍历左子树，再遍历右子树，最后访问根
遍历之层次遍历
思路：从上到小，从左到右遍历
代码:
BinaryTreeNode.h:

@interface BinaryTreeNode : NSObject
@property (nonatomic,assign)NSUInteger value;
@property (nonatomic,strong)BinaryTreeNode *leftNode;
@property (nonatomic,strong)BinaryTreeNode *rightNode;
//向二叉排序树节点添加一个节点
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value;
//二叉树的深度
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode;
// 先序遍历: 先访问根，再遍历左子树，再遍历右子树
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler;
//中序遍历:先遍历左子树，再访问根，再遍历右子树
+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler;
//后序遍历:先遍历左子树，再遍历右子树，再访问根
+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler;
//层次遍历（广度优先)
+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler;
@end

BinaryTreeNode.m:

#import "BinaryTreeNode.h"
@implementation BinaryTreeNode
/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param node 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+(BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)node value:(NSInteger)value
{
    if (!node) {
        node = [BinaryTreeNode new];
        node.value = value;
    }
    else if (value<node.value)
    {
        node.leftNode = [BinaryTreeNode addTreeNode:node.leftNode value:value];
    }
    else
    {
        node.rightNode = [BinaryTreeNode addTreeNode:node.rightNode value:value];
    }
    return node;
}
/**
 *  二叉树的深度
 *
 *  @param rootNode 二叉树根节点
 *
 *  @return 二叉树的深度
 */
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode {
    if (!rootNode) {
        return 0;
    }
    if (!rootNode.leftNode&&!rootNode.rightNode) {
        return 1;
    }
    
    NSInteger leftDepth = [BinaryTreeNode depthOfTree:rootNode.leftNode];
    NSInteger rightDepth = [BinaryTreeNode depthOfTree:rootNode.rightNode];
    return MAX(leftDepth, rightDepth)+1;    
}
/**
 *  先序遍历：先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        
        if (handler) {
            handler(rootNode);
        }
        
        [self preOrderTraverseTree:rootNode.leftNode handler:handler];
        [self preOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}

+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler
{
    if (rootNode) {
        
    
        [self inOrderTraverseTree:rootNode.leftNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
        [self inOrderTraverseTree:rootNode.rightNode handler:handler];
    }
}

+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler
{
    if (rootNode) {
        [self postOrderTraverseTree:rootNode.leftNode handler:handler];
        [self postOrderTraverseTree:rootNode.rightNode handler:handler];
        if (handler) {
            handler(rootNode);
        }
    }
}

/**
 *  层次遍历（广度优先）
 *
 *  @param rootNode 二叉树根节点
 *  @param handler  访问节点处理函数
 */
+ (void)levelTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler
{
    if (!rootNode) {
        return;
    }
    
    NSMutableArray *queryArray = [NSMutableArray array];
    [queryArray addObject:rootNode];
    while (queryArray.count>0) {
        BinaryTreeNode *node = queryArray.firstObject;
        if (handler) {
            handler(node);
        }
        [queryArray removeObjectAtIndex:0];
        if (node.leftNode) {
            [queryArray addObject:node.leftNode];
        }
        if (node.rightNode) {
            [queryArray addObject:node.rightNode];
        }
    }
}
@end

二叉树