C#数据结构-线索化二叉树

概述为什么线索化二叉树？ 对于二叉树的遍历，我们知道每个节点的前驱与后继，但是这是建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点，分别指向当前节点的前驱、后继，便

为什么线索化二叉树？

对于二叉树的遍历，我们知道每个节点的前驱与后继，但是这是建立在遍历的基础上,否则我们只知道后续的左右子树。现在我们充分利用二叉树左右子树的空节点，分别指向当前节点的前驱、后继，便于快速查找树的前驱后继。

不多说，直接上代码：

/// <summary>/// 线索二叉树 节点</summary><typeparam name="T"></typeparam>public class ClueTreeNode<T>{    <summary>     内容    </summary>    public T data { get; set; }     左树    public ClueTreeNode<T> leftNode {  右树    public ClueTreeNode<T> rightNode {  0 标识左树 1 标识 当前节点的前驱    int leftTag {  0标识右树 1 标识 当前节点的后继    int rightTag { ; }    public ClueTreeNode()    {        data = default(T);        leftNode = null;        rightNode = ;    }     ClueTreeNode(T item)    {        data = item;        leftNode = ;    }}

 线索化 二叉树 ///  为什么线索化二叉树？ 第一：对于二叉树，如果有n个节点，每个节点有指向左右孩子的两个指针域，所以一共有2n个指针域。 而n个节点的二叉树一共有n-1条分支线数，也就是说，其实是有 2n-(n-1) = n+1个空指针。 这些空间不存储任何事物，白白浪费内存的资源。 第二：对于二叉树的遍历，我们知道每个节点的前驱与后继，但是这是建立在遍历的基础上。 否则我们只知道后续的左右子树。 第三：对于二叉树来说，从结构上来说是单向链表，引入前驱后继后，线索化二叉树可以认为是双向链表。class ClueBinaryTree<T> 树根节    private ClueTreeNode<T> head {  线索化时作为前驱转存    private ClueTreeNode<T> preNode {  ClueBinaryTree(){        head = new ClueTreeNode<T>();    }     ClueBinaryTree(T val){        head = (val);    }    public ClueTreeNode<T> GetRoot(){        return head;    }     插入左节点    </summary>    <param name="val"></param>    <param name="node"></param>    <returns></returns>    public ClueTreeNode<T> AddleftNode(T val,ClueTreeNode<T> node){        if (node == )            throw new ArgumentNullException("参数错误");        ClueTreeNode<T> treeNode = (val);        ClueTreeNode<T> childNode = node.leftNode;        treeNode.leftNode = childNode;        node.leftNode = treeNode;         treeNode;    }     插入右节点    public ClueTreeNode<T> AddRightNode(T val,1)"> node.rightNode;        treeNode.rightNode = childNode;        node.rightNode = treeNode;    }     删除当前节点的 左节点    public ClueTreeNode<T> DeleteleftNode(ClueTreeNode<T>null || node.leftNode == );        ClueTreeNode<T> leftChild = node.leftNode;        node.leftNode = ;         leftChild;    }     删除当前节点的 右节点    public ClueTreeNode<T> DeleteRightNode(ClueTreeNode<T>null || node.rightNode == );        ClueTreeNode<T> rightChild = node.rightNode;        node.rightNode =  rightChild;    }     中序遍历线索化二叉树    voID MIDdlePrefaceTraversal(){        ClueTreeNode<T> node = head;        while (node != )        {            //判断是否是            while (node.leftTag == 0)            {                node = node.leftNode;            }            Console.Write($ {node.data});            while (node.rightTag == 1 node.rightNode;                Console.Write($);            }            node = node.rightNode;        }    }     线索化二叉树    <param name="node"></param>    voID MIDdleClueNodes(ClueTreeNode<T>;        }        线索化左子树        MIDdleClueNodes(node.leftNode);        当左树为空时，指向前驱，标识为 1        if (node.leftNode == )        {            node.leftNode = preNode;            node.leftTag = 如果 前驱的右树不为空        if (preNode != null && preNode.rightNode == )        {            preNode.rightNode = node;            preNode.rightTag = ;        }        preNode = node;        线索化右子树        MIDdleClueNodes(node.rightNode);    }}

 

 

 

 

 

 现在我们测试：

创建树ClueBinaryTree<string> clueBinaryTree = new ClueBinaryTree<string>(A);ClueTreeNode<string> tree1 = clueBinaryTree.AddleftNode(B,clueBinaryTree.GetRoot());ClueTreeNode<string> tree2 = clueBinaryTree.AddRightNode(Cstring> tree3 = clueBinaryTree.AddleftNode(DEFG中序遍历);clueBinaryTree.MIDdlePrefaceTraversal();

打印结果：

中序遍历 D B E A F C G

 

 

总结

以上是内存溢出为你收集整理的C#数据结构-线索化二叉树全部内容，希望文章能够帮你解决C#数据结构-线索化二叉树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。