关于c:树的解读

5次阅读

共计 1209 个字符，预计需要花费 4 分钟才能阅读完成。

前几期文章我介绍了链表，队列，栈这些都是线性构造的存储形式。明天咱们来看看非线性构造的树

业余的定义：

有且只有一个称为根的节点
有若干个互不相交的子树，这些子树自身也是一颗树

艰深的定义：

树是由节点和边组成
每个节点只有一个父节点但能够有多个子节点
但有一个节点例外，该节点没有父节点，此节点称为根节点

专业术语：

深度：从根节点到最底层节点的层数称之为深度（根节点是第一层）
叶子节点：没有子节点的节点
非终端节点：理论就是非叶子节点（根节点既能够是叶子也能够是非叶子节点）
度：子节点的个数称为度（一棵树看最大的）

树的分类

个别树
任意一个节点的子节点的个数都不受限制，子节点的程序能够更改也能够不能更改，能更改的树为无序个别树，不能更改的为有序个别树
二叉树

任意一个节点的子节点个数最多两个，且子节点的地位不可更改，即左子树和右子树的地位不可更改。

分类：
1. 个别二叉树
2. 满二叉树：
  在不减少树的层数的前提下，无奈再多增加一个节点的二叉树就是满二叉树
3. 齐全二叉树：
  如果只是删除了满二叉树最底层最左边的间断若干个节点，这样造成的二叉树就是齐全二叉树。
存储：
- 间断存储：
  间断存储用数组存储【实用于齐全二叉树，不是齐全二叉树的树补充为齐全二叉树】
  
  长处：查找某个节点的父节点和子节点（也包含判断有没有子节点）方便快捷
  
  毛病：耗费内存空间过大
- 链式存储：
  链式存储两个指针域别离指向两个子节点，没有子节点的为空
  
  长处：耗用内存空间小
  
  毛病：查找父节点不不便

咱们来看看经典的二叉树的前中后序遍历

一、首先来看看先序遍历

先拜访根节点
再先序拜访左子树
再先序拜访右子树

// 先序遍历伪代码
void PreTraverseBTree(PBTNODE pT)
{if (pT != NULL) {printf("%c\n", pT->data);
        PreTraverseBTree(pT->pLchild);
        PreTraverseBTree(pT->pRchild);
    }
}

先序遍历后果 A B C D E

二、再来看看中序遍历

中序遍历左子树
再拜访根节点
再中序遍历右子树

// 中序遍历伪代码
void MidTraverseBTree(PBTNODE pT)
{if (pT != NULL) {MidTraverseBTree(pT->pLchild); 
        printf("%c\n", pT->data);
        MidTraverseBTree(pT->pRchild);     
    }
}

中序遍历后果 B A D E C

三、最初是后序遍历

先后序遍历左子树
再后序遍历右子树
再拜访根节点

// 后序遍历伪代码
void LastTraverseBTree(PBTNODE pT)
{if (pT != NULL) {LastTraverseBTree(pT->pLchild);
        LastTraverseBTree(pT->pRchild);
        printf("%c\n", pT->data);
    }
}

后序遍历后果 B E D C A

感激你看完这篇文章，有什么不对的中央欢送指出，谢谢????

正文完