二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

二叉树遍历

所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础

• 深度优先遍历：先序遍历，中序遍历，后序遍历
• 广度优先遍历：层次遍历

先序遍历，中序遍历，后序遍历递归实现

#import<objc/objc.h>
#import <objc/runtime.h>
#import "ViewController.h"


@interface TreeNode: NSObject {
    @public
    int value;
    TreeNode *left;
    TreeNode *right;
}
@end

@implementation TreeNode
@end

@interface ViewController ()
@end
@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
}

//先序遍历
- (void)preOrderTraversal:(TreeNode *)node {
    if (!node) {
        return;
    }
    printf("%d",node->value);
    [self preOrderTraversal:node->left];
    [self preOrderTraversal:node->right];
}

//中序遍历
- (void)inOrderTraversal:(TreeNode *)node {
    if (!node) {
        return;
    }
    [self preOrderTraversal:node->left];
    printf("%d",node->value);
    [self preOrderTraversal:node->right];
}

//后序遍历
- (void)postOrderTraversal:(TreeNode *)node {
    if (!node) {
        return;
    }
    [self preOrderTraversal:node->left];
    [self preOrderTraversal:node->right];
    printf("%d",node->value);
}

先序遍历，中序遍历非递归实现

//先序遍历
void pre_traverse(BTree pTree) {
    PSTACK stack = create_stack();  //创建一个空栈
    BTree node_pop;                 //用来保存出栈节点
    BTree pCur = pTree;             //定义用来指向当前访问的节点的指针
    
    //直到当前节点pCur为NULL且栈空时，循环结束
    while(pCur || !is_empty(stack))
    {
        //从根节点开始，输出当前节点，并将其入栈，
        //同时置其左孩子为当前节点，直至其没有左孩子，及当前节点为NULL
        printf("%c ", pCur->data);
        push_stack(stack,pCur);
        pCur = pCur->pLchild;
        //如果当前节点pCur为NULL且栈不空，则将栈顶节点出栈，
        //同时置其右孩子为当前节点,循环判断，直至pCur不为空
        while(!pCur && !is_empty(stack))
        {
            pCur = getTop(stack);
            pop_stack(stack,&node_pop);
            pCur = pCur->pRchild;
        }
    }
}

//中序遍历
void in_traverse(BTree pTree)
{
    PSTACK stack = create_stack();  //创建一个空栈
    BTree node_pop;                 //用来保存出栈节点
    BTree pCur = pTree;             //定义指向当前访问的节点的指针
    
    //直到当前节点pCur为NULL且栈空时，循环结束
    while(pCur || !is_empty(stack))
    {
        if(pCur->pLchild)
        {
            //如果pCur的左孩子不为空，则将其入栈，并置其左孩子为当前节点
            push_stack(stack,pCur);
            pCur = pCur->pLchild;
        }
        else
        {
            //如果pCur的左孩子为空，则输出pCur节点，并将其右孩子设为当前节点，看其是否为空
            printf("%c ", pCur->data);
            pCur = pCur->pRchild;
            //如果为空，且栈不空，则将栈顶节点出栈，并输出该节点，
            //同时将它的右孩子设为当前节点，继续判断，直到当前节点不为空
            while(!pCur && !is_empty(stack))
            {
                pCur = getTop(stack);
                printf("%c ",pCur->data);
                pop_stack(stack,&node_pop);
                pCur = pCur->pRchild;
            }
        }
    }
}

层次遍历

思路

代码

void BinaryTreeLevelOrder(TreeNode* root) {
    Queue q;
    //树为空，直接返回
    if (root == NULL) {
        return;
    }
    QueueInit(&q); //先将根节点入队
    QueuePush(&q, root);
    while (QueueEmpty(&q)) {
        //出队保存队头并访问
        BTNode* front = QueueFront(&q);
        printf("%c", front->_data);
        QueuePop(&q); //将出队结点的左子树根入队
        if (front->_left)
            QueuePush(&q, front->_left);
        //将出队结点的右子树根入队
        if (front->_right)
            QueuePush(&q, front->_right);
        
    }
}

最长路径

public class Node {
    public var left: Node?
    public var right: Node?
    public init(_ val: Int) {
        self.left = nil
        self.right = nil
    }
}
//最长路径
func maxLength(node:Node?) -> Int {
    if node == nil {
        return 0
    }
    return max(maxLength(node: node?.left), maxLength(node: node?.right)) + 1
}