精华内容
下载资源
问答
  • 2021-04-24 13:44:54

    /*

    * 三叉链表实现排序二叉树

    */

    public class BSTByThreeNode {

    /**

    * 内部类: 节点Node

    *

    * @author Administrator

    */

    static class Node {

    Object data;

    Node parent;

    Node left;

    Node right;

    public Node(Object data, Node parent, Node left, Node right) {

    this.data = data;

    this.parent = parent;

    this.left = left;

    this.right = right;

    }

    @Override

    public String toString() {

    final String s = data.toString();

    return s;

    }

    @Override

    public boolean equals(Object obj) {

    if (obj == this) {

    return true;

    }

    if (obj.getClass() == Node.class) {

    Node target = (Node) obj;

    return data.equals(target.data)

    && left == target.left

    && right == target.right

    && parent == target.parent;

    }

    return false;

    }

    @Override

    public int hashCode() {

    return 3 * data.hashCode() + 5 * left.hashCode() + 7 * right.hashCode() + 13 * parent.hashCode();

    }

    }

    private Node root;

    /**

    * 创建空排序二叉树

    */

    public BSTByThreeNode() {

    root = null;

    }

    /**

    * 创建排序二叉树

    */

    public BSTByThreeNode(T o) {

    root = new Node(o, null, null, null);

    }

    /**

    * 添加节点

    */

    public void add(T ele) {

    if (root == null) {

    root = new Node(ele, null, null, null);

    } else {

    Node current = root;

    Node parent = null;

    int cmp = 0;

    while (current != null) {

    parent = current;

    cmp = ele.compareTo(current.data);

    if (cmp > 0) {

    current = current.right;

    } else {

    current = current.left;

    }

    }

    Node newNode = new Node(ele, parent, null, null);

    if (cmp > 0) {

    parent.right = newNode;

    } else {

    parent.left = newNode;

    }

    }

    }

    /**

    * 删除节点

    */

    public void remove(T ele) {

    Node target = getNode(ele);

    if (target == null) {

    return;

    }

    //被删除节点的左右子树都为空

    if (target.left == null && target.right == null) {

    if (target == root) {

    root = null;

    } else {

    if (target == target.parent.left) {

    target.parent.left = null;

    } else {

    target.parent.right = null;

    }

    target.parent = null;

    }

    }

    //左子树为空,右子树不为空

    else if (target.left == null && target.right != null) {

    //被删除的是根节点

    if (target == root) {

    root = target.right;

    } else {

    //被删除的节点是父节点的左子节点

    if (target == target.parent.left) {

    target.parent.left = target.right;

    }

    //被删除的节点是父节点的右子节点

    else {

    target.parent.right = target.right;

    }

    //被删除的节点的右子节点的父节点指向被删除节点的父节点

    target.right.parent = target.parent;

    }

    }

    //左子树不为空,右子树为空

    else if (target.left != null && target.right == null) {

    //被删除的是根节点

    if (target == root) {

    root = target.left;

    } else {

    //被删除的节点是父节点的左子节点

    if (target == target.parent.left) {

    target.parent.left = target.left;

    }

    //被删除的节点是父节点的右子节点

    else {

    target.parent.right = target.left;

    }

    //被删除的节点的左子节点的父节点指向被删除节点的父节点

    target.left.parent = target.parent;

    }

    }

    //左右子树都不为空(让中序前驱或后继节点替代所删除的节点,即左子树的最右下子节点或右子树的最左下节点)

    else {

    //leftMaxNode用于保存被删除节点左子树的最大节点

    Node leftMaxNode = target.left;

    //搜索leftMaxNode

    while (leftMaxNode.right != null) {

    leftMaxNode = leftMaxNode.right;

    }

    //从原来的子树中删除leftMaxNode

    leftMaxNode.parent.right = null;

    leftMaxNode.parent = target.parent;

    //被删除的节点是父节点的左子节点

    if (target == target.parent.left) {

    target.parent.left = leftMaxNode;

    } else {//被删除的节点是父节点的右子节点

    target.parent.right = leftMaxNode;

    }

    leftMaxNode.left = target.left;

    leftMaxNode.right = target.right;

    }

    //被删除的节点的引用都置空

    target.left = target.right = target.parent = null;

    }

    /**

    * 根据给定的值搜索节点

    */

    public Node getNode(T ele) {

    Node p = root;

    while (p != null) {

    int cmp = ele.compareTo(p.data);

    if (cmp > 0) {

    p = p.right;

    } else if (cmp < 0) {

    p = p.left;

    } else {

    break;

    }

    }

    return p;

    }

    /**

    * 广度遍历

    */

    public List breadthFirst() {

    Queue queue = new ArrayDeque();

    List list = new ArrayList();

    if (root != null) {

    queue.offer(root);

    }

    while (!queue.isEmpty()) {

    list.add(queue.peek());

    Node p = queue.poll();

    if (p.left != null) {

    queue.offer(p.left);

    }

    if (p.right != null) {

    queue.offer(p.right);

    }

    }

    return list;

    }

    /**

    * main方法测试

    */

    public static void main(String[] args) {

    BSTByThreeNode tree = new BSTByThreeNode();

    //添加节点

    tree.add(5);

    tree.add(20);

    tree.add(10);

    tree.add(3);

    tree.add(8);

    tree.add(15);

    tree.add(30);

    System.out.println(tree.breadthFirst());

    //删除节点

    tree.remove(20);

    System.out.println(tree.breadthFirst());

    }

    }

    更多相关内容
  • 数据结构源码C语言描述续,本篇描述了二叉树三叉链表结构及其操作,以及测试程序: //创建二叉树结点 TriTreeNode *CreateTriTreeNode(char data); //给二叉树添加结点,用于创建二叉树 int AddTriTreeNode(char ...
  • //利用mark(0:继续向左 1:向右 2:访问并回到双亲)的三叉链表的后序遍历(不用栈) #include<iostream> using namespace std; #define TElemType double typedef struct BiTNode { TElemType data; int mark;...

    题目6.39:
    在这里插入图片描述
    题目里面注明了mark如何使用,也让我学习到了一定的知识

    //利用mark(0:继续向左 1:向右 2:访问并回到双亲)的三叉链表的后序遍历(不用栈)
    #include<iostream>
    using namespace std;
    #define TElemType double
    typedef struct BiTNode
    {
        TElemType data;
        int mark;//标志变量0:继续向左 1:向右 2:访问该结点
        struct BiTNode* lchild,* rchild,* parent;//在二叉链表的基础上+parent构成三叉链表
    }BiTNode,* BiTree;
    
    void Creat_BiTree(BiTree& T,BiTree parent)//在原来创建二叉树的情况下设置双亲指针的值
    //递归构建三叉链表是在递归构建二叉链表的基础上
    //parent存放 指向T的双亲结点 的指针,若为根结点,则parent为nullptr
    {
        TElemType num;
        if(cin>>num){
            T=new BiTNode;
            if(!T) exit(-2);
            T->data=num;
            T->parent=parent;//设置双亲
            T->mark=0;//新开辟的结点的mark设为0
            Creat_BiTree(T->lchild,T);
            Creat_BiTree(T->rchild,T);
        }
        if(!cin){
            T=nullptr;
            if(parent)//为了后序遍历
                parent->mark++;//每有一个孩子(即T)为空,则parent的mark++
            cin.clear();
            cin.sync();
        }
    }
    
    void PreOrder_BiTree(BiTree T)//先序遍历打印三叉链表每个结点的mark值
    {
        if(T){
            cout<<T->mark<<endl;
            PreOrder_BiTree(T->lchild);
            PreOrder_BiTree(T->rchild);
        }
    }
    void PostOrder_BiTree(BiTree T)//利用mark对三叉链表进行后序遍历
    {
        BiTree p=T;
        while(p){//当p为空结束循环
            while(p->mark==0){//0:继续向左  “继续”体现了循环,所以用while
                p->mark++;
                p=p->lchild;
            }
            if(p->mark==1){//1:向右
                p->mark++;
                p=p->rchild;
            }
            if(p->mark==2){//2:访问并回到双亲结点
                cout<<p->data<<endl;
                p=p->parent;
            }
        }
    }
    
    int main()
    {
        BiTree T;
        Creat_BiTree(T,nullptr);//根结点的双亲为空
        cout<<"检验mark值:\n";
        PreOrder_BiTree(T);//带mark的三叉链表构建完成后,检验每个结点的mark值
        cout<<"检验完成\n";
        PostOrder_BiTree(T);
        return 0;
    }
    
    
    1
    2
    4
    @
    7
    3
    @
    @
    4
    @
    @
    5
    @
    @
    3
    @
    @
    检验mark值:
    0
    0
    1
    0
    2
    2
    2
    2
    检验完成
    3
    4
    7
    4
    5
    2
    3
    1
    
    Process returned 0 (0x0)   execution time : 4.365 s
    Press any key to continue.
    
    
    展开全文
  • 静态数组实现二叉树 二叉链表实现二叉树 三叉链表实现二叉树 线索二叉树 三叉链表存储结构 数据结构 //二叉树的三叉链表存储表示 typedef struct BiTPNode { TElemType data; BiTPNode *parent, *lchild, *rchild; /...

    静态数组实现二叉树

    二叉链表实现二叉树

    三叉链表实现二叉树

    线索二叉树

    三叉链表存储结构

    数据结构

    //二叉树的三叉链表存储表示
    typedef struct BiTPNode
    {
        TElemType data;
        BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
    } BiTPNode, *BiPTree
    

    存储示例

    在这里插入图片描述

    代码实现

    main.c

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-07-22     tyustli      first version
     */
    
    #include "tree.h"
    
    void visitT(BiPTree T)
    {
        if (T) // T非空
            printf("%d ", T->data);
    }
    
    int main(int argc, char *argv[])
    {
        printf("this bitree\r\n");
        int i;
        BiPTree T, c, q;
        TElemType e1, e2;
        InitBiTree(&T);
        printf("构造空二叉树后,树空否?%d(1:是 0:否)树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
        e1 = Root(T);
        if (e1)
            printf("二叉树的根为: %d \n", e1);
        else
            printf("树空,无根\n");
    
        printf("请按先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n");
        CreateBiTree(&T);
        printf("建立二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));
        e1 = Root(T);
        if (e1)
            printf("二叉树的根为: %d \n", e1);
        else
            printf("树空,无根\n");
    
        printf("\n先序递归遍历二叉树:\n");
        PreOrderTraverse(T, visitT);
        printf("\n中序递归遍历二叉树:\n");
        InOrderTraverse(T, visitT);
        printf("\n后序递归遍历二叉树:\n");
        PostOrderTraverse(T, visitT);
        printf("\n层序遍历二叉树:\n");
        LevelOrderTraverse(T, visitT);
    }
    
    /***************** end of file ******************/
    

    tree.c

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-07-22     tyustli      first version
     */
    
    #include "tree.h"
    
    // 二叉树的三叉链表存储的基本操作
    
    #define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
    
    TElemType Nil = 0; // 设整型以0为空
    
    // 操作结果:构造空二叉树T
    void InitBiTree(BiPTree *T)
    {
        *T = NULL;
    }
    
    // 初始条件:二叉树T存在。
    // 操作结果:销毁二叉树T
    void DestroyBiTree(BiPTree *T)
    {
        if (*T) // 非空树
        {
            if ((*T)->lchild)                 // 有左孩子
                DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树
            if (&(*T)->rchild)                // 有右孩子
                DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树
            free(*T);                         // 释放根结点
            *T = NULL;                        // 空指针赋0
        }
    }
    
    // 按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
    // 构造三叉链表表示的二叉树T
    void CreateBiTree(BiPTree *T)
    {
        TElemType ch;
        scanf("%d ", &ch);
        if (ch == Nil) // 空
        {
            *T = NULL;
        }
        else
        {
            *T = (BiPTree)malloc(sizeof(BiTPNode)); // 动态生成根结点
            if (!*T)
                exit(-1);
            (*T)->data = ch;               // 给根结点赋值
            (*T)->parent = NULL;           // 根结点无双亲
            CreateBiTree(&(*T)->lchild);   // 构造左子树
            if ((*T)->lchild)              // 有左孩子
                (*T)->lchild->parent = *T; // 给左孩子的双亲域赋值
            CreateBiTree(&(*T)->rchild);   // 构造右子树
            if ((*T)->rchild)              // 有右孩子
                (*T)->rchild->parent = *T; // 给右孩子的双亲域赋值
        }
    }
    
    // 初始条件:二叉树T存在。
    // 操作结果:若T为空二叉树,则返回TRUE,否则FALSE
    Status BiTreeEmpty(BiPTree T)
    {
        if (T)
            return FALSE;
        else
            return TRUE;
    }
    
    // 初始条件:二叉树T存在。
    // 操作结果:返回T的深度
    int BiTreeDepth(BiPTree T)
    {
        int i, j;
        if (!T)
            return 0; // 空树深度为0
        if (T->lchild)
            i = BiTreeDepth(T->lchild); // i为左子树的深度
        else
            i = 0;
        if (T->rchild)
            j = BiTreeDepth(T->rchild); // j为右子树的深度
        else
            j = 0;
        return i > j ? i + 1 : j + 1; // T的深度为其左右子树的深度中的大者+1
    }
    
    // 初始条件:二叉树T存在。
    // 操作结果:返回T的根
    TElemType Root(BiPTree T)
    {
        if (T)
            return T->data;
        else
            return Nil;
    }
    
    // 初始条件:二叉树T存在,p指向T中某个结点。
    // 操作结果:返回p所指结点的值
    TElemType Value(BiPTree p)
    {
        return p->data;
    }
    
    // 给p所指结点赋值为value
    void Assign(BiPTree p, TElemType value)
    {
        p->data = value;
    }
    
    #if 1
    
    typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型
    
    typedef struct QNode
    {
        QElemType data;     /* 数据域 */
        struct QNode *next; /* 指针域 */
    } QNode, *QueuePtr;
    
    typedef struct LinkQueue
    {
        QueuePtr front; // 队头指针
        QueuePtr rear;  // 队尾指针
    } LinkQueue;
    
    void InitQueue(LinkQueue *Q);
    void DestroyQueue(LinkQueue *Q);
    void ClearQueue(LinkQueue *Q);
    Status QueueEmpty(LinkQueue Q);
    int QueueLength(LinkQueue Q);
    Status GetHead(LinkQueue Q, QElemType *e);
    void EnQueue(LinkQueue *Q, QElemType e);
    Status DeQueue(LinkQueue *Q, QElemType *e);
    void QueueTraverse(LinkQueue Q, void (*vi)(QElemType));
    void print(QElemType i);
    void InitQueue(LinkQueue *Q)
    {
        Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    
        if (Q->front == NULL)
            exit(-1);
        Q->front->next = NULL;
    }
    
    void DestroyQueue(LinkQueue *Q)
    {
        while (Q->front)
        {
            Q->rear = Q->front->next;
            free(Q->front);
            Q->front = Q->rear;
        }
    }
    
    void ClearQueue(LinkQueue *Q)
    {
        QueuePtr p, q;
        Q->rear = Q->front;
        p = Q->front->next;
        Q->front->next = NULL;
        while (p)
        {
            q = p;
            p = p->next;
            free(q);
        }
    }
    Status QueueEmpty(LinkQueue Q)
    {
        if (Q.front->next == NULL)
            return TRUE;
        else
            return FALSE;
    }
    int QueueLength(LinkQueue Q)
    {
        int i = 0;
        QueuePtr p;
        p = Q.front;
        while (Q.rear != p)
        {
            i++;
            p = p->next;
        }
        return i;
    }
    Status GetHead(LinkQueue Q, QElemType *e)
    {
        QueuePtr p;
        if (Q.front == Q.rear)
            return ERROR;
        p = Q.front->next;
        *e = p->data;
    
        return OK;
    }
    void EnQueue(LinkQueue *Q, QElemType e)
    {
        QueuePtr p;
        if (!(p = (QueuePtr)malloc(sizeof(QNode))))
            exit(-1);
        p->data = e;
        p->next = NULL;
        Q->rear->next = p;
        Q->rear = p;
    }
    Status DeQueue(LinkQueue *Q, QElemType *e)
    {
        QueuePtr p;
        if (Q->front == Q->rear)
            return ERROR;
        p = Q->front->next;
        *e = p->data;
        Q->front->next = p->next;
        if (Q->rear == p)
            Q->rear = Q->front;
        free(p);
    
        return OK;
    }
    void QueueTraverse(LinkQueue Q, void (*vi)(QElemType))
    {
        QueuePtr p;
        p = Q.front->next;
        while (p)
        {
            vi(p->data);
            p = p->next;
        }
        printf("\n");
    }
    void print(QElemType i)
    {
        // printf("%s ", i);
    }
    #endif
    
    // typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型
    
    // 返回二叉树T中指向元素值为e的结点的指针
    BiPTree Point(BiPTree T, TElemType e)
    {
        LinkQueue q;
        QElemType a;
        if (T) // 非空树
        {
            InitQueue(&q);         // 初始化队列
            EnQueue(&q, T);        // 根结点入队
            while (!QueueEmpty(q)) // 队不空
            {
                DeQueue(&q, &a); // 出队,队列元素赋给a
                if (a->data == e)
                    return a;
                if (a->lchild)              // 有左孩子
                    EnQueue(&q, a->lchild); // 入队左孩子
                if (a->rchild)              // 有右孩子
                    EnQueue(&q, a->rchild); // 入队右孩子
            }
        }
        return NULL;
    }
    
    // 初始条件:二叉树T存在,e是T中某个结点
    // 操作结果:若e是T的非根结点,则返回它的双亲,否则返回"空"
    TElemType Parent(BiPTree T, TElemType e)
    {
        BiPTree a;
        if (T) // 非空树
        {
            a = Point(T, e);            // a是结点e的指针
            if (a && a != T)            // T中存在结点e且e是非根结点
                return a->parent->data; // 返回e的双亲的值
        }
        return Nil; // 其余情况返回空
    }
    
    // 初始条件:二叉树T存在,e是T中某个结点。
    // 操作结果:返回e的左孩子。若e无左孩子,则返回"空"
    TElemType LeftChild(BiPTree T, TElemType e)
    {
        BiPTree a;
        if (T) // 非空树
        {
            a = Point(T, e);            // a是结点e的指针
            if (a && a->lchild)         // T中存在结点e且e存在左孩子
                return a->lchild->data; // 返回e的左孩子的值
        }
        return Nil; // 其余情况返回空
    }
    
    // 初始条件:二叉树T存在,e是T中某个结点。
    // 操作结果:返回e的右孩子。若e无右孩子,则返回"空"
    TElemType RightChild(BiPTree T, TElemType e)
    {
        BiPTree a;
        if (T) // 非空树
        {
            a = Point(T, e);            // a是结点e的指针
            if (a && a->rchild)         // T中存在结点e且e存在右孩子
                return a->rchild->data; // 返回e的右孩子的值
        }
        return Nil; // 其余情况返回空
    }
    
    // 初始条件:二叉树T存在,e是T中某个结点
    // 操作结果:返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回"空"
    TElemType LeftSibling(BiPTree T, TElemType e)
    {
        BiPTree a;
        if (T) // 非空树
        {
            a = Point(T, e);                                                // a是结点e的指针
            if (a && a != T && a->parent->lchild && a->parent->lchild != a) // T中存在结点e且e存在左兄弟
                return a->parent->lchild->data;                             // 返回e的左兄弟的值
        }
        return Nil; // 其余情况返回空
    }
    
    // 初始条件:二叉树T存在,e是T中某个结点
    // 操作结果:返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回"空"
    TElemType RightSibling(BiPTree T, TElemType e)
    {
        BiPTree a;
        if (T) // 非空树
        {
            a = Point(T, e);                                                // a是结点e的指针
            if (a && a != T && a->parent->rchild && a->parent->rchild != a) // T中存在结点e且e存在右兄弟
                return a->parent->rchild->data;                             // 返回e的右兄弟的值
        }
        return Nil; // 其余情况返回空
    }
    
    // 初始条件:二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空
    // 操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点
    Status InsertChild(BiPTree p, int LR, BiPTree c) // 形参T无用
    {
        //           的原有左或右子树则成为c的右子树
        if (p) // p不空
        {
            if (LR == 0)
            {
                c->rchild = p->lchild;
                if (c->rchild) // c有右孩子(p原有左孩子)
                    c->rchild->parent = c;
                p->lchild = c;
                c->parent = p;
            }
            else // LR==1
            {
                c->rchild = p->rchild;
                if (c->rchild) // c有右孩子(p原有右孩子)
                    c->rchild->parent = c;
                p->rchild = c;
                c->parent = p;
            }
            return OK;
        }
        return ERROR; // p空
    }
    
    // 初始条件:二叉树T存在,p指向T中某个结点,LR为0或1
    // 操作结果:根据LR为0或1,删除T中p所指结点的左或右子树
    Status DeleteChild(BiPTree p, int LR) // 形参T无用
    {
        if (p) // p不空
        {
            if (LR == 0) // 删除左子树
                ClearBiTree(&p->lchild);
            else // 删除右子树
                ClearBiTree(&p->rchild);
            return OK;
        }
        return ERROR; // p空
    }
    
    // 先序递归遍历二叉树T
    void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
    {
        if (T)
        {
            Visit(T);                           // 先访问根结点
            PreOrderTraverse(T->lchild, Visit); // 再先序遍历左子树
            PreOrderTraverse(T->rchild, Visit); // 最后先序遍历右子树
        }
    }
    
    // 中序递归遍历二叉树T
    void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
    {
        if (T)
        {
            InOrderTraverse(T->lchild, Visit); // 中序遍历左子树
            Visit(T);                          // 再访问根结点
            InOrderTraverse(T->rchild, Visit); // 最后中序遍历右子树
        }
    }
    
    // 后序递归遍历二叉树T
    void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
    {
        if (T)
        {
            PostOrderTraverse(T->lchild, Visit); // 后序遍历左子树
            PostOrderTraverse(T->rchild, Visit); // 后序遍历右子树
            Visit(T);                            // 最后访问根结点
        }
    }
    
    // 层序遍历二叉树T(利用队列)
    void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
    {
        LinkQueue q;
        QElemType a;
        if (T)
        {
            InitQueue(&q);
            EnQueue(&q, T);
            while (!QueueEmpty(q))
            {
                DeQueue(&q, &a);
                Visit(a);
                if (a->lchild != NULL)
                    EnQueue(&q, a->lchild);
                if (a->rchild != NULL)
                    EnQueue(&q, a->rchild);
            }
        }
    }
    
    /***************** end of file ******************/
    
    

    tree.h

    /*
     * Change Logs:
     * Date           Author       Notes
     * 2021-07-22     tyustli      first version
     */
    
    #include <string.h>
    #include <ctype.h>
    #include <malloc.h> // malloc()等
    #include <limits.h> // INT_MAX等
    #include <stdio.h>  // EOF(=^Z或F6),NULL
    #include <stdlib.h> // atoi()
    #include <math.h>   // floor(),ceil(),abs()
    
    // 函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    // #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
    typedef int Status;  // Status是函数的类型,其值是函数结果状态代码,如OK等
    typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
    
    typedef int TElemType;
    
    //二叉树的三叉链表存储表示
    typedef struct BiTPNode
    {
        TElemType data;
        struct BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
    } BiTPNode, *BiPTree;
    
    void InitBiTree(BiPTree *T);
    void CreateBiTree(BiPTree *T);
    void DestroyBiTree(BiPTree *T);
    void ClearBiTree(BiPTree *T);
    Status BiTreeEmpty(BiPTree T);
    int BiTreeDepth(BiPTree T);
    TElemType Root(BiPTree T);
    TElemType Value(BiPTree p);
    void Assign(BiPTree p, TElemType value);
    BiPTree Point(BiPTree T, TElemType e);
    TElemType Parent(BiPTree T, TElemType e);
    TElemType LeftChild(BiPTree T, TElemType e);
    TElemType RightChild(BiPTree T, TElemType e);
    TElemType LeftSibling(BiPTree T, TElemType e);
    TElemType RightSibling(BiPTree T, TElemType e);
    Status InsertChild(BiPTree p, int LR, BiPTree c);
    Status DeleteChild(BiPTree p, int LR);
    void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
    void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
    void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
    void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
    
    /***************** end of file ******************/
    

    makefile

    objects  = main.o tree.o
    obj: $(objects)
    	cc -o obj $(objects) -lm
    
    main.o : tree.h
    tree.o : tree.h
    
    .PHONY : clean
    clean :
    	-rm obj $(objects)
    
    
    展开全文
  • 三叉链表

    千次阅读 2019-11-11 22:29:47
    在二叉链表的基础上增加了一个指向双亲的指针域。 data、lchild和rchild三个域的含义同二叉链表的结点结构; parent域为指向该结点的双亲结点的指针。 结点数据类型声明: template<class T> struct Node {...

    在二叉链表的基础上增加了一个指向双亲的指针域。
    在这里插入图片描述

    data、lchild和rchild三个域的含义同二叉链表的结点结构;
    parent域为指向该结点的双亲结点的指针。

    结点数据类型声明:

    template<class T>
    struct Node
    {
    	T data;
    	Node<T> * lchild, *rchild,*parent;
    };
    
    template <class T>
    BiNode<T> * BiTree<T>::Creat(BiNode<T> * &root,BiNode<T> *parent)
    {
        T ch;
        cout<<"请输入创建一棵二叉树的结点数据"<<endl;
        cin>>ch;
        if (ch=="#")
            root = NULL;
        else
        {
            root = new BiNode<T>;       //生成一个结点
            root->data=ch;
            root->parent=parent;
            Creat(root->lchild,root );    //递归建立左子树
            Creat(root->rchild,root);    //递归建立右子树
        }
        return root;
    }
    
    template<class T>
    BiTree<T>::BiTree( int i)
    {
        number=0;
        Creat(root,NULL);
    }
    

    森林转换为二叉树
    ⑴ 将森林中的每棵树转换成二叉树;
    ⑵ 从第二棵二叉树开始,
    依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子,
    当所有二叉树连起来后,此时所得到的二叉树就是由森林转换得到的二叉树。

    二叉树转换为树或森林
    ⑴ 加线——若某结点x是其双亲y的左孩子,则把结点x的右孩子、右孩子的右孩子、……,都与结点y用线连起来;
    ⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线;
    ⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林,使之层次分明。

    森林的遍历
    ⑴前序(根)遍历:前序遍历森林即为前序遍历森林中的每一棵树。
    ⑵后序(根)遍历:后序遍历森林即为后序遍历森林中的每一棵树。

    展开全文
  • 数据结构源码C语言描述续,前面上传文档描述了二叉树的递归算法,本篇描述了二叉树三叉链表的非递归操作,以及测试程序:
  • /*** @author WB* @param ** 三叉链表存储的思想是让每个节点不仅“记住”它的左、右两个子节点,还要“记住”它的父节点,因此需要为每个节点增加left、right和parent* 三个指针,分别引用该节点的左、右两个子节点...
  • 三叉链表存储表示改进于二叉链表,增加指向父节点的指针,能更好地实现结点间的访问。存储结构/* 二叉树的三叉链表存储表示 */typedef struct BiTPNode{TElemType data;struct BiTPNode *parent,*lchild,*rchild; /*...
  • 数据结构之---C语言实现二叉树的三叉链表存储表示//二叉树的三叉链表存储//杨鑫#include #include #define max(a, b) a > b ? a : b#define ClearBiTree DestroyBiTreetypedef char TElemType;// 二叉树的三叉...
  • 三叉链表及树的遍历

    2021-10-04 21:43:36
    文章目录树的三叉链表双亲链表二叉树遍历 树的三叉链表 元素:lchild data rchild parent typedef struct TriTNode { int data; //左右孩子指针 struct TriTNode *lchild, *rchild; struct TriTnode *parent; }...
  • 二叉树的三叉链表存储表示.
  • 数据结构C语言版 二叉树的三叉链表存储表示.txt大悲无泪,大悟无言,大笑无声。我们手里的金钱是保持自由的一种工具。女人在约会前,一定先去美容院;男人约会前,一定先去银行。/*数据结构C语言版 二叉树的三叉链表...
  • /*** 与二叉树的二叉链表存储相比,三叉链表存储* 多了一个指针域来记录当前节点的父节点*/class ThreeLinkBinTree{public static class TreeNode{Object data;TreeNode left; //左子节点TreeNode right; //右子节点...
  • 做课设的时候发现网上资料没有用三叉链表动态实现赫夫曼树译码器的资料,自己写了一份,方便大家学习,完全由个人创作。
  • Tnode树的标准存储表示:templatestruct Tnode{typedefstd::vector CT;CT children_;T value_;Tnode(Tconst& v = T()): children(), value_(v){ }T&value(void){ return value_; }void add_child(Tnode* ch)...
  • 三叉链表存储的思想是让每个节点持有三个引用parent、left、right,分别指向其父节点、左子节点和右子节点。如下图所示: 因此,三叉链表存储的节点大致如:class Node{T data;Node parent;Node left;Node right;}...
  • 二叉树三叉链表表示 题目描述 给定有根二叉树T,请编写一个程序,输出其各结点u的如下信息。 u的结点编号 u的深度 u的父结点 u的高 u的兄弟结点 结点的种类(根、内部结点、叶) u的子结点数 设给定二叉树拥有n个...
  • 满二叉树和完全二叉树适合顺序存储结构,一般...下- 含三个指针的结点结构(三叉链表)。 (其中 Lchild:指向左结点的指针 Parent:指向双亲结点的指针 Rchild:指向右结点的指针) Lchild data Rchild Lchi...
  • 本节主要讲述二叉树的三叉链表存储结构和相关操作
  • 三叉链表存储二叉树

    千次阅读 2019-09-17 15:01:44
    二叉树的三叉链式存储 三叉链式存储的思想是让每个节点不仅“记住”它的左,右两个节点,还要“记住”它...三叉链表存储方式是对二叉链表的一种改进,通过为树节点添加一个parent引用,可以让每个节点都能非常方便...
  • 三叉链表后序遍历

    2019-10-05 14:44:03
    【题目】假设在三叉链表的结点中增设一个标志域 (mark取值0,1或2)以区分在遍历过程中到达该结点 时应继续向左或向右或访问该结点。试以此存储结 构编写不用栈辅助的二叉树非递归后序遍历算法。 带标志域的三叉链表...
  • C++语言描述,实现三叉链表表示的二叉树,包括创建,插入,删除和循环算法遍历二叉树等!
  • 二叉树的三叉链表存储结构比二叉链表多一个指向双亲结点的指针,因此,求双亲和左右兄弟都很容易。但在构造二叉树时要另给双亲指针赋值,从而增加了复杂度。由于三叉链表和二叉链表在结构上的相似性,它们有些相应的...
  • #include<bits/stdc++.h> using namespace std; struct node { char val; node *l,*r,*parent;... node * create()// 创建三叉链表 { char ch;//按照前序遍历输入 需要#来标记 cin>>ch;
  • 二叉树的三叉链表

    2020-03-18 18:56:57
    本周要实现二叉树三叉链表的存储,刚开始想用递归的方法不过好像不行。 附一个递归代码 P.S.要区分空树 (*T)->data = c; (*T)->lchild = NULL; (*T)->rchild = NULL; CreateBiTree(&((*T)->...
  • 程序代码: /*#include<iostream> using namespace std;...//二叉链表 typedef struct BiNode{ TElemType data; struct BiNode *lchild, *rchild; }BiTNode, *BiTree; //建立二叉链表 void CreateBiT...
  • public class ThreeLinkTree {// 内部节点类public static class TreeNode {Object data;TreeNode left;TreeNode right;TreeNode parent;public TreeNode(Object data) {this.data = data;}public TreeNode(Object ...
  • 三叉链表】 在二叉链表的存储方式下,从某结点出发可以直接访问到它的孩子结点,但要找到某个结点的父节点需要从根节点开始搜索,最坏情况下,需要遍历整个二叉链表。 而三叉链表,在二叉链表的基础上加了一个...
  • 三叉链表:左子树、右子树、父节点,总的指针是n+2 在有n个结点的二叉链表中,值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外,其余N-1个结点都有一个父结点。所以,一共有N-1个...
  • typedef struct ThreadNode{ int data;... } //后序遍历 void PostOrder(ThreadNode *T){ //利用三叉链表实现遍历 for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p)){ printf("%d",p->data); } }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,181
精华内容 1,272
关键字:

三叉链表

友情链接: program75.rar