06_线索二叉树

6.1 介绍

现有一个结点数目为n的二叉树，采用二叉链表的形式存储，对于每个结点均有指向左右孩子的两个指针域。

结点为n的二叉树一共有 n + 1 个空指针域。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

线索二叉树：先对二叉树中序化，中序线索化，建立虚线以后，再进行前驱后继的处理，就直接按照线索化的路径进行遍历。

中序遍历：1. 一直往左走，直到找到左线索点。2. 当前这个点是否有右线索，一直往右。3. 当发现某个点的右边不是线索化点，把这个右边的点当作新结点，重复1. 。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

6.2 申明

由于左右指针域，既可能表示节点，也可能线索化，因此添加标记Tag，来辅助表示。

c 实现：

typedef char Element_t;
//定义线索二叉树节点结构
typedef struct treenode {
	Element_t data;
	struct treenode* left;
	struct treenode* right;
	int leftTag;	//0表示left指向节点，1表示线索化（前驱）
	int rightTag;	//0表示right指向节点，1表示线索化（后继）
}TreeNode_t;

//定义线索二叉树结构
typedef struct {
	TreeNode_t* root;
	int count;
}ThreadedBinaryTree_t;

Java 实现：

Element:

package com.Sonnet.Threaded;

public class Element {
    private char data;

    public Element() {}
    public Element(char data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return String.valueOf(data);
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(data);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (this.getClass() != obj.getClass()) return false;
        Element other = (Element)obj;
        return this.data == other.data;
    }
}

TreeNode:

package com.Sonnet.Threaded;

public class TreeNode {
    Element data;
    TreeNode left;
    TreeNode right;
    //false 表示left指向节点，true 表示线索化（前驱）
    boolean leftTag;
    //false 表示right指向节点，true 表示线索化（后继）
    boolean rightTag;

    public TreeNode() {}
    public TreeNode(Element data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.leftTag = false;
        this.rightTag = false;
    }
}

ThreadedBinaryTree:

package com.Sonnet.Threaded;

public class ThreadedBinaryTree {
    TreeNode root;
    int count;
}

6.3 创建

c 实现： 

/*创建节点*/
TreeNode_t* createTreeNode(Element_t data) {
	TreeNode_t* node = malloc(sizeof(TreeNode_t));
	if (node == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	node->leftTag = 0;
	node->rightTag = 0;

	return node;
}

/*创建线索二叉树*/
ThreadedBinaryTree_t* createThreadedBinaryTree(TreeNode_t* root) {
	if (root == NULL) return NULL;
	ThreadedBinaryTree_t* tree = malloc(sizeof(ThreadedBinaryTree_t));
	if (tree == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	tree->count = 1;
	tree->root = root;

	return tree;
}

Java 实现：

public ThreadedBinaryTree() {}
public ThreadedBinaryTree(TreeNode root) {
    private this.root = root;
    private this.count = 1;
}

6.4 插入

c 实现： 

/*插入*/
void insertTreeNode(ThreadedBinaryTree_t* tree, TreeNode_t* parent, TreeNode_t* left, TreeNode_t* right) {
	if (tree == NULL || parent == NULL) return;
	if (left) {
		parent->left = left;
		tree->count++;
	}
	if (right) {
		parent->right = right;
		tree->count++;
	}

	return;
}

Java 实现：

/*
	功能： 插入
	参数： 父亲节点 左孩子 右孩子
	返回值： 无
*/
public void insertTreeNode(TreeNode parent, TreeNode left, TreeNode right) {
    if (parent == null) return;
    if (left != null) {
        parent.left = left;
        this.count++;
    }
    if (right != null) {
        parent.right = right;
        this.count++;
    }
}

6.5 访问

c 实现：

/*访问*/
void visitTreeNode(TreeNode_t* node) {
	if (node == NULL) return;
	printf("%c\t", node->data);
}

Java 实现：

/*
	功能： 访问节点
	参数： 节点
	返回值： 无
*/
public void visitTreeNode(TreeNode node) {
    if (node == null) return;
    System.out.print(node.data + "\t");
}

6.6 线索化

c 实现：

/*线索化节点*/
static TreeNode_t* pre = NULL;
void inOrderTreeNode(TreeNode_t* node) {
	//递归退出条件
	if (node == NULL) return;
	//访问左孩子
	inOrderTreeNode(node->left);
	//线索化
	if (node->left == NULL) {
		node->left = pre;
		node->leftTag = 1;
	}
	if (pre && pre->right == NULL) {
		pre->right = node;
		pre->rightTag = 1;
	}
	pre = node;
	//访问右孩子
	inOrderTreeNode(node->right);
}

/*线索化*/
void inOrderThreadingBinaryTree(ThreadedBinaryTree_t* tree) {
	inOrderTreeNode(tree->root);
}

Java 实现：

    private TreeNode pre = null;
    private void inOrderTreeNode(TreeNode node) {
        //递归退出条件
        if (node == null) return;
        inOrderTreeNode(node.left);
        if (node.left == null) {
            node.left = pre;
            node.leftTag = true;
        }
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightTag = true;
        }
        pre = node;
        inOrderTreeNode(node.right);
    }

    /*
        功能： 线索化二叉树
        参数： 无
        返回值： 无
     */
    public void inOrderThreadingBinaryTree() {
        inOrderTreeNode(this.root);
    }

6.7 中序遍历线索二叉树

  1. 一直往左走，直到找到做线索点
  2. 如果有右线索，一直往右，直到无右线索
  3. 无右线索时，以右节点为新节点，重复1

c 实现：

/*中序遍历线索二叉树*/
void inOrderThreadedBinaryTree(ThreadedBinaryTree_t* tree) {
	TreeNode_t* node = tree->root;
	while (node) {
		//一路向左
		while (node->leftTag == 0) {
			node = node->left;
		}
		//访问头节点
		visitTreeNode(node);
		//一路向右
		while (node->rightTag == 1 && node->right) {
			node = node->right;
			visitTreeNode(node);
		}
		node = node->right;
	}
	printf("\n");
}

Java 实现：

    /*
        功能： 中序遍历线索二叉树
        参数:  无
        返回值： 无
     */
    public void inOrderThreadedBinaryTree() {
        TreeNode node = this.root;
        while (node != null) {
            //一直往左, 直到左线索点
            while (!node.leftTag) {
                node = node.left;
            }
            //访问头节点
            visitTreeNode(node);
            //一路向右
            while (node.rightTag && node.right != null) {
                node = node.right;
                visitTreeNode(node);
            }
            //重置头节点
            node = node.right;
        }
        System.out.println();
    }

6.8 释放

c 实现：

static void freeTreeNode(ThreadedBinaryTree_t* tree, TreeNode_t* node) {
	if (node == NULL) return;
	if (node->leftTag == 0) {
		freeTreeNode(tree, node->left);
	}
	if (node->rightTag == 0) {
		freeTreeNode(tree, node->right);
	}
	free(node);
	tree->count--;
}

/*释放*/
void releaseThreadedBinaryTree(ThreadedBinaryTree_t* tree) {
	freeTreeNode(tree, tree->root);
	printf("tree have %d node\n", tree->count);
	free(tree);
}

Java 实现：

    private void freeTreeNode(TreeNode node) {
        if (node == null) return;
        if (!node.leftTag) {
            freeTreeNode(node.left);
        }
        if (!node.rightTag) {
            freeTreeNode(node.right);
        }
        node.left = null;
        node.right = null;
        this.count--;
    }

    /*
        功能： 释放线索二叉树
        参数: 无
        返回值： 无
     */
    public void releaseThreadedBinaryTree() {
        freeTreeNode(this.root);
        System.out.println("tree have " + this.count + " node");
        this.root = null;
    }

6.9 完整实现

c 实现：

ThreadedBTree.h:

#pragma once

typedef char Element_t;
//定义线索二叉树节点结构
typedef struct treenode {
	Element_t data;
	struct treenode* left;
	struct treenode* right;
	int lTag;	//0表示left是指向节点，1表示线索化（前驱）
	int rTag;	//0表示right是指向节点，1表示线索化（后继）
}TreeNode_t;

//定义二叉线索树结构
typedef struct {
	int number;
	TreeNode_t* root;
}ThreadedBTree_t;

/*
	功能： 创建二叉线索树
	参数： 根节点
	返回值： 线索二叉树
*/
ThreadedBTree_t* createThreadedBinaryTree(TreeNode_t* root);

/*
	功能： 创建节点
	参数： 节点数据
	返回值： 节点
*/
TreeNode_t* createTreeNode(Element_t element);

/*
	功能： 释放二叉线索树
	参数： 二叉线索树
	返回值： 无
*/
void releaseThreadedBinaryTree(ThreadedBTree_t* tree);

/*
	功能： 插入节点
	参数： 二叉树， 父亲节点，左孩子，右孩子
	返回值：无
*/
void insertTreeNode(ThreadedBTree_t* tree, TreeNode_t* parent, TreeNode_t* left, TreeNode_t* right);

/*
	功能： 访问节点数据
	参数： 节点
	返回值： 无
*/
void visitTreeNode(TreeNode_t* node);

/*
	功能： 中序线索化
	参数：二叉树
	返回值： 无
*/
void inOrderThreadingBinaryTree(ThreadedBTree_t* tree);

/*
	功能： 线索化后，开始二叉树的中序遍历
	参数： 线索二叉树
	返回值： 无
*/
void inOrderTraversal(ThreadedBTree_t* tree);

ThreadedBTree.c:

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

/*创建二叉树*/
ThreadedBTree_t* createThreadedBinaryTree(TreeNode_t* root) {
	if (root == NULL) return NULL;
	ThreadedBTree_t* tree = malloc(sizeof(ThreadedBTree_t));
	if (tree == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	tree->number = 1;
	tree->root = root;

	return tree;
}

/*创建节点*/
TreeNode_t* createTreeNode(Element_t e) {
	TreeNode_t* node = malloc(sizeof(TreeNode_t));
	if (node == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	//初始化
	node->data = e;
	node->left = NULL;
	node->right = NULL;
	node->lTag = 0;
	node->rTag = 0;

	return node;
}

/*插入*/
void insertTreeNode(ThreadedBTree_t* tree, TreeNode_t* parent, TreeNode_t* left, TreeNode_t* right) {
	if (!tree || !parent) return;
	if (left) {
		parent->left = left;
		tree->number++;
	}
	if (right) {
		parent->right = right;
		tree->number++;
	}

	return;
}

/*访问*/
void visitTreeNode(TreeNode_t* node) {
	if (node == NULL) return;
	printf("%c\t", node->data);
}

/*线索化节点*/
static TreeNode_t* pre = NULL;
static void inOrderTreeNode(TreeNode_t* node) {
	//递归退出条件
	if (node == NULL) return;
	//访问左孩子
	inOrderTreeNode(node->left);
	//线索化
	if (node->left == NULL) {
		node->lTag = 1;
		node->left = pre;
	}
	if (pre && pre->right == NULL) {
		pre->right = node;
		pre->rTag = 1;
	}
	pre = node;
	//访问右孩子
	inOrderTreeNode(node->right);
}

/*线索化二叉树*/
void inOrderThreadingBinaryTree(ThreadedBTree_t* tree) {
	inOrderTreeNode(tree->root);

	return;
}

/*中序遍历线索二叉树
	1. 一直往左走，直到找到左线索点
	2. 如果有右线索，一直往右，直到无右线索
	3. 无右线索时，以右节点为新节点，重复1
*/ 
void inOrderTraversal(ThreadedBTree_t* tree) {
	TreeNode_t* node = tree->root;
	while (node) {
		//一直往左走，找到可以作为线索的节点
		while (node->lTag != 1) {
			node = node->left;
		}
		//访问头节点
		visitTreeNode(node);
		//一路向右，
		while (node->rTag == 1 && node->right) {
			node = node->right;
			visitTreeNode(node);
		}
		//重置node位置，再次循环
		node = node->right;
	}
	printf("\n");

	return;
}

/*释放节点*/
static void freeTreeNode(ThreadedBTree_t* tree, TreeNode_t* node) {
	if (node == NULL) return;
	if (node->lTag == 0) {
		freeTreeNode(tree, node->left);
	}
	if (node->rTag == 0) {
		freeTreeNode(tree, node->right);
	}
	free(node);
	tree->number--;

	return;
}

/*释放*/
void releaseThreadedBinaryTree(ThreadedBTree_t* tree) {
	freeTreeNode(tree, tree->root);
	printf("tree have %d node", tree->number);
	free(tree);
}

main.c:

#include <stdio.h>
#include "ThreadedBTree.h"

ThreadedBTree_t* init() {
	TreeNode_t* nodeA = createTreeNode('A');
	TreeNode_t* nodeB = createTreeNode('B');
	TreeNode_t* nodeC = createTreeNode('C');
	TreeNode_t* nodeD = createTreeNode('D');
	TreeNode_t* nodeE = createTreeNode('E');
	TreeNode_t* nodeF = createTreeNode('F');
	TreeNode_t* nodeG = createTreeNode('G');
	TreeNode_t* nodeH = createTreeNode('H');
	TreeNode_t* nodeK = createTreeNode('K');

	ThreadedBTree_t* tree = createThreadedBinaryTree(nodeA);
	insertTreeNode(tree, nodeA, nodeB, nodeE);
	insertTreeNode(tree, nodeB, NULL, nodeC);
	insertTreeNode(tree, nodeC, NULL, NULL);
	insertTreeNode(tree, nodeC, nodeD, NULL);
	insertTreeNode(tree, nodeD, NULL, NULL);
	insertTreeNode(tree, nodeE, NULL, nodeF);
	insertTreeNode(tree, nodeF, nodeG, NULL);
	insertTreeNode(tree, nodeG, nodeH, nodeK);

	return tree;
}

int main() {
	ThreadedBTree_t* tree;
	tree = init();
	printf("tree have %d node\n", tree->number);
	inOrderThreadingBinaryTree(tree);
	inOrderTraversal(tree);
	releaseThreadedBinaryTree(tree);

	return 0;
}

Java 实现：

Element:

package com.Sonnet.Threaded;

public class Element {
    private char data;

    public Element() {}
    public Element(char data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return String.valueOf(data);
    }

    @Override
    public int hashCode() {
        return Integer.hashCode(data);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (this.getClass() != obj.getClass()) return false;
        Element other = (Element)obj;
        return this.data == other.data;
    }
}

TreeNode:

package com.Sonnet.Threaded;

public class TreeNode {
    Element data;
    TreeNode left;
    TreeNode right;
    //false 表示left指向节点，true 表示线索化（前驱）
    boolean leftTag;
    //false 表示right指向节点，true 表示线索化（后继）
    boolean rightTag;

    public TreeNode() {}
    public TreeNode(Element data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.leftTag = false;
        this.rightTag = false;
    }
}

ThreadedBinaryTree:

package com.Sonnet.Threaded;

public class ThreadedBinaryTree {
    private TreeNode root;
    private int count;

    public ThreadedBinaryTree() {}
    public ThreadedBinaryTree(TreeNode root) {
        this.root = root;
        this.count = 1;
    }

    /*
        功能： 插入
        参数： 父亲节点 左孩子 右孩子
        返回值： 无
     */
    public void insertTreeNode(TreeNode parent, TreeNode left, TreeNode right) {
        if (parent == null) return;
        if (left != null) {
            parent.left = left;
            this.count++;
        }
        if (right != null) {
            parent.right = right;
            this.count++;
        }
    }

    /*
        功能： 访问节点
        参数： 节点
        返回值： 无
     */
    public void visitTreeNode(TreeNode node) {
        if (node == null) return;
        System.out.print(node.data + "\t");
    }

    private TreeNode pre = null;
    private void inOrderTreeNode(TreeNode node) {
        //递归退出条件
        if (node == null) return;
        inOrderTreeNode(node.left);
        if (node.left == null) {
            node.left = pre;
            node.leftTag = true;
        }
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightTag = true;
        }
        pre = node;
        inOrderTreeNode(node.right);
    }

    /*
        功能： 线索化二叉树
        参数： 无
        返回值： 无
     */
    public void inOrderThreadingBinaryTree() {
        inOrderTreeNode(this.root);
    }

    /*
        功能： 中序遍历线索二叉树
        参数:  无
        返回值： 无
     */
    public void inOrderThreadedBinaryTree() {
        TreeNode node = this.root;
        while (node != null) {
            //一直往左, 直到左线索点
            while (!node.leftTag) {
                node = node.left;
            }
            //访问头节点
            visitTreeNode(node);
            //一路向右
            while (node.rightTag && node.right != null) {
                node = node.right;
                visitTreeNode(node);
            }
            //重置头节点
            node = node.right;
        }
        System.out.println();
    }

    private void freeTreeNode(TreeNode node) {
        if (node == null) return;
        if (!node.leftTag) {
            freeTreeNode(node.left);
        }
        if (!node.rightTag) {
            freeTreeNode(node.right);
        }
        node.left = null;
        node.right = null;
        this.count--;
    }

    /*
        功能： 释放线索二叉树
        参数: 无
        返回值： 无
     */
    public void releaseThreadedBinaryTree() {
        freeTreeNode(this.root);
        System.out.println("tree have " + this.count + " node");
        this.root = null;
    }
}

test:

package com.Sonnet.Threaded;

public class test {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = initThreadedBinaryTree();
        tree.inOrderThreadingBinaryTree();
        tree.inOrderThreadedBinaryTree();
        tree.releaseThreadedBinaryTree();
    }

    public static ThreadedBinaryTree initThreadedBinaryTree() {
        TreeNode nodeA = new TreeNode(new Element('A'));
        TreeNode nodeB = new TreeNode(new Element('B'));
        TreeNode nodeC = new TreeNode(new Element('C'));
        TreeNode nodeD = new TreeNode(new Element('D'));
        TreeNode nodeE = new TreeNode(new Element('E'));
        TreeNode nodeF = new TreeNode(new Element('F'));
        TreeNode nodeG = new TreeNode(new Element('G'));
        TreeNode nodeH = new TreeNode(new Element('H'));
        TreeNode nodeK = new TreeNode(new Element('K'));

        ThreadedBinaryTree tree = new ThreadedBinaryTree(nodeA);
        tree.insertTreeNode(nodeA, nodeB, nodeE);
        tree.insertTreeNode(nodeB, null, nodeC);
        tree.insertTreeNode(nodeC, null, null);
        tree.insertTreeNode(nodeC, nodeD, null);
        tree.insertTreeNode(nodeD, null, null);
        tree.insertTreeNode(nodeE, null, nodeF);
        tree.insertTreeNode(nodeF, nodeG, null);
        tree.insertTreeNode(nodeG, nodeH, nodeK);

        return tree;
    }
}
# c语言 # java # 开发语言 # 数据结构
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

AI 资讯日报 | 2026年8月23日：开源提速、算力狂飙，Agent加速落地，AI产业进入资本、技术与商业化全面竞速的新阶段

avatar AI编程社区
cover

Agent 敢开写权限吗？Python 文件写入沙箱守卫实战

avatar AI编程社区

初识智能体

在过去两年中，几乎所有人都体验过大语言模型（如 ChatGPT、Claude、DeepSeek）的强大能力：写周报、润色邮件、解答编程疑难。被动响应：你问一句，它答一句。如果你的 Prompt 没有写清楚约束条件，它无法主动追问或修正目标。知行脱节：大模型能用流畅的文字告诉你“如何部署一个高可用 K8s 集群”，但它无法替你登录服务器敲下命令、查看报错日志并自动回滚。信息孤岛：大模型的知识止步于预

avatar AI编程社区