精华内容
下载资源
问答
  • 文章目录一、用数组存储层序遍历的堆1.按层序遍历2.算左子节点、算右子节点、算父节点的下标(1)伪代码结果(2)C++二、堆1.大顶堆和小顶堆2.堆的高度和层三、大顶堆排序算法1.MAX-HEAPIFY2.BUILD-MAX-HEAP3.堆排序...


    一、用数组存储层序遍历的堆

    1.按层序遍历

    在这里插入图片描述
    在这里插入图片描述

    2.算左子节点、算右子节点、算父节点的下标

    (1)伪代码结果

    在这里插入图片描述
    i为本结点,j为所求结点,采用[1,n]

    • LEFT(i)=2i\small{\text{LEFT(i)}}=2*i

    • RIGHT(i)=2i+1\small{\text{RIGHT(i)}}=2*i+1

    • PARENT(i)=i/2\small{\text{PARENT(i)}}=\lfloor i/2 \rfloor

    (2)C++

    i为本结点,j为所求结点,采用[0,n-1]

    • LEFT(i):j+1=2(i+1)j=2i+1j+1=2(i+1),则j=2*i+1

    • RIGHT(i):j+1=2(i+1)+1j=2(i+1)j+1=2(i+1)+1,则j=2(i+1)

    • PARENT(i):j+1=(i+1)/2j+1=\lfloor (i+1)/2 \rfloor,则j=(i+1)/21j=\lfloor{(i+1)/2}\rfloor-1

    二、堆

    1.大顶堆和小顶堆

    • 大顶堆:父结点比左右子节点的值都大
    • 小顶堆:父结点比左右子节点的值都小

    2.堆的高度和层

    • 高度:log2nlog_2{n}
    • 层=高度+1

    三、大顶堆排序算法

    • MAX-HEAPIFY(调整本结点以下的顶堆为大顶堆)
    • BUILD-MAX-HEAP(无序数组→大顶堆)

    1.MAX-HEAPIFY

    // 伪代码
    // 数组A,要调整的本结点下标i(调整本结点以下的顶堆为大顶堆)
    MAX-HEAPIFY(A, i)
    	// 获得左孩子下标
    	l ← LEFT(i)
    	// 获得右孩子下标
    	r ← RIGHT(i)
    
    	/* 比较本节点、左子节点、右子节点的值,让largest为最大下标 */
    	
    	// 检验l是否没有越界,并且当左孩子的值比本结点的更大时
    	if l ≤ heap-size[A] and A[l] > A[i]
    		// 则最大值的下标largest为左孩子的下标l
    		then largest ← l
    	// 否则,当本结点的值比左孩子的更大时,则最大值的下标largest为本结点的下标i
    	else largest ← i
    	
    	// 检验r是否没有越界,并且当右孩子的值比最大值结点的更大时
    	if r ≤ heap-size[A] and A[r] > A[largest]
    		// 则最大值的下标largest为右孩子的下标r
    		then largest ← r
    	
    	// 当最大值的下标不是本结点i时(需要调整因交换而破坏的下一层大顶堆)时
    	if largest ≠ i
    		// 则交换本结点和最大值结点的值
    		then exchange A[i] ⇿ A[largest]
    			 // 对最大值结点的大顶堆进行调整
    			 MAX-HEAPIFY(A, largest)
    

    在这里插入图片描述

    2.BUILD-MAX-HEAP

    感觉像是冒泡排序一样,大的元素逐渐浮上堆顶,小的元素沉积下去。

    注意:完事后数组不是降序的,左右子节点的大小还没有排

    // 伪代码
    // 无序数组A(我们想要将无序数组→大顶堆)
    BUILD-MAX-HEAP(A)
    	// 堆的大小是数组A的长度
    	heap-size[A] ← length[A]
    	// 从一半的下标开始(最后一个叶子节点的父结点下标,直接用PARENT(n))
    	// 下标递减往上遍历各个结点。
    	for i ← ⌊ length[A] / 2 ⌋ downto 1
    		// 对每个结点进行MAX-HEAPIFY(调整本结点以下的顶堆为大顶堆)
    		do MAX-HEAPIFY(A, i)
    

    在这里插入图片描述
    PS:循环不变式做验证的过程
    在这里插入图片描述

    3.堆排序算法

    // 伪代码
    // 无序数组A
    HEAPSORT(A)
    	// 将无序数组→大顶堆
    	BUILD-MAX-HEAP(A)
    	// i表示每次循环中堆的最后一个叶子结点
    	// 直到只剩下一个根节点(因为不用MAX-HEAPIFY了)
    	for i ← length[A] downto 2
    		// 交换树根A[1]和最后的叶子结点A[i]
    		do	exchange A[1] ⇿ A[i]
    			// 剪掉这个叶子结点(堆中目前的最大值),即堆的大小减1
    			heap-size[A] ← heap-size[A] - 1
    			// 对树根进行MAX-HEAPIFY,因为交换了树根A[1]和最后的叶子结点A[i]
    			MAX-HEAPIFY(A, 1)
    

    数组:增序(因为是倒着减去堆中的最大值)

    PS:A[i]是最后的叶子结点,而不是最小值的结点。

    在这里插入图片描述

    4.时间复杂度

    BUILD-MAX-HEAPnlgnnlgn

    堆排序算法nlgnnlgn

    共:还是nlgnnlgn

    四、C++实现

    #include <iostream>
    
    using namespace std;
    
    // 初始化于BUILD_MAX_HEAP(),用于MAX_HEAPIFY()中
    int heap_size;
    
    int LEFT(int i)
    {
        // 伪代码是2 * i
        return 2 * i + 1;
    }
    
    int RIGHT(int i)
    {
        // 伪代码是2 * i + 1
        return 2 * (i + 1);
    }
    
    int PARENT(int i)
    {
        // 伪代码是PARENT(i)=⌊i/2⌋
        return (int)((i + 1) / 2) - 1;
        // 或者 return floor((i + 1) / 2) - 1; 需要 #include <math.h> // for floor()
    }
    
    // 调整本结点以下的顶堆为大顶堆
    void MAX_HEAPIFY(int A[], int i)
    {
        // 获得左孩子下标
        int l = LEFT(i);
        // 获得右孩子下标
        int r = RIGHT(i);
    
    	/* 比较本节点、左子节点、右子节点的值,让largest为最大下标 */
    	
        // 本结点、左孩子、右孩子中值最大的结点下标。先假设本结点最大
        int largest = i;
        // 检验l是否没有越界,并且当左孩子的值比本结点的更大时
        if (l < heap_size && A[l] > A[i])
        {
    	    // 则最大值的下标largest为左孩子的下标l
            largest = l;
        }
        
        // 检验r是否没有越界,并且当右孩子的值比最大值结点的更大时
        if (r < heap_size && A[r] > A[largest])
        {
        	// 则最大值的下标largest为右孩子的下标r
            largest = r;
        }
    
    	// 当最大值的下标不是本结点i时(需要调整因交换而破坏的下一层大顶堆)时
        if (largest != i)
        {
            // 则交换本结点A[i]和最大值结点的值A[largest]
            swap(A[i], A[largest]);
    		// 对最大值结点的大顶堆进行调整
            MAX_HEAPIFY(A, largest);
        }
    }
    
    // 无序数组→大顶堆和初始化heap_size
    void BUILD_MAX_HEAP(int A[], int length)
    {
        // 初始化全局变量heap_size,为数组A的元素个数
        heap_size = length;
        // 从一半的下标开始(最后一个叶子节点的父结点下标,直接用PARENT(heap_size -1))
    	// 下标递减往上遍历各个结点。
        for (int i = PARENT(heap_size - 1); i >= 0; i--)
        {
        	// 对每个结点进行MAX-HEAPIFY(调整本结点以下的顶堆为大顶堆)
            MAX_HEAPIFY(A, i);
        }
    }
    
    // 要调用的堆排序函数
    void HEAPSORT(int A[], int length)
    {
        // 无序数组→大顶堆和初始化heap_size
        BUILD_MAX_HEAP(A, length);
    	// i表示每次循环中堆的最后一个叶子结点
    	// 直到只剩下一个根节点(下标0)(因为不用MAX-HEAPIFY了)
        for (int i = heap_size - 1; i >= 1; i--)
        {
            // 交换树根A[0]和最后的叶子结点A[i]
            swap(A[0], A[i]);
            // 剪掉这个叶子结点(堆中目前的最大值),即堆的大小减1
            heap_size--;
            // 对树根进行MAX-HEAPIFY,因为交换了树根A[0]和最后的叶子结点A[i]
            MAX_HEAPIFY(A, 0);
        }
    }
    
    int main()
    {
        int A[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
        int length = sizeof(A) / sizeof(A[0]);
        HEAPSORT(A, length);
        for (int i = 0; i < length; i++)
        {
            cout << A[i] << " ";
        }
        cout << endl;
        return 0;
    }
    

    五、扩展:优先级队列

    手写优先级队列

    展开全文
  • 求:给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。示例:二叉树:[3,9,20,null,null,15,7],3/9 20/15 7返回其层次遍历结果:[[3],[9,20],[15,7]]解:思路:使用广度...

    8731a31b6c853550098db38145cbb69d.png

    求:

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

    示例:

    二叉树:[3,9,20,null,null,15,7],

    3

    /

    9  20

    /

    15   7

    返回其层次遍历结果:

    [

    [3],

    [9,20],

    [15,7]

    ]

    解:

    思路:使用广度优先搜索,逐层扫描数据。这里需要一个辅助数据结构:队列。首先将根节点入队列,对每一层的扫描,都应该有一个数组保存结果。遍历当前层时,逐个从主队列中弹出数据,将数据加入到当前层的数组中,并将当前层下一层的数据放到一个临时队列中存储(这样才能知道下一层有哪些数据,并且由于队列FIFO的特性,能够保证下一次层序遍历时候的有序性)。当前层遍历完毕后,将临时队列中的数据加入到主队列中,继续进行下一层的迭代。当主队列为空时,说明所有数据已经遍历完毕,返回结果。

    这里因为Java对队列、可变数组的快速实现,因此使用Java语言实现。

    /**

    * Definition for a binary tree node.

    * public class TreeNode {

    *     int val;

    *     TreeNode left;

    *     TreeNode right;

    *     TreeNode(int x) { val = x; }

    * }

    */

    class

    Solution {

    public

    List> levelOrder(TreeNode root) {

    List> ret =

    new

    ArrayList();

    if

    (root==null)

    return

    ret;

    Queue queue =

    new

    LinkedList<>();

    queue.add(root);

    while

    (!queue.isEmpty()){

    List levelList =

    new

    ArrayList();

    Queue tmp =

    new

    LinkedList<>();

    while

    (!queue.isEmpty()) {

    TreeNode t = queue.remove();

    levelList.add(t.val);

    if

    (t.left != null) tmp.add(t.left);

    if

    (t.right != null) tmp.add(t.right);

    }

    ret.add(levelList);

    queue = tmp;

    }

    return

    ret;

    }

    }

    展开全文
  • void solve(int ALeft, int ARight, int TRoot) ... // TRoot是结果树序列的数组下标 n = ARight - ALeft + 1; if (n==0) return; L = GetLeftLength(n); // 计算出n个结点的树其左子树有多少个结点 T[T...

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    void solve(int ALeft, int ARight, int TRoot)
    {   // 初始调用为 solve(0, N-1, 0)
        // ALeft是排序后的输入序列A的左端点数组下标,ARight是右端点数组下标
        // TRoot是结果树序列的数组下标
        n = ARight - ALeft + 1;
        if (n==0) return;
        L = GetLeftLength(n);   // 计算出n个结点的树其左子树有多少个结点
        T[TRoot] = A[ALeft + L];
        LeftTRoot = TRoot * 2 + 1;   // 找到左子树的根结点数组下标,注意:数组是从0开始,堆栈是从1开始
        RightTRoot = LeftTRoot + 1;    // 找到右子树的根结点数组下标
        solve(ALeft, ALeft+L-1, LeftTRoot);
        solve(ALeft+L+1, ARight, RightTRoot);
    }
    
    • 例如
      在这里插入图片描述
      在这里插入图片描述
    展开全文
  • 二叉树(递归实现先序遍历,中序遍历,后序遍历,非递归实现先序遍历,中序遍历,后序遍历,二叉树层序遍历,二叉树结点个数,二叉树叶子结点个数,判断一颗树是否为完全二叉树) 1.构造二叉树:通过前序遍历的数组eg:"ABD##E#H#...

    二叉树(递归实现先序遍历,中序遍历,后序遍历,非递归实现先序遍历,中序遍历,后序遍历,二叉树层序遍历,二叉树结点个数,二叉树叶子结点个数,判断一颗树是否为完全二叉树)
    1.构造二叉树:通过前序遍历的数组eg:"ABD##E#H##CF##G##"构建二叉树;
    2.递归实现二叉树的前中后序遍历;
    3.非递归实现二叉树的前中后序遍历;
    4.后序遍历销毁二叉树;
    5.层序遍历:借助队列实现;
    6.判断一颗二叉树是否为完全二叉树:有右没左,或有孩子且标记为1;
    7.二叉树结点个数的计数通过遍历实现;
    8.叶子结点的个数通过判断该结点的类型实现.
    BinaryTree.h

    #ifndef _BINARYTREE_H_
    #define _BINARYTREE_H_
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    
    typedef char BTDataType;
    
    typedef struct BinaryTreeNode
    {
    	BTDataType _data;
    	struct BinaryTreeNode* _left;
    	struct BinaryTreeNode* _right;
    }BTNode;
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    BTNode* BinaryTreeCreate(BTDataType* src);
    // 递归遍历
    void BinaryTreePrevOrder(BTNode* root);//先序遍历
    void BinaryTreeInOrder(BTNode* root);//中序遍历
    void BinaryTreePostOrder(BTNode* root);//后序遍历
    void BinaryTreeLevelOrder(BTNode* root);// 层序遍历
    void BinaryTreeDestory(BTNode** root);//销毁二叉树
    // 非递归遍历
    void BinaryTreePrevOrderNonR(BTNode* root);//先序遍历
    void BinaryTreeInOrderNonR(BTNode* root);//中序遍历
    void BinaryTreePostOrderNonR(BTNode* root);//后序遍历
    //递归实现
    int BinaryTreeLeafSize(BTNode* root);二叉树叶子结点个数
    int BinaryTreeLevelKSize(BTNode* root, int k);第K层结点个数
    //非递归实现
    int BinaryTreeSizeNonR(BTNode* root);二叉树结点个数
    int BinaryTreeLeafSizeNonR(BTNode* root);//二叉树叶子结点个数
    int BinaryTreeLevelKSizeNonR(BTNode* root, int k);//第K层结点个数
    int BinaryTreeComplete(BTNode* root);// 判断二叉树是否是完全二叉树
    #endif // !_BINARYTREE_H_
    
    

    Queue.h

    #ifndef _QUEUE_H_
    #define _QUEUE_H_
    #include "BinaryTree.h"
    
    typedef BTNode * QueueDataType;
    
    typedef struct QueueNode
    {
    	QueueDataType _data;
    	struct QueueNode* _next;
    }QueueNode;
    
    typedef struct Queue {
    	QueueNode * _head;
    	QueueNode * _real;
    }Queue;
    
    void QueueInit(Queue* plist);
    void QueueDestory(Queue* plist);
    void QueuePop(Queue* plist);
    void QueuePush(Queue* plist, QueueDataType x);
    QueueDataType QueueTop(Queue* plist);
    int QueueEmpty(Queue* plist);
    int QueueSize(Queue* plist);
    
    #endif //_QUEUE_H_
    

    Stack.h

    #ifndef _Stack_H_
    #define _Stack_H_
    
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    #include "BinaryTree.h"
    
    typedef BTNode* StDataType;
    
    typedef struct Stack
    {
    	StDataType* array; // 指向动态开辟的数组
    	size_t size; // 有效数据个数
    	size_t capicity; // 容量空间的大小
    }Stack;
    
    void StackInit(Stack* psl, size_t capacity);
    void StackDestory(Stack* psl);
    void CheckCapacity(Stack* psl);
    void StackPush(Stack* psl, StDataType x);
    void StackPop(Stack* psl);
    StDataType StackTop(Stack* psl);
    int StackEmpty(Stack* psl);
    
    #endif // _Stack_H_
    
    

    Binarytree.c

    #include "BinaryTree.h"
    #include "Queue.h"
    #include "Stack.h"
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    BTNode* BinaryTreeCreate(BTDataType* src) {
    	static int s_n = 0;
    	if (src[s_n] == '#') {
    		s_n++;
    		return NULL;
    	}
    	BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
    	cur->_data = src[s_n];
    	s_n++;
    	cur->_left = BinaryTreeCreate(src);
    	cur->_right = BinaryTreeCreate(src);
    	return cur;
    }
    
    //递归遍历
    //前序遍历(递归)
    void BinaryTreePrevOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		putchar(root->_data);
    		BinaryTreePrevOrder(root->_left);
    		BinaryTreePrevOrder(root->_right);
    	}
    }
    
    //中序遍历(递归)
    void BinaryTreeInOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		BinaryTreeInOrder(root->_left);
    		putchar(root->_data);
    		BinaryTreeInOrder(root->_right);
    	}
    }
    
    //后序遍历(递归)
    void BinaryTreePostOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		BinaryTreePostOrder(root->_left);
    		BinaryTreePostOrder(root->_right);
    		putchar(root->_data);
    	}
    }
    
    //层序遍历(队列实现)
    void BinaryTreeLevelOrder(BTNode* root) {
    	BTNode* cur;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu, root);
    	while (!QueueEmpty(&qu)) {
    		cur = QueueTop(&qu);
    		putchar(cur->_data);
    		if (cur->_left) {
    			QueuePush(&qu, cur->_left);
    		}
    		if (cur->_right) {
    			QueuePush(&qu, cur->_right);
    		}
    		QueuePop(&qu);
    	}
    	QueueDestory(&qu);
    }
    
    //销毁二叉树
    void BinaryTreeDestory(BTNode** root) {
    	assert(root);
    	if (root) {
    		BinaryTreePostOrder((*root)->_left);
    		BinaryTreePostOrder((*root)->_right);
    		free(*root);
    		*root = NULL;
    	}
    }
    
    //非递归遍历(均用栈实现)
    //前序遍历(非递归)
    void BinaryTreePrevOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    }
    
    //中序遍历(非递归)
    void BinaryTreeInOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (!StackEmpty(&st) || cur) {
    		for (; cur; cur = cur->_left) {
    			StackPush(&st, cur);
    		}
    		cur = StackTop(&st);
    		putchar(cur->_data);
    		StackPop(&st);
    		cur = cur->_right;
    	}
    	StackDestory(&st);
    }
    
    //后序遍历(非递归)
    void BinaryTreePostOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	char tag[100];
    	StackInit(&st, 100);
    	do {
    		for (; cur; cur = cur->_left) {
    			StackPush(&st, cur);
    			tag[st.size - 1] = 0;
    		}
    		while (!StackEmpty(&st) && tag[st.size - 1]) {
    			cur = StackTop(&st);
    			putchar(cur->_data);
    			StackPop(&st);
    		}
    		if (!StackEmpty(&st)) {
    			cur = StackTop(&st);
    			tag[st.size - 1] = 1;
    			cur = cur->_right;
    		}
    	} while (!StackEmpty(&st));
    	StackDestory(&st);
    }
    
    //递归实现
    //二叉树叶子结点个数
    int BinaryTreeLeafSize(BTNode* root) {
    	if (root == NULL) {
    		return 0;
    	}
    	else if ((root->_left == NULL) && (root->_right == NULL)) {
    		return 1;
    	}
    	else {
    		return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
    	}
    }
    
    //第K层结点个数
    int BinaryTreeLevelKSize(BTNode* root, int k) {
    	if (root == NULL || k <= 0) {
    		return 0;
    	}
    	else if (root&&k == 1) {
    		return 1;
    	}
    	else {
    		return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
    	}
    }
    
    //非递归实现
    //二叉树结点个数
    int BinaryTreeSizeNonR(BTNode* root) {
    	assert(root);
    	int count = 0;
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		count++;
    		//putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    	return count;
    }
    
    //二叉树叶子结点个数
    int BinaryTreeLeafSizeNonR(BTNode* root) {
    	assert(root);
    	int count = 0;
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		if (cur->_left == NULL && cur->_right == NULL) {
    			count++;
    		}
    		//putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    	return count;
    }
    
    //第K层结点个数
    int BinaryTreeLevelKSizeNonR(BTNode* root, int k) {
    	if (root == NULL || k <= 0) {
    		return 0;
    	}
    	int cur_level_size = 0;
    	int cur_level = 0;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu,root);
    	while (!QueueEmpty(&qu)) {
    		cur_level++;
    		cur_level_size = QueueSize(&qu);
    		if (cur_level == k) {
    			break;
    		}
    		int tmp_count = 0;
    		while (tmp_count < cur_level_size) {
    			tmp_count++;
    			root = QueueTop(&qu);
    			QueuePop(&qu);
    			if (root->_left) {
    				QueuePush(&qu, root->_left);
    			}
    			if (root->_right) {
    				QueuePush(&qu, root->_right);
    			}
    		}
    	}
    	QueueDestory(&qu);
    	if (cur_level == k) {
    		return cur_level_size;
    	}
    }
    
    // 判断二叉树是否是完全二叉树
    int BinaryTreeComplete(BTNode* root) {
    	int tag = 0;
    	BTNode* cur;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu, root);
    	while (!QueueEmpty(&qu)) {
    		cur = QueueTop(&qu);
    		putchar(cur->_data);
    		if (root->_right&&root->_left == NULL) {
    			return 0;
    		}
    		if (tag && (root->_left || root->_right)) {
    			return 0;
    		}
    		if (cur->_left) {
    			QueuePush(&qu, cur->_left);
    		}
    		if (cur->_right) {
    			QueuePush(&qu, cur->_right);
    		}
    		else {
    			tag = 1;
    		}
    		QueuePop(&qu);
    	}
    	QueueDestory(&qu);
    	return 1;
    }
    

    Queue.c

    #include "Queue.h"
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    void QueueInit(Queue* plist) {
    	assert(plist);
    	plist->_head = NULL;
    	plist->_real = NULL;
    }
    
    void QueueDestory(Queue* plist)
    {
    	assert(plist);
    	QueueNode * tmp;
    	while (plist->_head) {
    		tmp = plist->_head;
    		plist->_head = plist->_head->_next;
    		free(tmp);
    	}
    }
    
    void QueuePop(Queue* plist)
    {
    	assert(plist);
    	QueueNode * tmp;
    	if (plist->_head) {
    		tmp = plist->_head;
    		plist->_head = plist->_head->_next;
    		free(tmp);
    	}
    }
    
    void QueuePush(Queue* plist, QueueDataType x) {
    	assert(plist);
    	QueueNode * cur = (QueueNode *)malloc(sizeof(QueueNode));
    	cur->_data = x;
    	cur->_next = NULL;
    	if (QueueEmpty(plist)) {
    		plist->_head = plist->_real = cur;
    		return;
    	}
    	plist->_real->_next = cur;
    	plist->_real = cur;
    }
    
    int QueueEmpty(Queue* plist) {
    	assert(plist);
    	return plist->_head == NULL;
    }
    
    QueueDataType QueueTop(Queue* plist) {
    	assert(plist);
    	if (QueueEmpty(plist)) {
    		return (QueueDataType)0;
    	}
    	return plist->_head->_data;
    }
    
    //队列长度
    int QueueSize(Queue* plist) {
    	assert(plist);
    	if (plist == NULL) {
    		return 0;
    	}
    	int count = 0;
    	QueueNode* cur;
    	for (cur = plist->_head; cur; cur = cur->_next) {
    		count++;
    	}
    	return count;
    }
    

    Stack.c

    #include "Stack.h"
    
    //初始栈
    void StackInit(Stack* psl, size_t capacity) {
    	assert(psl);
    	psl->capicity = capacity;
    	psl->array = (StDataType*)malloc(capacity*sizeof(StDataType));
    	assert(psl->array);
    	psl->size = 0;
    }
    
    //销毁栈
    void StackDestory(Stack* psl) {
    	assert(psl);
    	if (psl->array) {
    		free(psl->array);
    		psl->capicity = 0;
    		psl->size = 0;
    		psl->array = NULL;
    	}
    }
    
    //扩容栈
    void CheckCapacity(Stack* psl) {
    	assert(psl);
    	if (psl->size == psl->capicity) {
    		psl->capicity *= 2;
    		psl->array = (StDataType*)realloc(psl->size, psl->capicity*sizeof(StDataType));
    	}
    }
    
    //入栈
    void StackPush(Stack* psl, StDataType x) {
    	assert(psl);
    	CheckCapacity(psl);
    	psl->array[psl->size] = x;
    	psl->size++;
    }
    
    //出栈
    void StackPop(Stack* psl) {
    	assert(psl || psl->size);
    	psl->size--;
    }
    
    //返回栈顶元素
    StDataType StackTop(Stack* psl) {
    	assert(psl);
    	if (StackEmpty(psl)) {
    		return (StDataType)0;
    	}
    	return psl->array[psl->size - 1];
    }
    
    //判空
    int StackEmpty(Stack* psl) {
    	assert(psl);
    	return psl->size == 0;
    }
    
    

    main.c

    #include "BinaryTree.h"
    #include "Queue.h"
    #include "Stack.h"
    
    int main() {
    	int count;
    	Queue que;
    	//ABD##E#H##CF##G##
    	//ABD#GI##J###CE#HK###F##
    	BTNode* root = BinaryTreeCreate("ABD#GI##J###CE#HK###F##");
    	BinaryTreePrevOrder(root);
    	putchar('\n');
    	BinaryTreeInOrder(root);
    	putchar('\n');
    	BinaryTreePostOrder(root);
    	putchar('\n');
    	BinaryTreeLevelOrder(root);
    	putchar('\n');
    	BinaryTreePrevOrderNonR(root);
    	putchar('\n');
    	BinaryTreeInOrderNonR(root);
    	putchar('\n');
    	BinaryTreePostOrderNonR(root);
    	putchar('\n');
    	//printf("%d\n", BinaryTreeSize(root));
    	printf("%d\n", BinaryTreeLeafSize(root));
    	printf("%d\n", BinaryTreeSizeNonR(root));
    	printf("%d\n", BinaryTreeLeafSizeNonR(root));
    	printf("%d\n", BinaryTreeLevelKSize(root, 1));
    	printf("%d\n", BinaryTreeLevelKSize(root, 2));
    	printf("%d\n", BinaryTreeLevelKSize(root, 3));
    	printf("%d\n", BinaryTreeLevelKSize(root, 4));
    	printf("%d\n", BinaryTreeLevelKSize(root, 5));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 1));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 2));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 3));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 4));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 5));
    	BinaryTreeComplete(root);
    	putchar('\n');
    	system("pause");				   
    	return 0;
    }
    
    
    展开全文
  • 过队列的方式实现层序遍历,层序遍历与 BFS的不同点在于,层序遍历返回的每一层是一个list,而BFS是所有层拼起来的一个数组 class Solution(object): def levelorderTraversal(self, root: TreeNode): if root ...
  • //二叉树的层序遍历 void leveloredertravers(TreeNode*tp)//层序遍历 { /* *利用队列的先进先出原则 *层序遍历 *创建队列 元素为节点结构体指针数组 *从上往下进行遍历 *利用队列的特点进行层层输出 */ ...
  • 0、这是最基本的层序遍历算法,没有... * 层序遍历,使用了ArrayDeque,一个循环数组,性能很好 * @param root */ public void sequenceSearch(Node root){ checkRoot(root); Queue fkQueue = new ArrayDeque();
  • 二叉树的层序遍历

    2021-03-20 10:33:00
    题目描述:给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal 求解思路: 采用层序遍历,...
  • 二叉树的前中后序遍历(递归实现) #include <iostream> #include <cstdio> #include <string> #include <vector> #include <queue> #include <stack> #include <algorithm&...
  • 求由(1,1)到终点的最短步数,并输出对应的路径。 1.利用层序遍历,不断扩展延伸。...3.用数组实现队列。 /* 层序遍历实现广度优先搜索。 */ #include"stdio.h" #include"string.h" int next[4][2]={...
  • 102. 二叉树的层序遍历(JS实现

    千次阅读 2020-06-21 15:24:36
    1 题目 给你一个二叉树,请你返回其按 层序...这道题的主要思路是用队列来进行层序遍历,由于需要区分每一层,因此额外使用一个数组来存储下一层的节点 3代码 /** * Definition for a binary tree node. * function
  • 采用二维数组ans存储每一层的数组,同时为了保证将同一层的值写进level里,利用for循环,将确保每一层的全部输出,在 while 循环的每一轮中,都是将当前层的所有结点出队列,再将下一层的所有结点入队列,这样就实现...
  • 1. 二叉树层序遍历Ⅰ——剑指offer32-Ⅰ从上到下,从左到右打印二叉树,返回一维数组int[] res。class Solution {public int[] levelOrder(TreeNode root) {if (root == null) return new int[0];Queue q =...
  • 429 N叉树的层序遍历

    2020-09-08 10:02:19
    给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明: 树的深度不会超过 1000。 树的节点总数不会超过 5000。 方法1: ...
  • 实际上就是广度优先遍历, 借助一个队列(这里用数组代替)就可以实现: 1、先将root节点加入队列 2、队列不为空时取队列首节点 3、打印节点的值,然后将该节点的左、右子节点先后加入队尾(核心步骤,广度优先体现在...
  • 二叉树的层序遍历 1.递归实现 -相同层次的节点归入同一个数组 -传入辅助的level参数决定层次 时间复杂度O(n) 空间复杂度O(n) 2.迭代 -关键词:层次遍历 -模式识别:一旦出现树的层次遍历,都可以用队列...
  • 下面的代码主要解决的问题是:有一... 给定二叉树的根结点root,请返回打印结果,结果按照每一层一个数组进行储存,所有数组的顺序按照层数从上往下,且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
  • 将二叉树层序遍历结果装入二维数组 利用队列保存每一层的节点,遍历每一层节点,保存值,并将下一层入队列 遍历完一层之后将结果存入最终结果集合,开始下一轮,知道队列为空 代码实现 func levelOrder(root *...
  • 层序遍历实现leetcode 297-Serialize and Deserialize Binary Tree最近在写leetcode的测试集,目前想实现一个输入string类型的数组得到对应树的去序列化程序。正好这题跟297其实是一个意思,然后就顺带看了下。看...
  • // 层序遍历打印二叉树 public static void levelOrderPrintBST(TreeNode root) { Queue<TreeNode> queue = new LinkedList(); if (root==null) return; queue.offer(root); while(!queue.isEmpty()) { ...
  • 给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替) 例如: 给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树之字形层序遍历的结果是 [ [3], [20,9], [15,7] ] 输入:{1,...
  • 图一:完全二叉树以及对应的数组图二:满二叉树以及对应的数组图三:普通二叉树以及对应的数组 (字符'^'代表空节点)四:我们以这三个二叉树为例,使用C#实现四种遍历(1)构造一个二叉树顺序结构类/******************...
  • 层序遍历 ????遍历应用举例 中缀表达式采用加括号来规避运算符优先级影响 ????树的同构问题 何为同构树 总共8个结点 其后以0为起点给每个结点标号右侧两数字为其字母的左右儿子序号 根结点不一定是写在第...
  • 层序遍历:要注意的是往临时数组push节点的顺序很重要,因为我们用while循环来实现层序遍历,所以必定是最后一次循环才输出这个值,因此先往临时数组插入右子树根节点,再插入左子树根节点,然后再从数组第一个位置...
  • 给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 其实就是一会正向录入数组中,一会逆向录入数组中,一个就是从左遍历,一个就是从右...
  • N叉树的层序遍历 注意: 一般一棵多叉树的结构: 其中边长数组便于存储不定长的子节点。 class Node{ int val; vector<Node*> children; }; 而字典树(Trie)的存储结构一般为: 现将字符映射为数字,用...
  • 所以使用递归的方法真的很简单的可以实现前后遍历 因为数组的原因 所以我们没法进行中序遍历(无法知道插入到什么位置去) 先序遍历 void dfs(Node* root, vector<int>& nums) { if (root == NULL) { ...
  • 二叉树的结点定义 typedef struct BiTNode {  TElemType data;...二叉树的创建:根据字符数组创建字母ABC等代表结点,#代表空子树 也是用递归实现 bool CreateBiTree(BiTree &T,char *s,int &po

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 226
精华内容 90
关键字:

数组实现层序遍历