树和二叉树

树

节点（Node：）

树由一系列的节点组成，每个节点可以包含数据和指向其他节点的链接。

节点通常包含一个数据元素和若干指向其他节点的指针

根节点（Root）：

树的顶部节点称为根节点，它是树中没有父节点的唯一节点

子节点（Child）：

一个节点的子节点是指由该节点直接指向的节点

叶节点（Leaf）：

没有子节点的节点称为叶节点或终端节点

深度（Depth）：

节点的深度是从根节点到该节点的路径上的边数。

（广）度：

最大的节点的度

二叉树

每个节点最多有两个子节点的树，通常称为左子节点和右子节点

满二叉树：

在不增加层数的情况下，不能再增加节点了，即为满二叉树

第K层节点个数：

2^(k-1)

K层满二叉树：

总结点数：2^K - 1

完全二叉树：

在满二叉树的基础下，删除节点，只能从右至左，从下到上，删若干个

添加节点，只能从左至右，从上到下，添加若干个。

满二叉树一定是完全二叉树

完全二叉树不一定是满二叉树

二叉树的遍历

前序遍历：先遍历根，再遍历左子树然后再遍历右子树

中序遍历：先遍历左子树，再遍历根，再遍历右子树

后序遍历：先遍历左子树，再遍历右子树，最后遍历根

层序遍历：从上到下，从左至右，逐层遍历

前三种称为深度优先，层序遍历称为广度优先

已知一种排序，不能还原出唯一的二叉树

已知前序+中序 --->唯一的二叉树

已知后序+中序 --->唯一的二叉树

但是知道前序和后序不能还原

二叉树相关练习

1.创建二叉树

TNode_t *create_bin_tree()
{TDataType data = tree[idx++];if(data == '#'){return NULL;}TNode_t *pnode = malloc(sizeof(TNode_t));if(NULL == pnode){perror("malloc fail");return NULL;}pnode->data = data;pnode->pl = create_bin_tree();pnode->pr = create_bin_tree();return pnode;
}

2.前序遍历

void pre_order(TNode_t *proot)
{if(NULL == proot){return;}printf("%c",proot->data);pre_order(proot->pl);pre_order(proot->pr);
}

3.中序遍历

void mid_order(TNode_t *proot)
{if(NULL == proot){return;}mid_order(proot->pl);printf("%c",proot->data);mid_order(proot->pr);
}

4.后序遍历

void last_order(TNode_t *proot)
{if(NULL == proot){return;}last_order(proot->pl);last_order(proot->pr);printf("%c",proot->data);
}

5.层序遍历

void layer_order(TNode_t *pnode)
{Queue_t *qnode = create_queue();if(NULL == qnode){return;}push_queue(qnode,(QDataType)pnode);while(!is_empty_queue(qnode)){QDataType outdata;if(pop_queue(qnode,&outdata) == 0){TNode_t *node = (TNode_t *)outdata;printf("%c",outdata->data);if(node->pl){push_queue(qnode,(QDataType)node->pl);}if(node->pr){push_queue(qnode,(QDataType)node->pr);}}}destory_queue(qnode);
}

6.获取二叉树节点数

int get_tree_node(TNode_t *proot)
{if(NULL == proot){return 0;}num++;get_tree_node(proot->pl);get_tree_node(proot->pr);return num;
}

7.获取二叉树层数

int get_tree_fl(TNode_t *proot)
{if(NULL == proot){return 0;}int cntl = get_tree_fl(proot->pl);int cntr = get_tree_fl(proot->pr);return cntl > cntr ? cntl + 1 : cntr + 1;
}

//二叉树的相关函数，例如创建二叉树，前序，后序，中序等都是基于一个函数递归调用的思想，原因是，树本身就是一个递归的结构，由根节点和子节点构成，所以写写树相关的代码时离不了相关函数的递归调用。不过值得一提的是，函数的递归调用的执行效率并不高。