结构 二叉树的遍历一、树由于树有一个不包含回路的特点,因此树被赋予了许多特性,如下所示:
通常情况下,我们在对树进行讨论的时候,将一棵树中的每个点称为结点:
每个结点有一个深度的概念,例如上图左边的树,4号结点深度是3。 二、二叉树1. 基本概念2. 二叉树的存储结构特点:
二叉树中有两种比较特殊的二叉树:满二叉树、完全二叉树,对于满二叉树和完全二叉树可以按照层次进行顺序存储。 满二叉树:二叉树中每个内部结点都存在左子树和右子树满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。 满二叉树的严格定义:一颗深度为h且具有2h-1个结点的二叉树。 完全二叉树:二叉树相关名词解释:
二叉树基本性质:
存储方式 实现代码: #include <stdio.h> #include <stdlib.h> #define N 10 typedef struct node { char data; struct node *lchild; /* 左子树 */ struct node *rchild; /* 右子树 */ }BiTNode, *BiTree; void CreatBiTree (BiTree *T) /* BiTree *T等价于 struct node **T */ { char ch; scanf("%c", &ch); if (ch == '#') /* 当遇到#时,令树的结点为NULL,从而结束该分支的递归 */ { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if (*T == NULL) { printf("内存分配失败"); exit(0); } (*T)->data = ch; /* 生成结点 */ CreatBiTree(&(*T)->lchild); /* 构造左子树 */ CreatBiTree(&(*T)->rchild); /* 构造右子树 */ /* 这里需要注意的是->的优先级比&高,所以&(*T)->lchild得到的是lchild的地址 */ } } int main() { int level = 1; BiTree t = NULL; printf("以前序遍历方式输入二叉树\n"); CreatBiTree(&t); /* 传入指针的地址 */ } 上面的实现代码使用的是链表,代码采用的是以前序遍历方式输入二叉树,当输入“#”时,指针指向NULL,说明是该结点是叶结点。 三、二叉树的遍历(前序/中序/后序遍历)顺序:访问根节点->前序遍历左子树->前序遍历右子树 /* 以递归方式 前序遍历二叉树 */ void PreOrderTraverse(BiTree t, int level) { if (t == NULL) { return ; } printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1); } 中序遍历:首先遍历左子树,然后访问根节点,最后遍历右子树(左->根->右) 顺序:中序遍历左子树->访问根节点->中序遍历右子树 /* 以递归方式 中序遍历二叉树 */ void PreOrderTraverse(BiTree t, int level) { if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->rchild, level + 1); } /* 以递归方式 后序遍历二叉树 */ void PreOrderTraverse(BiTree t, int level) { if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1); printf("data = %c level = %d\n ", t->data, level); } |
|