建站公司 知乎 discuz_温州做高端网站公司_自己怎么优化网站_网站生成器

什么是树？

1.树是一种非线性的数据结构，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。

2.树的相关概念：

叶结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等结点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
注意：空树高度为0
           只有根节点高度为1

任何一颗树都是由根+N棵子树（N>=0)组成的

3.树的定义（左孩子右兄弟表示法）：

struct TreeNode
{//无论一个父节点有多少个孩子，child指向左边开始的第一个孩子int val;struct TreeNode* leftchild;//第一个孩子节点struct TreeNode* rightbrother;//指向下一个兄弟节点};

二叉树的定义

概念：一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成
   以下均为二叉树：
   

特殊二叉树：

满二叉树：每一层的节点数都要达到最大值

完全二叉树：1）前h-1层都是满的
                      2）第h层的叶子从左到右是连续的

假设高度是h,满二叉树一共有多少个节点？

二叉树的存储结构

顺序存储：

       顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆后面的章节会专门讲解。

       顺序存储的优点：可以通过下标计算父子关系。

       数组存储的局限性：只适用于满二叉树或者完全二叉树。

链式存储：

二叉树的遍历：前序，中序，后序，层序遍历

1）前序

void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

2）中序

void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

3）后序

void HOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}HOrder(root->left);HOrder(root->right);printf("%d ", root->data);}

求二叉树的高度

int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ?leftHeight + 1 : rightHeight + 1;
}

求结点的个数

int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

求叶子节点的个数

int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left)+ TreeLeafSize(root->right);
}

求k层节点的个数

int TreeLeveSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeLeveSize(root->left, k - 1) + TreeLeveSize(root->right, k - 1);
}

二叉树查找值为x的节点：

//二叉树查找值为x的节点
BTNode* BTTreeFind(BTNode* root, BTDateType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret = BTTreeFind(root->left, x);if (ret)return ret;BTNode* bet = BTTreeFind(root->right, x);if (bet)return bet;return NULL;}

二叉树的销毁

void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}

层序遍历：利用队列的先进先出，上一层带下一层

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!Empty(&q)){BTNode* Front = QueueFront(&q);QueuePop(&q);printf("%d\n", Front->data);if (Front->left)QueuePush(&q, Front->left);if (Front->right)QueuePush(&q, Front->right);}QueueDestory(&q);
}

判断是否是完全二叉树

1.层序遍历走，空也要进队列
2.遇到第一个空节点时，开始判断，后面全空就是完全二叉树，后面非空就不是完全二叉树

bool TreeCommplte(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!Empty(&q)){BTNode* Front = QueueFront(&q);QueuePop(&q);if (Front == NULL)break;QueuePush(&q, Front->left);QueuePush(&q, Front->right);}while (!Empty(&q)){BTNode* Front = QueueFront(&q);QueuePop(&q);if (Front){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}

(完）