【学习打卡】第13天 数据结构和算法

2022/8/18 4:22:51

本文主要是介绍【学习打卡】第13天 数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二叉树

二叉树是什么

  • 树的每个节点最多只有两个子节点。
  • JS可以用Object来模拟二叉树。
{
	val: 'a',
	left: {
		val: 'b',
		left: {
			val: 'c',
			left: null,
			right: null
		},
		right: {
			val: 'd',
			left: null,
			right: null
		}
	},
	right: {
		val: 'e',
		left: {
			val: 'f',
			left: null,
			right: null
		},
		right: {
			val: 'g',
			left: null,
			right: null
		}
	}
}

二叉树的先、中、后序遍历 (递归版)

先序遍历

算法口诀:(根 —> 左 —> 右)

  1. 访问根节点
  2. 对根节点的左子树进行先序遍历
  3. 对根节点的右子树进行先序遍历
const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

const preorder = (root) => {
  if (!root) return;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

preorder(root);

// 输出:a b c d e f g

中序遍历

算法口诀:(左 —> 根 —> 右)

  1. 对根节点的左子树进行中序遍历
  2. 访问根节点
  3. 对根节点的右子树进行中序遍历
const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

const midorder = (root) => {
  if (!root) return;
  midorder(root.left);
  console.log(root.val);
  midorder(root.right);
}

midorder(root);

// 输出: c b d a f e g

后序遍历

算法口诀:(左 —> 右 —> 根)

  1. 对根节点的左子树进行后序遍历
  2. 对根节点的右子树进行后序遍历
  3. 访问根节点
const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

const nextorder = (root) => {
  if (!root) return;
  nextorder(root.left);
  nextorder(root.right);
  console.log(root.val);
}

nextorder(root);

// 输出: c d b f g e a

二叉树的先、中、后序遍历 (非递归版)

  • 利用栈和循环实现

先序遍历(根 —> 左 —> 右)

  1. 创建一个栈
  2. 先把根节点放入栈中
  3. 根节点出栈并打印,然后把右节点先入栈,再把左节点入栈
  4. 重复3步骤,直至栈为空
const preorder = (root) => {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.val);
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
}

preorder(root);

中序遍历(左 —> 根 —> 右)

  1. 创建一个栈
  2. 先把根节点放入栈中,再把左节点入栈
  3. 重复2步骤,直至当前子树的左节点为空
  4. 当前栈顶出栈并打印,将指针指向当前栈顶元素的右节点
  5. 重复2、3、4步骤,直至栈和指针都为空停止
const midorder = (root) => {
  if (!root) return;
  const stack = [];
  let p = root;
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left;
    }
    const n = stack.pop();
    console.log(n.val);
    p = n.right;
  }
}

midorder(root);

后序遍历(左 —> 右 —> 根)

  1. 创建两个栈stack和outStack
  2. stack用来循环将节点以根 —> 右 —> 左的顺序推入outStack栈中
  3. 依次输出outStack栈顶节点
const nextorder = (root) => {
  if (!root) return;
  const stack = [root];
  const outStack = [];
  while (stack.length) {
    const n = stack.pop();
    outStack.push(n);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }

  while (outStack.length) {
    const r = outStack.pop();
    console.log(r.val)
  }
}

nextorder(root);


这篇关于【学习打卡】第13天 数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程