中国建设银行网站余额查询,wordpress ms,百度爱采购排名,大神做的动漫网站文章目录 二叉树树的定义二叉树的定义遍历先序遍历中序遍历后序遍历层次遍历定义队列层次创建二叉树层次遍历 二叉树 树是一种非线性的数据结构#xff0c;由若干个节点组成#xff0c;节点之间存在一种父子关系#xff0c;具有层次结构。二叉树是一种特殊的树结构#xff… 文章目录 二叉树树的定义二叉树的定义遍历先序遍历中序遍历后序遍历层次遍历定义队列层次创建二叉树层次遍历 二叉树 树是一种非线性的数据结构由若干个节点组成节点之间存在一种父子关系具有层次结构。二叉树是一种特殊的树结构每个节点最多有两个子节点。树结构可以用来实现各种算法例如二叉查找树、平衡二叉树、堆等。
树的定义
树Tree 是n(n0)个结点的有限集。n0时称为空树。在任意一颗非空树中
有且仅有一个特定的称为根Root的结点当n1时其余结点可分为m(m0)个互不相交的有限集T1、T2、…、Tn其中每一个集合本身又是一棵树并且称为根的子树。
此外树的定义还需要强调以下两点
n0时根结点是唯一的不可能存在多个根结点数据结构中的树只能有一个根结点。m0时子树的个数没有限制但它们一定是互不相交的。
二叉树的定义 二叉树是n(n0)个结点的有限集合该集合或者为空集称为空二叉树或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。 从定义和图例中可以看出二叉树每个节点最多只会有两棵子树且左右子树是有顺序的次序不能随意颠倒。当一个节点既没有左子树也没有右子树则该节点为叶子节点。 代码实现 结构体定义树
typedef struct Tree{int val; //数据域struct Tree *left; // 左子树struct Tree *right; // 右子树
}Tree,*tree;遍历 二叉树作为一种存储结构将数据存入之后则需要遍历对数据进行对应的处理。而二叉树的遍历分为四种先(前)序遍历、中序遍历、后序遍历、层次遍历。 先序遍历
先序遍历是指从根节点开始经过左子树最后再遍历右子树遍历顺序为根节点-左子树-右子树。 代码实现 首先使用先序递归的创建一颗二叉树
// 创建新节点
Tree newNode(int val){Tree root (Tree) malloc(sizeof (tree));root-val val;root-left NULL;root-right NULL;return root
}
Tree CreateBiTree(int* len){//创建一颗节点数为len的二叉树if((*len)0){return NULL;}int val; //创建一个数据接收参数。printf(请输入插入数值);// 为根节点数据域赋值scanf(%d,val);//创建一个根节点Tree root newNode(val);(*len)--;root-left CreateBiTree(len); //递归创建左子树root-right CreateBiTree(len); //递归创建右子树//创建完成后返回根节点return root;
}再进行先序遍历
//先序遍历
void preorder(Tree root){if(rootNULL){return ;}// 首先输出根节点的值printf(节点的值%d\n,root-val);//先递归遍历左子树preorder(root-left);//递归遍历右子树preorder(root-right);
}运行结果 中序遍历
中序遍历是指从左子树开始再访问根节点最后遍历右子树遍历顺序为左子树-根节点-右子树。 代码实现 利用先序递归创建一颗二叉树并使用中序遍历二叉树
//中序遍历
void inorder(Tree root){//如果节点为NULL退出遍历if(rootNULL){return ;}//先递归遍历左子树inorder(root-left);// 输出根节点的值printf(节点的值%d\n,root-val);//递归遍历右子树inorder(root-right);
}运行结果 后序遍历
后序遍历是指从左子树开始再遍历右子树最后访问根节点遍历顺序为左子树-右子树-根节点。 代码实现 // 后序遍历
void postorder(Tree root){//如果节点为NULL退出遍历if(rootNULL){return ;}//先递归遍历左子树postorder(root-left);//再递归遍历右子树postorder(root-right);//输出根节点的值printf(节点的值%d\n,root-val);
}运行结果 为什么后序遍历和中序遍历的结果相同呢 因为创建二叉树的时候使用的是前序递归所以创建出来的二叉树都在根节点的左子树上其右子树为空此时这种情况被称为斜二叉树并且也被称之为二叉树退化成单链表。这样创建出来的二叉树是很浪费空间且不规范的。 所以先序递归创建的二叉树是不可取的。此时就用到层次创建二叉树层次创建是用到最多的创建方式也是较为直观的一种创建方式。
层次遍历
层次遍历是指从根节点开始然后一层一层向下遍历。 代码实现 一把是利用队列来实现层次创建及遍历二叉树
定义队列
// 定义队列
struct Queue {struct Tree *Tree;struct Queue *next;
};// 初始化队列
void initQueue(struct Queue **head, struct Queue **tail) {*head *tail NULL;
}// 入队
void enQueue(struct Queue **head, struct Queue **tail, struct Tree *Tree) {struct Queue *node (struct Queue*)malloc(sizeof(struct Queue));node-Tree Tree;node-next NULL;if (*head NULL) {*head *tail node;} else {(*tail)-next node;*tail node;}
}// 出队
struct Tree* deQueue(struct Queue **head, struct Queue **tail) {if (*head NULL) {return NULL;}struct Tree *Tree (*head)-Tree;if (*head *tail) {*head *tail NULL;} else {*head (*head)-next;}return Tree;
}层次创建二叉树
// 创建二叉树
struct Tree* createTree(int *arr, int size) { //arr为数据数组,size为层数if (size 0) {return NULL;}// 创建根节点struct Tree *root (struct Tree*)malloc(sizeof(struct Tree));root-val arr[0];root-left NULL;root-right NULL;// 初始化队列struct Queue *head, *tail;initQueue(head, tail);enQueue(head, tail, root);int i 1;// 层次遍历创建二叉树while (i size) {struct Tree *node deQueue(head, tail);// 左子树if (i size arr[i] ! -1) { //当数据为-1时证明该处为空节点node-left (struct Tree*)malloc(sizeof(struct Tree));node-left-val arr[i];node-left-left NULL;node-left-right NULL;enQueue(head, tail, node-left);}i;// 右子树if (i size arr[i] ! -1) {node-right (struct Tree*)malloc(sizeof(struct Tree));node-right-val arr[i];node-right-left NULL;node-right-right NULL;enQueue(head, tail, node-right);}i;}return root;
}层次遍历
// 层次遍历
void levelOrder(struct Tree* root) {if (root NULL) {return;}struct Queue *head, *tail; // 定义队头与队尾initQueue(head, tail);enQueue(head, tail, root);while (head ! NULL) {struct Tree *node deQueue(head, tail);printf(%d , node-val);if (node-left ! NULL) {enQueue(head, tail, node-left);}if (node-right ! NULL) {enQueue(head, tail, node-right);}}
}main函数
// 测试代码
int main() {// 层次遍历序列其中-1表示空节点int arr[] {1, 2, 3, 4, -1, -1, 5};int size sizeof(arr) / sizeof(int);// 创建二叉树struct Tree* root createTree(arr, size);// 打印二叉树levelOrder(root);return 0;
}运行结果 层次遍历已经实现接着使用层次创建二叉树并实现先中后序遍历
运行结果分别为 先序遍历 中序遍历 后序遍历
