【概述】 对于一个有 n 个结点的二叉链表,每个结点指向左右孩子的两个指针域,故共有 2n 个指针域,而 n 个结点的二叉树共有 n-1 条分支,即存在 2n-(n-1)=n+1 个空指针域,白白浪费了资源。 另一方面,在二叉链表上,只能知道每个结点的左右孩子结点的地址,而不知道某个结点的前驱和后继,要想知道,必须对二叉树进行遍历,以后每次想要知道时,都要遍历一次,这无疑浪费了时间。 综合以上两个方面,可以考虑利用空地址,存放指向结点在某种遍历次序下的前驱与后继,将指向前驱与后继的指针称为线索,加上线索的二叉链表称…

2019年6月10日 0条评论 1点热度 阅读全文

【概述】 对于一个有 n 个结点的二叉链表,每个结点指向左右孩子的两个指针域,故共有 2n 个指针域,而 n 个结点的二叉树共有 n-1 条分支,即存在 2n-(n-1)=n+1 个空指针域,白白浪费了资源。 另一方面,在二叉链表上,只能知道每个结点的左右孩子结点的地址,而不知道某个结点的前驱和后继,要想知道,必须对二叉树进行遍历,以后每次想要知道时,都要遍历一次,这无疑浪费了时间。 综合以上两个方面,可以考虑利用空地址,存放指向结点在某种遍历次序下的前驱与后继,将指向前驱与后继的指针称为线索,加上线索的二叉链表称…

2019年6月10日 0条评论 3点热度 阅读全文

【三叉链表】 在二叉链表的存储方式下,从某结点出发可以直接访问到它的孩子结点,但要找到某个结点的父节点需要从根节点开始搜索,最坏情况下,需要遍历整个二叉链表。 而三叉链表,在二叉链表的基础上加了一个指向父结点的指针域,使得即便于查找孩子结点,又便于查找父结点,但相对二叉链表而言,加大了空间开销。 template<class T> struct Node{ T data;//数据域,存放该结点的信息 Node<T> *lchild;//左指针域,存放指向左孩子的指针,当左孩子不存在时为空 N…

2019年6月9日 0条评论 0点热度 阅读全文

【三叉链表】 在二叉链表的存储方式下,从某结点出发可以直接访问到它的孩子结点,但要找到某个结点的父节点需要从根节点开始搜索,最坏情况下,需要遍历整个二叉链表。 而三叉链表,在二叉链表的基础上加了一个指向父结点的指针域,使得即便于查找孩子结点,又便于查找父结点,但相对二叉链表而言,加大了空间开销。 template<class T> struct Node{ T data;//数据域,存放该结点的信息 Node<T> *lchild;//左指针域,存放指向左孩子的指针,当左孩子不存在时为空 N…

2019年6月9日 0条评论 0点热度 阅读全文

【二叉链表】 二叉树一般采用二叉链表存储,其基本思想是:令二叉树的每个结点对应一个链表结点,链表结点除了存放与二叉树结点有关的数据信息外,还要设置指示左右孩子的指针。  template<class T> struct Node{ T data;//数据域,存放该结点的信息 Node<T> *lchild;//左指针域,存放指向左孩子的指针,当左孩子不存在时为空 Node<T> *rchild;//右指针域,存放指向右孩子的指针,当右孩子不存在时为空 }; 如图,一个二…

2019年6月9日 0条评论 1点热度 阅读全文

【二叉链表】 二叉树一般采用二叉链表存储,其基本思想是:令二叉树的每个结点对应一个链表结点,链表结点除了存放与二叉树结点有关的数据信息外,还要设置指示左右孩子的指针。  template<class T> struct Node{ T data;//数据域,存放该结点的信息 Node<T> *lchild;//左指针域,存放指向左孩子的指针,当左孩子不存在时为空 Node<T> *rchild;//右指针域,存放指向右孩子的指针,当右孩子不存在时为空 }; 如图,一个二…

2019年6月9日 0条评论 0点热度 阅读全文

【概述】 从树的孩子兄弟表示法和二叉树的二叉链表表示可以看出,树的孩子兄弟表示法实质上是二叉树的二叉链表存储形式,第一个孩子指针和右兄弟指针分别相当于二叉链表的左孩子指针和右孩子指针。 因此,从物理结构上看,树的孩子兄弟表示法和二叉树的二叉链表是相同的,只是解释不同。 以二叉链表为媒介,可导出树与二叉树的对应关系,即给出一棵树,可以找到唯一的一棵二叉树与之对应,这样树的操作实现就可借助二叉树存储,利用二叉树上的操作来实现。 【树转二叉树】 将一棵树转为二叉树的方法是: 加线:树中所有相邻兄弟结点间加一条线 去线:对…

2019年6月9日 0条评论 1点热度 阅读全文

【概述】 从树的孩子兄弟表示法和二叉树的二叉链表表示可以看出,树的孩子兄弟表示法实质上是二叉树的二叉链表存储形式,第一个孩子指针和右兄弟指针分别相当于二叉链表的左孩子指针和右孩子指针。 因此,从物理结构上看,树的孩子兄弟表示法和二叉树的二叉链表是相同的,只是解释不同。 以二叉链表为媒介,可导出树与二叉树的对应关系,即给出一棵树,可以找到唯一的一棵二叉树与之对应,这样树的操作实现就可借助二叉树存储,利用二叉树上的操作来实现。 【树转二叉树】 将一棵树转为二叉树的方法是: 加线:树中所有相邻兄弟结点间加一条线 去线:对…

2019年6月9日 0条评论 0点热度 阅读全文

【递归遍历】 以二叉链表的存储结构为例 1.先序遍历 若二叉树为空,则空操作,否则:先访问根结点,再先序遍历左子树,然后先序遍历右子树 void preOrder(Node *bt){//先序遍历根结点为bt的二叉树的递归算法 if(bt==NULL) return; else{ cout<<bt->data;//输出根节点bt的数据域 preOrder(bt->lchild);//前序遍历bt的左子树 preOrder(bt->rchild);//前序遍历bt的右子树 } } 2.中…

2019年6月9日 0条评论 2点热度 阅读全文

【递归遍历】 以二叉链表的存储结构为例 1.先序遍历 若二叉树为空,则空操作,否则:先访问根结点,再先序遍历左子树,然后先序遍历右子树 void preOrder(Node *bt){//先序遍历根结点为bt的二叉树的递归算法 if(bt==NULL) return; else{ cout<<bt->data;//输出根节点bt的数据域 preOrder(bt->lchild);//前序遍历bt的左子树 preOrder(bt->rchild);//前序遍历bt的右子树 } } 2.中…

2019年6月9日 0条评论 0点热度 阅读全文