二叉树的遍历

先序遍历:根左右
中序遍历:左根右
后序遍历:左右根

二叉树遍历的实现

先序:可以用递归的思想

void preorder(binaryTree tree) {
    if(tree != NULL) {
        visit(tree);
        preorder(tree->left);
        preorder(tree->right);
    }
}

中序:一样用递归的思想

void inorder(binaryTree tree) {
    if(tree != NULL) {
        inorder(tree->left);
        visit(tree);
        inorder(tree->right);
    }
}

后序:一样用递归的思想

void postorder(binaryTree tree) {
    if(tree != NULL) {
        postorder(tree->left);
        postorder(tree->right);
        visit(tree);
    }
}

通过遍历的顺序构造一棵二叉树

必须要由 “中序遍历+先序遍历” 或 “中序遍历+后序遍历” 或 “中序遍历+层次遍历” 才行。
因为必须要用中序遍历区分出哪个是左节点和右节点。

线索二叉树

就是给二叉树加上指针域,分别指向左子树和右子树。
如果没有左子树,就把左指针指向前驱节点;
如果没有右指针,就把右指针指向后继节点。

这样的话就会有个问题,就是你不知道它的这个指针指向的到底是它的子树还是前后置节点。
为了解决这个问题所以就再引入一个tag来标记它到底是是不是子树。

所以,线索二叉树一个node的结构就是

typedef struct threadedBinaryNode {
    elemType value;
    struct threadedBinaryNode* left; * right;
    //    这俩玩意儿就叫做线索  ~~~~~~~~~~~~~~
    int leftTag; rightTag;
}

这一整个东西就叫做线索链表
由这些东西组成的数叫做线索二叉树。

标签: none